Khá nhiều cấu trúc thực sự có thể xác định được theo hàm vòng mật mã khối, và từ cấu trúc này, người ta có thể tạo ra các bất biến hàm vòng mật mã khối để đo độ an toàn mật mã.
Một phần của câu trả lời này về cơ bản giống như của tôi câu trả lời trước đây, vì vậy trong trường hợp đó, chúng ta sẽ bỏ qua phần chứng minh kết quả.
Nếu $G,H$ là các nhóm, sau đó chúng tôi nói rằng một chức năng $\phi:G\rightarrow H$ là một đồng cấu đống nếu tồn tại một đồng cấu nhóm $\psi:G\rightarrow H$ cùng với một $b\in H$ ở đâu $\phi(g)=b\psi(g)$ cho tất cả $b\in B.$ Tương tự, ánh xạ $\phi:G\rightarrow H$ là một đồng cấu đống khi và chỉ khi
$\phi(xy^{-1}z)=\phi(x)\phi(y)^{-1}\phi(z)$ bất cứ khi nào $x,y,z\trong G$. Một phép đồng hình heap song ánh được cho là một phép tự cấu của heap.
Đối với bài viết này, hãy để $U_{0},\dots,U_{n-1},V_{0},\dots,V_{n-1}$ được các nhóm. Giả sử rằng $I_{i}:U_{i}\rightarrow V_{i}$ là một đẳng cấu nhóm bất cứ khi nào $0\leq i<n$. Để cho $K=U_{0}\times\dots\times U_{n-1},X=V_{0}\times\dots\times V_{n-1}$.
Sau đó xác định đẳng cấu nhóm $\iota:K\rightarrow X$ bằng cách cho phép
$\iota(u_{0},\dots,u_{n-1})=(I_{0}(u_{0}),\dots,I_{n-1}(u_{n-1})) $.
Nếu $0\leq i<n$, sau đó để $s_{i}:V_{i}\rightarrow V_{i}$ là một nhị phân tùy ý.
Xác định ánh xạ $S:V_{0}\times\dots\times V_{n-1}\rightarrow V_{0}\times\dots\times V_{n-1}$ bằng cách cho phép $S(v_{0},\dots,v_{n-1})=(s_{0}(v_{0}),\dots,s_{n-1}(v_{n-1}))$.
Để cho $\Gamma:X\rightarrow X$ là một heap automorphism. Để cho $P=\Gamma\circ S$, và xác định một ánh xạ $F:K\times X\rightarrow X$ bằng cách cho phép
$F(k,x)=\iota(k)P(x)$.
Đề xuất: Các ánh xạ $K^{2}\times X\rightarrow X,(j,k,x)\mapsto\iota(jk^{-1})x$ và $X^{3}\rightarrow X,(x,y,z)\mapsto xy^{-1}z$ là thứ tự đầu tiên có thể xác định được trong $(K,X,F)$.
Để cho $\pi_{i}:X\rightarrow V_{i}$ là nhóm chiếu đồng cấu. Để cho $\simeq_{i}$ là quan hệ tương đương trên $X$ nơi chúng tôi đặt $x\simeq_{i}y$ nếu và chỉ nếu $\pi_{i}(x)=\pi_{i}(y)$. Tôi khẳng định rằng tập hợp các quan hệ tương đương $\{\simeq_{0},\dots,\simeq_{n-1}\}$ thứ tự cao hơn có thể được xác định trong $(K,X,F)$ theo các giả thuyết hợp lý về mật mã khối $F$, nhưng để chứng minh khẳng định này, chúng ta sẽ cần đi qua một vài bổ đề. Từ khả năng xác định của $\{\simeq_{0},\dots,\simeq_{n-1}\}$, chúng ta có thể tạo ra nhiều bất biến hàm vòng mật mã khối để đo tính phi tuyến tính và cả hiệu ứng tuyết lở.
Vì $0\leq i<n$, và $j\in U_{i}$, để cho $s_{i}^{j}$ là hoán vị của $V_{i}$ được xác định bằng cách cho phép $s_{i}^{j}(v)=I_{i}(j)s_{i}(v)$.
Nếu $0\leq i<n$, sau đó để $H_{i}$ là nhóm tất cả các hoán vị của $V_{i}$ được tạo ra bởi $s_{i}^{j}\circ(s_{i}^{k})^{-1},(s_{i}^{j})^{-1}\circ s_{i}^{ k}$.
Để cho $H$ là nhóm tất cả các hoán vị của $X$ được tạo bởi tất cả các hoán vị của mẫu $F_{j}^{-1}\circ F_{k},F_{j}\circ F_{k}^{-1}$. quan sát rằng
$F_{j}\circ F_{k}^{-1}(x)=\iota(jk^{-1})(x)$ và $F_{j}^{-1}\circ F_{k}(x)=S^{-1}[\Gamma^{-1}[\iota(j^{-1}k)]S(x )]$. Đặc biệt,
$H$ được tạo ra bởi các hoán vị của mẫu $x\mapsto\iota(m)(x)$ cùng với các hoán vị của mẫu $S^{-1}[\iota(m)S(x)]$. Nói khác đi, $H$ được tạo ra bởi các hoán vị của mẫu
$$(x_{0},\dots,x_{n-1})\mapsto(I_{0}(m_{0})(x_{0}),\dots,I_{n-1}(m_{ n-1})(x_{n-1}))$$ và
$$(x_{0},\dots,x_{n-1})\mapsto(s_{0}^{-1}[I_{0}(m_{0})(s_{0}(x_{n -1}))],\dots,s_{n-1}^{-1}[I_{n-1}(m_{n-1})(s_{n-1}(x_{n-1} ))]).$$
Như vậy, $H$ gồm tất cả các hoán vị có dạng $h_{0}\times\dots\times h_{n-1}$ ở đâu $h_{i}\in H_{i}$ bất cứ khi nào $0\leq i<n$.
Vì vậy $H\simeq H_{0}\times\dots\times H_{n-1}$ như một sản phẩm trực tiếp bên ngoài. Chúng tôi cũng có thể viết $H$ như một sản phẩm trực tiếp nội bộ $H_{0}^{\sharp},\dots,H_{n-1}^{\sharp}$ ở đâu $H_{i}^{\sharp}$ bao gồm tất cả các ánh xạ $h\in H$ ở đâu nếu $h_{0},\dots,h_{n-1}$ là các ánh xạ trong đó $h(x_{0},\dots,x_{n-1})=(h_{0}(x_{0}),\dots,h_{n-1}(x_{n-1}))$ cho tất cả $x_{0},\dots,x_{n-1}$, sau đó
$h_{j}$ là chức năng nhận dạng bất cứ khi nào $j\neq i$. sau đó $H_{i}^{\sharp}\simeq H_{i}$ bất cứ khi nào $0\leq i<n.$
Chúng tôi nói rằng một nhóm $G$ là superindecomposible nếu bất cứ khi nào $A,B$ là các nhóm con của $G$ với $ab=ba$ bất cứ khi nào $a\trong A,b\trong B$ và $G=AB$, sau đó $|A|=1$ hoặc $|B|=1$ (hãy cho tôi biết trong phần nhận xét nếu bạn có thể nghĩ ra từ nào hay hơn từ 'siêu phân hủy').
Định lý (Krull-Schmidt): Giả sử rằng $G$ là nhóm thỏa mãn điều kiện chuỗi tăng và điều kiện chuỗi giảm trên các nhóm con chuẩn (bất kỳ nhóm hữu hạn nào cũng thỏa mãn tính chất này). Hơn nữa, giả sử rằng $G$ được viết dưới dạng một sản phẩm trực tiếp bên trong của các nhóm con không thể phân tích trực tiếp không tầm thường theo hai cách khác nhau, cụ thể là $G=G_{0}\times\dots\times G_{n-1}$ và $G=H_{0}\times\dots H_{n-1}$. Khi đó tồn tại một hoán vị $\rho$ của $\{0,\dots,n-1\}$ như vậy mà
$G_{i}\simeq H_{\rho(i)}$ vì $0\leq i<n$ và ở đâu
$$G=G_{0}\times\dots\times G_{r}\times H_{\rho(r+1)}\times\dots H_{\rho(n-1)}$$ bất cứ khi nào $0\leq r\leq n-1$.
Bổ đề: Giả sử rằng $G$ là một nhóm hữu hạn. Nếu $G$ là một sản phẩm trực tiếp bên trong của các nhóm con siêu phân tách, sau đó bất cứ khi nào chúng ta tính $G$ như sản phẩm trực tiếp nội bộ $G=G_{0}\times\dots\times G_{m-1}$ và $G=H_{0}\times\dots\times H_{n-1}$, sau đó $m=n$, và có một số hoán vị $\rho:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$ ở đâu $H_{i}=G_{\rho(i)}$ vì $0\leq i<n$.
Định lý: Tồn tại đẳng thức bậc cao $\phi$ sao cho nếu các nhóm $H_{0},\dots,H_{n-1}$ là không thể phân hủy, sau đó $(K,X,F)\models\phi(z)$ nếu và chỉ nếu $z=\{\simeq_{0},\dots,\simeq_{n-1}\}$.
Chứng minh: Quan sát rằng nhóm $H$ là thứ tự cao hơn có thể xác định được trong cấu trúc $(K,X,F)$. Hơn nữa, nhóm $H$ có một thừa số hoán vị lên đến duy nhất
$H^{\sharp}_{0}\times\dots\times H^{\sharp}_{n-1}$ thành các yếu tố không thể phân hủy của nó. Do đó, tập hợp tất cả các yếu tố bất khả phân $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$ được xác định trong $(K,X,F)$.
Bây giờ, đối với mỗi $i$, để cho $\hat{\simeq}_{i}$ là quan hệ tương đương nơi chúng ta đặt
$x\hat{\simeq}_{i}y$ nếu và chỉ nếu $h(x)=y$ cho một số $h\in H^{\sharp}_{i}$. Để cho
$\simeq_{i}$ là quan hệ tương đương trên $X$ được tạo ra bởi
$\bigcup\{\hat{\simeq}_{j}\mid j\neq i\}$. sau đó $\{\simeq_{0},\dots,\simeq_{n-1}\}$ được xác định từ $\{H^{\sharp}_{0},\dots,H^{\sharp}_{n-1}\}$. Do đó, bộ
$\{\simeq_{0},\dots,\simeq_{n-1}\}$ được xác định trong $(K,X,F)$. $\square$
Từ khả năng xác định của $\{\simeq_{0},\dots,\simeq_{n-1}\}$, chúng ta có thể định nghĩa khá nhiều bất biến hàm vòng mật mã khối.
Nếu $T_{1},T_{2}$ là các nhóm và $f_{i}:T_{i}\rightarrow T_{i}$ vì $i\in\{1,2\}$, sau đó chúng tôi nói rằng $f_{1},f_{2}$ tương đương với nhau nếu tồn tại tự biến đống $L_{1}:T_{1}\rightarrow T_{2},L_{2}:T_{2}\rightarrow T_{1}$ ở đâu
$f_{2}=L_{1}f_{1}L_{2}$. Chúng tôi nói rằng một ánh xạ $M$ là bất biến dưới tương đương affine nếu $M(f)=M(g)$ bất cứ khi nào $f,g$ tương đương nhau.
Chúng tôi nói rằng một cặp $(k,\Delta)$ là hộp hóa S nếu $\Delta$ là một tự biến hình đống và bất cứ khi nào $x\simeq_{i}y$, sau đó $\Delta\circ F_{k}(x)\simeq_{i}\Delta\circ F_{k}(y)$. Tập hợp tất cả các hộp hóa S có thứ tự cao hơn có thể xác định trong $(K,X,F)$. Quan sát rằng tồn tại một hộp hóa S, cụ thể là ánh xạ $(e,\Gamma^{-1})$. Bây giờ giả sử rằng
$(k,\Delta)$ là một hộp hóa S. Khi đó dễ dàng chỉ ra rằng mỗi $\simeq_{i}$ là một sự phù hợp đối với $\Delta\Gamma^{-1}$. Vì vậy $\Delta=E\Gamma^{-1}$ đối với một số tự động hóa đống $E$ mỗi nơi $\simeq_{i}$ là một sự phù hợp đối với $E$. Vì vậy, $\Delta\circ F_{k}=E'\circ S$ đối với một số tự động hóa đống $E'$. Do đó, đại số thương $(X,\Delta\circ F_{k})/\simeq_{i}$ tương đương với $(V_{i},s_{i})$ vì $0\leq i<n$. Từ những quan sát này, chúng tôi có được thực tế sau đây.
Thực tế: Nếu ánh xạ $M$ là bất biến dưới sự tương đương affine và có thể xác định được trong logic bậc cao hơn, khi đó ánh xạ $M^{+}$ được xác định bằng cách cho phép
$M^{+}(F)=\{M(s_{0}),\dots,M(s_{n-1})\}$ là thứ tự cao hơn có thể xác định được trong cấu trúc $(K,X,F)$. Vì vậy, $M^{+}$ là tham số bất biến hàm tròn.