Invariants of block cipher round functions and definability

In this post, we shall discuss a problem with measuring the cryptographic security of a block cipher round function along with a solution to this problem that works for block ciphers like the AES. For this post, the reader is supposed to understand the basics of model theory, some group theory, universal algebra, and cryptography (some familiarity with block ciphers would suffice).

If F:K\times X\rightarrow X is a function, then for k\in K, let F_{k}:X\rightarrow X be the mapping defined by letting F_{k}(x)=F(k,x) for each x\in X. Recall that a block cipher round function is a mapping F:K\times X\rightarrow X where for each k\in K, the mapping F_{k}:X\rightarrow X is a permutation.

Let F:\{0,1\}^{k}\times\{0,1\}^{m}\rightarrow\{0,1\}^{m} be a block cipher round function. Suppose that P is a permutation of \{0,1\}^{m} and T is a permutation of \{0,1\}^{k}. Then the block cipher round function G:\{0,1\}^{k}\times\{0,1\}^{m}\rightarrow\{0,1\}^{m} defined by G(k,x)=P(F(T(k),P^{-1}(x))) has the same level of security as F does, but mappings F and G could appear to be quite different from each other. This is a problem for any entity analyzing the security of a block cipher since an entity may assign the block ciphers F and G different levels of security even though these block ciphers should be assigned the same level of security. For example, the mapping F could have a very high level of linearity, but the permutations P,T could be chosen so that G has a low level of linearity according to such a measure of linearity.

Suppose that F:J\times X\rightarrow X,G:K\times Y\rightarrow Y are block cipher round functions. Then an isomorphism between F,G is a pair (\phi,\psi) where \phi:J\rightarrow K,\psi:X\rightarrow Y are bijections and where \psi(F(j,x))=G(\phi(j),\psi(x)) for all j\in J,x\in X. We say that block cipher round functions F,G are isomorphic (and write F\simeq G) if there exists an isomorphism from F to G.

Two isomorphic block ciphers round functions F,G should have the same level of security. Therefore, a good measure of some aspect of security of a block cipher should assign isomorphic block cipher round functions the same level of that aspect of security.

We say that a function N is a block cipher round function invariant if N(F)=N(G) whenever the block cipher round functions F,G are isomorphic. Equivalently, a block cipher round function invariant is a function N that is in some sense definable (N should at least be definable in terms of higher order logic). In this post, we shall mainly develop some theory in order to define as many aspects of block ciphers as possible. We shall then describe block cipher round function invariants N that quantify a certain aspect of cryptographic security such as non-linearity. In future posts, we shall describe other block cipher round function invariants such as the spectral radii of linear operators obtained from the block cipher round function.

Defining heap operations and other structure in a block cipher

In order to show that certain measures of security are block cipher round function invariants (such as some measures of non-linearity), we will first need to be able to define certain operations and relations from the block cipher round function F. If the function F has a nice form, then it is not too difficult to define quite a bit of structure on the sets K,X (this structure can almost make K,X into vector spaces), and one can use this structure to produce block cipher round function invariants.

Let K,X be sets. Suppose that K is a group. Suppose that the group K acts on the set X. Suppose that P:X\rightarrow X is a permutation and F:K\times X\rightarrow X is the function defined by F(k,x)=k\cdot P(x). Suppose furthermore that whenever j,k\in K,j\neq k, there exists some x\in X with j(x)\neq k(x). Plenty of block cipher round functions such as AES’s are of this form, and the block ciphers of this form can be studied mathematically. In practice, the group K is usually a vector space over F_{2} or at least an abelian 2-group.

We have F_{j}(F_{k}^{-1}(x))=j\cdot P(F_{k}^{-1}(x))=j\cdot P(P^{-1}(k^{-1}\cdot x))=j\cdot k^{-1}(x). Therefore, the mapping (i,j,k,l,x)\mapsto i\cdot j^{-1}\cdot k\cdot l^{-1}\cdot x is definable (for this post, by definable, we mean definable in the structure (J,X,F)), so the relation \{(i,j,k,l)\mid\forall x\in X,ij^{-1}kl^{-1}\cdot x=x\} is definable. However, ij^{-1}kl^{-1}\cdot x=x for all x if and only if ij^{-1}kl^{-1}=e which happens if and only if ij^{-1}k=l. Therefore, the mapping (j,k,l)\mapsto jk^{-1}l is definable, and this definable ternary operation should be considered to be an algebraic structure that looks like a group but where there is no element that is designated to be the basepoint of this algebraic structure. Let us now go over the theory of algebraic structures that are like groups except without basepoints in order to make sense of the ternary operation (j,k,l)\mapsto jk^{-1}l.

A heap is a pair (X,L) where L is a ternary operation that satisfies the following identities:

i.L(L(p,q,r),s,t)=L(p,L(s,r,q),t)=L(p,q,L(r,s,t)) whenever p,q,r,s,t\in X.

ii. L(x,x,y)=y=L(y,x,x) whenever x,y\in X.

Heaps should be considered to be algebraic structures that are very similar to groups but heaps do not have an identity element.

Example: Suppose that X,Y are sets. Then let G be the collection of all functions f:X\rightarrow Y. Then define an operation L:G^{3}\rightarrow G by letting L(f,g,h)=f\circ g^{-1}\circ h. Then (G,L) is a heap. One can easily extend this example to category theory since the collection of all isomorphisms between two fixed objects in a category is also a heap.

Example: Let X be a topological space. Suppose that x_{0},x_{1}\in X. Let A be the collection of all continuous functions f:[0,1]\rightarrow X where f(0)=x_{0},f(1)=x_{1}. Define a mapping L:A^{3}\rightarrow A by letting L(f,g,h)(t)=f(3t) for 0\leq t\leq 1/3, L(f,g,h)(t)=h(3t-2) for 2/3\leq t\leq 1, and L(f,g,h)=g(2-3t) for 1/3\leq t\leq 2/3. Define a relation \simeq on A where we set f\simeq g if f,g are homotopic. In other words, set f\simeq g if there is a continuous mapping F:[0,1]\times[0,1]\rightarrow X where if we set f_{s}(t)=f(s,t), then f_{0}=f,f_{1}=g and f_{s}\in A for each s\in[0,1]. Then \simeq is a congruence on the structure (A,L), and the quotient algebra (A,L)/\simeq is a heap know as the fundamental heap of (X,x_{0},x_{1}). One writes \pi_{1}(X,x_{0},x_{1}) for (A,L)/\simeq.

A heap with a basepoint is an algebraic structure (X,L,a) where (X,L) is a heap, and a\in X.

If \mathcal{G}=(G,\cdot) is a group with identity e, then let \mathcal{G}^{*}=(G,L,e) where L is the algebraic operation defined by letting L(x,y,z)=x\cdot y^{-1}\cdot z. If \mathcal{X}=(X,L,a) is a heap with basepoint, then let (G,\cdot) be the algebraic structure where x\cdot y=L(x,a,y).

Theorem:

  1. Suppose that \mathcal{G} is a group. Then \mathcal{G}^{*} is a heap with basepoint.

2. Suppose that \mathcal{G} is a heap with basepoint. Then \mathcal{G}^{*} is a group.

3. If \mathcal{G} is a group, then \mathcal{G}=\mathcal{G}^{**}.

4. If \mathcal{G} is a heap with basepoint, then \mathcal{G}=\mathcal{G}^{**}.

Proof: 1. Let \mathcal{G}=(G,\cdot) is a group. Suppose that L(x,y,z)=xy^{-1}z. Then

i-a. L(L(p,q,r),s,t)=pq^{-1}rs^{-1}t,

i-b. L(p,L(s,r,q),t)=pL(s,r,q)^{-1}t=p(sr^{-1}q)^{-1}t=pq^{-1}(r^{-1})^{-1}s^{-1}t=pq^{-1}rs^{-1}t, and

ic. L(p,q,L(r,s,t))=pq^{-1}rs^{-1}t.

Furthermore,

L(x,x,y)=xx^{-1}y=y=yx^{-1}x=L(y,x,x).

Therefore, \mathcal{G}=(G,L,e) is a heap with a basepoint.

2. Suppose that \mathcal{G}=(G,L,a) is a heap with a basepoint a, and x\cdot y=L(x,a,y). Then (x\cdot y)\cdot z=L(x,a,y)\cdot z=L(L(x,a,y),a,z)=L(x,a,L(y,a,z))=x\cdot(y\cdot z). Therefore, the operation \cdot is associative.

Furthermore, a\cdot x=L(a,a,x)=x, and x\cdot a=L(x,a,a)=x, so the element a is the identity of (G,\cdot). Now define a unary operation u\mapsto u^{-1} by letting x^{-1}=L(a,x,a).

Then x\cdot x^{-1}=L(x,a,x^{-1})=L(x,a,L(a,x,a))

=L(x,L(x,a,a),a)=L(x,x,a)=a.

Furthermore, x^{-1}\cdot x=L(x^{-1},a,x)=L(L(a,x,a),a,x)

=L(a,L(a,a,x),x)=L(a,x,x)=a.

Therefore, x,x^{-1} are inverses, so (G,\cdot,a) is a group.

3. Let \mathcal{G}=(G,\cdot) be a group with identity e. Suppose that

\mathcal{G}^{*}=(G,L,e), and \mathcal{G}^{**}=(G,*). Then whenever x,y\in G, we have x*y=L(x,e,y)=x\cdot e^{-1}\cdot y=x\cdot y. Therefore, \mathcal{G}=\mathcal{G}^{**}.

4. Let \mathcal{G}=(G,L,a) be a heap. Suppose that \mathcal{G}^{*}=(G,\cdot,a), and let \mathcal{G}^{**}=(G,M,a). Then

M(x,y,z)=x\cdot y^{-1}\cdot z=x\cdot L(a,y,a)\cdot z

=L(x,a,L(a,y,a))\cdot z=L(L(x,a,a),y,a)\cdot z=L(x,y,a)\cdot z

=L(L(x,y,a),a,z)=L(x,y,L(a,a,z))=L(x,y,z).

Therefore, \mathcal{G}=\mathcal{G}^{**}.

Q.E.D.

Proposition: Suppose now that G,H are groups. Then a function \phi:G\rightarrow H is a heap homomorphism if and only if there is some b\in H and a group homomorphism \psi:G\rightarrow H such that \phi(g)=a\psi(g) for each g\in G.

Proof: Let L denote the heap operation for both groups G,H. Then

\leftarrow. Suppose that \phi(g)=a\psi(g) for each g\in G and \psi:G\rightarrow H is a group homomorphism. Then \phi(L(x,y,z))=a\psi(L(x,y,z))=a\psi(xy^{-1}z)=a\psi(x)\psi(y)^{-1}\psi(z)

=a\psi(x)\psi(y)^{-1}a^{-1}a\psi(z)=\phi(x)\phi(y)^{-1}\phi(z)=L(\phi(x),\phi(y),\phi(z)).

\rightarrow. Suppose that \phi is a heap homomorphism. Then let

a=\phi(e). Then let \psi:G\rightarrow G is a mapping such that \psi(g)=a^{-1}\phi(g) for each g\in G. Then

\psi(g)\psi(h)=a^{-1}\phi(g)a^{-1}\phi(h)

=a^{-1}\phi(g)\phi(e)^{-1}\phi(h)=a^{-1}\phi(ge^{-1}h)=a^{-1}\phi(gh)=\psi(gh). Q.E.D.

One can also obtain a group from a heap without needing to assign the heap an arbitrary point as its basepoint.

Suppose that G is a heap. Then let \simeq be the relation on G\times G where we set (w,x)\simeq(y,z) if and only if [w,x,z]=y.

Proposition: \simeq is an equivalence relation on G\times G

Proof outline: One can show that \simeq the old fashioned way by showing that \simeq is reflexive, symmetric, and transitive. One can also observe that there is a group operation \cdot where [x,y,z]=xy^{-1}z, and here, if (w,x)\simeq(y,z) if and only if wx^{-1}=yz^{-1}. Q.E.D.

Proposition: If x,y\in G, then (x,x)\simeq(y,y).

Proof: We have [x,x,y]=y, so (x,x)\simeq(y,y). Q.E.D.

Now, define a operations *, and ^{-1} by letting (w,x)*(y,z)=([w,x,y],z) and (x,y)^{-1}=(y,x).

Proposition: The operation * is associative.

Proof: ((u,v)*(w,x))*(y,z)=([u,v,w],x)*(y,z)=([[u,v,w],x,y],z)

=([u,v,[w,x,y]],z)=(u,v)*([w,x,y],z)=(u,v)*((w,x)*(y,z)).

Proposition: \simeq is a congruence with respect to the operations * and ^{-1}.

Proof outline: One can show that (u,v)\simeq(w,x)\Rightarrow(u,v)*(y,z)\simeq(w,x)*(y,z) and (w,x)\simeq(y,z)\Rightarrow(u,v)*(w,x)\simeq(u,v)*(y,z) and (w,x)\simeq(y,z)\Rightarrow(w,x)^{-1}\simeq(y,z)^{-1} the old fashioned way. One can also define a mapping \phi:G^{2}\rightarrow G by letting \phi(x,y)=xy^{-1}. The mapping \phi is clearly a homomorphism from (G,*,^{-1}) to (G,\cdot,^{-1}), and \ker(\phi) is just \simeq. Q.E.D.

Therefore, let x/y denote the equivalence class of (x,y) with respect to the equivalence relation \simeq.

Let e=x/x. We have already shown that e does not depend on the choice of x. Let \cdot,^{-1} denote the operations where we set (w/x)\cdot(y/z)=[w,x,y]/z which is the equivalence class containing (w,x)*(y,z) and where (x/y)^{-1}=y/x which is the equivalence class containing (x,y)^{-1}.

Proposition: ((G\times G)/\simeq,\cdot,^{-1},e) is a group.

Proof outline: It is not too hard to show that ((G\times G)/\simeq,\cdot,^{-1},e) satisfies the group axioms, but there is another way of proving that ((G\times G)/\simeq,\cdot,^{-1},e) is a group.

The mapping \phi:G^{2}\rightarrow G in the above proposition is a surjective homomorphism. Therefore, the mapping \theta:G^{2}/\simeq\rightarrow G defined by \theta(x/y)=\phi(x,y) is an isomorphism. Since G is a group, the structure G^{2}/\simeq is isomorphic to G, so G^{2}/\simeq is a group as well. Q.E.D.

Observe that the group K^{2}/\simeq is definable in (K,X,F), and the action of K^{2}/\simeq on X defined by letting (j/k)\cdot x=(j\cdot k^{-1})(x) is also definable since (j/k)\cdot x=F_{j}(F_{k}^{-1}(x)).

Suppose that K is a heap. Then a heap action of K on a set X is a mapping \theta:K\rightarrow\text{Sym}(X) such that \theta([j,k,l])=\theta(j)\theta(k)^{-1}\theta(l) whenever j,k,l\in K (one can generalize the notion of a heap action further to a function \theta:K\rightarrow\text{Iso}(X,Y) where \theta([j,k,l])=\theta(j)\theta(k)^{-1}\theta(l) for all j,k,l\in K, but we do not need this more general notion of a heap action). From the following proposition, we see that the heap actions are just group actions composed with a permutation.

Proposition: Suppose that K is a group and \theta:K\rightarrow\text{Sym}(X) is a function. Then the following are equivalent:

  1. the mapping \theta is a heap action.
  2. there is some permutation P:X\rightarrow X and a group action of K on X where \theta(k)(x)=k\cdot P(x) whenever k\in K,x\in X.
  3. There is a permutation Q:X\rightarrow X and a group action of K on X where \theta(k)(x)=Q(k\cdot x).

Proposition: Suppose that G is a group, and \theta:G\rightarrow X is a heap action.

  1. There exists a unique pair (\cdot,P) where \cdot is an action of the group G on X and where \theta(g)=g\cdot P(x) for all g\in G,x\in X.

2. There exists a unique pair (\#,Q) where \# is an action of the group G on X and where \theta(g)=Q(g\# x) for all g\in G,x\in X.

3. P=Q and the actions \cdot,\# are conjugate in the sense that g\# x=P^{-1}(g\cdot P(x)) and g\cdot x=P(g\# P^{-1}(x)) whenever g\in G,x\in X.

A faithful group action of a group G on a set X is said to be a torsor if for each x,y\in X, there exists a unique g\in G with g\cdot x=y. A faithful group action is a torsor if and only if there exists a (not necessarily definable) group structure on X and an isomorphism \iota:G\rightarrow X such that g\cdot x=\iota(g)x whenever g\in G,x\in X.

A heap torsor is a heap action \theta:K\rightarrow\text{Sym}(X) such that for each x,y\in X, there exists a unique k\in K where \theta(k)(x)=y. If K is a group, then \theta:K\rightarrow\text{Sym}(X) is a heap torsor if and only if there is a group operation \cdot on X and a group isomorphism \iota:K\rightarrow X such that \theta(k)(x)=\iota(k)P(x). If \theta is a heap torsor, then the heap operations on X,K are definable from \theta. We observe that plenty of block cipher round functions including AES’s round function are heap torsors.

Heap torsor duality

There are several structures that are equivalent to the notion of a heap torsor.

Let G be a group. Then whenever P:G\rightarrow G is a permutation of G and g\in G, let gP:G\rightarrow G be the permutation be defined by letting gP(x)=g\cdot P(x) for each x\in G. Let GP=\{gP\mid g\in G\}. Observe that the set of operations GP only depends on the heap operation on G. A heap with permutation coset is a pair (G,GP) where G is a heap and P is some permutation of G.

If \mathcal{G}=(G,GP) is a heap with permutation coset where L is the heap operation on G, then let \Omega,\mho be the operations defined by letting \Omega(x,y,z)=L(x,P(y)^{-1},P(z)) and \mho(x,y,z)=P^{-1}(L(P(x),y,z) The operations \Omega,\mho do not depend on the representative P of GP. Let \mathcal{G}^{*}=(G,L,\Omega,\mho).

A one-sorted heap torsor is a set G together with three ternary operations L,\Omega,\mho such that (G,L) is a heap and L,\Omega,\mho satisfy the following identities:

  1. \Omega(a,b,\mho(b,a,x))=\mho(a,b,\Omega(b,a,x))=x and
  2. \Omega(x,y,z)=L(x,\Omega(a,b,y),\Omega(a,b,z)).

If \mathcal{G}=(G,\Omega,\mho,L) is a one-sorted heap torsor, then whenever a,b\in G, let P_{a,b}:G\rightarrow G be the mapping defined by letting P_{a,b}(x)=\Omega(a,b,x).

Proposition: Suppose that \mathcal{G}=(G,\Omega,\mho,L) is a one-sorted heap torsor. Then whenever a,b,c,d\in G, we have GP_{a,b}=GP_{c,d}.

Proof: For simplicity, suppose that G is a group. Then P_{a,b}(x)=\Omega(a,b,x)=a\cdot P_{c,d}(b)^{-1}\cdot P_{c,d}(x). Therefore, P_{a,b}\in GP_{c,d}, so GP_{a,b}=GP_{c,d}.

Q.E.D.

If \mathcal{G}=(G,L,\Omega,\mho) is a one-sorted heap torsor, then let \mathcal{G}^{*}=(G,GP_{a,b}) whenever a,b\in G.

If \mathcal{G}=(G,GP) is a heap with permutation coset and heap operation L, then let \Omega:G^{3}\rightarrow G be the mapping where \Omega(x,y,z)=L(x,P(y),P(z)) and \mho(x,y,z)=P^{-1}(L(P(x),y,z)). Then \Omega,\mho do not depend on the representative P of GP. Let \mathcal{G}^{*}=(G,L,\Omega,\mho).

Theorem:

  1. Suppose that \mathcal{G} is a heap with permutation coset. Then \mathcal{G}^{*} is a one-sorted heap torsor.
  2. Suppose that \mathcal{G} is a one-sorted heap torsor. Then \mathcal{G}^{*} is a heap with permutation coset.
  3. If \mathcal{G} is a heap with permutation coset, then \mathcal{G}=\mathcal{G}^{**}.
  4. If \mathcal{G} is a one-sorted heap torsor, then \mathcal{G}=\mathcal{G}^{**}.

Proof:

(1). For simplicity, assume that G is a group. Then L(x,\Omega(a,b,y),\Omega(a,b,z))=x\Omega(a,b,y)^{-1}\Omega(a,b,z)

=x(aP(b)^{-1}P(y))^{-1}aP(b)^{-1}P(z)=xP(y)^{-1}P(b)a^{-1}aP(b)^{-1}P(z)=xP(y)^{-1}P(z)=\Omega(x,y,z).

Furthermore, \Omega(a,b,x)=y if and only if aP(b)^{-1}P(x)=y if and only if

x=P^{-1}(P(b)a^{-1}y) if and only if x=\mho(b,a,y). Therefore, the mappings

x\mapsto\Omega(a,b,x),y\mapsto\mho(b,a,y) are inverses. We conclude that \mathcal{G}^{*} is a one-sided heap torsor.

2. This is trivial.

3. Suppose that \mathcal{G}=(G,GP) is a heap with permutation coset and heap operation L. Then let \mathcal{G}^{*}=(G,L,\Omega,\mho). Then \mathcal{G}^{**}=(G,GP_{a,b}) where a,b\in G and P_{a,b} is the mapping where P_{a,b}(x)=\Omega(a,b,x)=aP(b)^{-1}P(x). In this case, we have

GP_{a,b}=GP, so \mathcal{G}=\mathcal{G}^{**}.

4. Suppose that \mathcal{G}=(G,L,\Omega,\mho) is a one-sorted heap torsor. For a,b\in G, recall that P_{a,b}(x)=\Omega(a,b,x) for a,b\in G. Then \mathcal{G}^{*}=(G,GP_{a,b}) whenever a,b\in G. Therefore, let \mathcal{G}^{**}=(G,L,\Omega^{**},\mho^{**}). Then \Omega^{**}(x,y,z)=L(x,P_{a,b}(y),P_{a,b}(z))=L(x,\Omega(a,b,y),\Omega(a,b,z))=\Omega(x,y,z).

Therefore \Omega^{**}=\Omega. Since the mappings x\mapsto\Omega(a,b,x) is an inverse to x\mapsto\mho(b,a,x) and x\mapsto\Omega^{**}(a,b,x) is an inverse to x\mapsto\mho^{**}(b,a,x), we know that \mho=\mho^{**} as well. Therefore, \mathcal{G}=\mathcal{G}^{**}.

Q.E.D.

Let us now construct a duality between one-sorted heap torsors and heap torsors.

Suppose that F:K\times X\rightarrow X is a heap torsor mapping. Let \mathcal{X}=(K,X,F) Let L denote the heap operation on both K and X.

For simplicity, suppose that K,X are groups, \iota:K\rightarrow X is a group isomorphism, and P:X\rightarrow X is a permutation such that F(k,x)=\iota(k)P(x) for all k\in K,x\in X.

Then whenever x,y,z, let k\in K be the unique element with F(k,y)=x. Then define \Omega(x,y,z)=F(k,z). We observe that x=F(k,y)=\iota(k)P(y), and \iota(k)=xP(y)^{-1}, so \Omega(x,y,z)=F(k,z)=\iota(k)P(z)=xP(y)^{-1}P(z).

Let \mho:X^{3}\rightarrow X be the mapping where if a,b\in X, then x\mapsto\Omega(a,b,x),y\mapsto\mho(b,a,x) are inverses. Let \mathcal{X}^{+}=(X,L,\Omega,\mho).

Suppose that \mathcal{G}=(G,L,\Omega,\mho) is a one-sorted heap torsor. Then define an relation on G^{2} where we set (r,s)\simeq(t,u) if and only if \Omega(r,s,u)=t.

We observe that if G is endowed with a group operation and a permutation P such that \Omega(x,y,z)=xP(y)P(z)^{-1} for all x,y,z\in G, then (r,s)\simeq(t,u) if and only if \Omega(r,s,u)=t iff rP(s)^{-1}P(u)=t iff rP(s)^{-1}=tP(u)^{-1}. In particular, \simeq is an equivalence relation, and \Omega(r,s,x)=\Omega(t,u,x) if and only if (r,s)\simeq(t,u).

Define a ternary operation L:(G^{2})^{3}\rightarrow G^{2} by letting L((p,q),(r,s),(t,u))=(\Omega(p,q,s),\mho(u,t,r)).

Define a mapping \phi:G^{2}\rightarrow G by letting \phi(r,s)=rP(s)^{-1}.

Proposition: The mapping \phi:G^{2}\rightarrow G preserves the operation \phi in the sense that \phi(L((p,q),(r,s),(t,u)))=L(\phi(p,q),\phi(r,s),\phi(t,u)).

Proof:

L(\phi(p,q),\phi(r,s),\phi(t,u))=L(pP(q)^{-1},rP(s)^{-1},tP(u)^{-1})=pP(q)^{-1}(rP(s)^{-1})^{-1}tP(u)^{-1}

=pP(q)^{-1}P(s)r^{-1}tP(u)^{-1}=\Omega(p,q,s)(P(u)t^{-1}r)^{-1}=\Omega(p,q,s)P(\mho(u,t,r))^{-1}

=\phi(\Omega(p,q,s),\mho(u,t,r)).

Q.E.D.

Since \phi is a surjective homomorphism from (G^{2},L) to (G,L) with kernel \simeq, the equivalence relation \simeq is a congruence, and the mapping \theta:(G^{2}/\simeq,L)\rightarrow(G,L) defined by letting \theta([p,q])=\phi(p,q) is a heap isomorphism.

Define a mapping \omega:G^{2}/\simeq\times G\rightarrow G by letting \omega([p,q],x)=\Omega(p,q,x). The mapping \omega is a well-defined mapping.

Proposition: The mapping \omega is a heap torsor.

Proof: Let’s overload the symbol \omega by letting \omega([p,q])(x)=\omega([p,q],x). Then

\omega([p,q])\circ\omega([r,s])^{-1}\circ\omega([t,u])(x)

=pP(q)^{-1}P\circ\omega([r,s])^{-1}[tP(u)^{-1}P(x)]=pP(q)^{-1}P(s)r^{-1}tP(u)^{-1}P(x)

=\Omega(p,q,s)(P(u)t^{-1}r)^{-1}P(x)=\Omega(p,q,s)P(\mho(u,t,r))^{-1}P(x).

=\omega([\Omega(p,q,s),\mho(u,t,r)],x)=\omega(L([p,q],[r,s],[t,u]),x).

We observe that \omega([y,x],x)=\Omega(y,x,x)=yP^{-1}(x)P(x)=y.

Now, if \omega([a,b],x)=\omega([c,d],x), then \Omega(a,b,x)=\Omega(c,d,x), so aP(b)^{-1}P(x)=cP(d)^{-1}P(x). Therefore, aP(b)^{-1}=cP(d)^{-1}. We conclude that [a,b]=[c,d]. Therefore, \omega is a heap torsor.

Q.E.D.

Let \mathcal{G}^{+}=(G^{2}/\simeq,G,\omega) be the heap torsor obtained from \mathcal{G}.

Theorem: If \mathcal{G}=(G,L,\Omega,\mho) is a one-sorted heap torsor, then \mathcal{G}^{++}=\mathcal{G}.

Proof: Suppose that \mathcal{G}^{+}=(G^{2}/\simeq,G,\omega) and \mathcal{G}^{++}=(G,L^{++},\Omega^{++},\mho^{++}).

Suppose that p,q\in G. Then \Omega(p,q,x)=\omega([p,q],x) for all x\in G. However, since \omega([p,q],q)=\Omega(p,q,q)=p, we know that \Omega^{++}(p,q,x)=\omega([p,q],x)=\Omega(p,q,x) for each x\in X.

Since the operations L^{++},\mho^{++} are definable as terms in (G,\Omega^{++}) in the same way that L,\mho are definable as terms in (G,\Omega), we know that L=L^{++},\mho=\mho^{++}, so \mathcal{G}=\mathcal{G}^{++}.

Q.E.D.

If \mathcal{X}=(K,X,F) is a heap torsor, then let \mathcal{X}^{+}=(X,L,\Omega,\mho). Let \mathcal{X}^{++}=(X^{2}/\simeq,X,\omega). Define a mapping v:X^{2}\rightarrow K by letting F(v(x,y),y)=x. If K,X are groups, and \iota:K\rightarrow X is a group isomorphism and F(k,x)=\iota(k)P(x), then v(x,y)=\iota^{-1}(xP(y)^{-1}). In particular, \ker(v)=\simeq. Therefore, define a mapping v^{\sharp}:X^{2}/\simeq\rightarrow K by letting v^{\sharp}([a,b])=v(a,b). Then the mapping v^{\sharp} is a bijection.

Proposition: \omega([a,b],x)=F(v^{\sharp}([a,b]),x) whenever a,b,x\in X.

Proof: Suppose a,b\in X. Let k be the element with F(k,b)=a. Then k=v(a,b)=v^{\sharp}([a,b]), and \omega([a,b],x)=\Omega(a,b,x)=F(k,x)=F(v^{\sharp}([a,b]),x).

Q.E.D.

Definability of cartesian product structure and S-boxes in SP-networks

In order to produce powerful measures of security for the block cipher round function F, let us assume that F is not just a heap torsor, but F is a substitution-permutation (SP) network. Under this assumption that F is an SP-network with reasonably secure S-boxes, nearly any sensible measure of security of F is actually definable from the torsor F.

Suppose that U_{0},\dots,U_{n-1},V_{0},\dots,V_{n-1} are groups. Let I_{i}:U_{i}\rightarrow V_{i} be a group isomorphism for 0\leq i<n. Let K=U_{0}\times\dots\times U_{n-1},X=V_{0}\times\dots\times V_{n-1}. Define a group isomorphism \iota:K\rightarrow X by letting \iota((u_{i})_{i=0}^{r-1})=(I_{i}(u_{i}))_{i=0}^{r-1}. Suppose that s_{i}:V\rightarrow V is a permutation for 0\leq i<n, and S:X\rightarrow X is the mapping defined by letting S((v_{i})_{i=0}^{n-1})=(s_{i}(v_{i}))_{i=0}^{n-1}. The mapping S is the S-box mapping in our block cipher.

Let \Gamma:X\rightarrow X be a heap homomorphism. The mapping \Gamma:X\rightarrow X is the permutation box map in the SP-network. Suppose that P=\Gamma\circ S.

Let \pi_{i}:X^{n}\rightarrow V_{i} be the projection mapping where \pi_{i}(x_{0},\dots,x_{n-1})=x_{i}. Let \simeq_{i} be the equivalence relation where x\simeq_{i}y if and only if \pi_{i}(x)=\pi_{i}(y). We shall now under various hypotheses and in various ways define the set of all equivalence relations \{\simeq_{0},\dots,\simeq_{n-1}\} from the structure (K,X,F).

Define an operation M:X^{3}\rightarrow X by letting M(x,y,z)=P^{-1}(L(P(x),P(y),P(z))) for each x,y,z\in X. Observe that the operation M is definable from the operations \Omega,\mho. Observe furthermore that M(x,y,z)=S^{-1}(L(S(x),S(y),S(z))) for each x,y,z\in X.

Let \mathcal{X}=(X,L,M). Let \mathcal{V}_{i}=(V_{i},L,M) where L is the heap operation on V_{i} and M is the operation on V_{i} defined by M(x,y,z)=s_{i}^{-1}(L(s_{i}(x)),L(s_{i}(y)),L(s_{i}(z))). Observe that \mathcal{X} is the direct product of the algebras \mathcal{X}_{0},\dots,\mathcal{X}_{n-1}. If we can establish that \mathcal{X}=\mathcal{X}_{0}\times\dots\times\mathcal{X}_{n-1} is the only factorization (up to the rearrangement of the factors) of \mathcal{X} as a direct product of directly irreducible factors, then can define our set of equivalence relations \{\simeq_{0},\dots,\simeq_{n-1}\} as the kernels of the projection mappings onto \mathcal{X}_{i}, so we shall now work towards proving that \mathcal{X}_{0}\times\dots\times\mathcal{X}_{n-1} is the unique factorization of \mathcal{X} as a direct product of directly irreducible algebras (under reasonable hypotheses about the mappings s_{0},\dots,s_{n-1}).

If \mathcal{Z}=(Z,L,M) is a structure such that L,M are two heap operations on Z, then we shall define subgroups H_{i}(\mathcal{Z}) of the group of all permutations of Z for i\in\{0,1,2,3\}.

Let H_{0}(\mathcal{Z}) be the group generated by the permutations of the form x\mapsto L(a,b,x) along with the permutations of the form x\mapsto M(a,b,x). Observe that H_{0}(\mathcal{X}) is generated by the permutations of the form F_{j}\circ F_{k}^{-1} along with the permutations of the form F_{j}^{-1}\circ F_{k}. Let H_{1}(\mathcal{Z}) be the group generated by permutations of the forms x\mapsto M(a,b,x),x\mapsto L(a,b,x),x\mapsto L(x,a,b),x\mapsto M(x,a,b).

Let Q be the group with presentation \langle l,m\mid l^{2}=m^{2}=1\rangle. In other words, Q is the infinite dihedral group. Q can also be thought of as the free product \mathbb{Z}_{2}*\mathbb{Z}_{2}. Let H^{+}_{2}(\mathcal{Z}) be the subgroup of \text{Sym}(Z)\times Q generated by H_{1}(\mathcal{Z})\times\{e\} along with the pairs (f,l) where there are a,b where f(x)=L(a,x,b) for all x\in Z and the pairs (g,m) where there are a,b with g(x)=M(a,x,b) for all x\in Z. Let H_{2}(\mathcal{Z}) be the group of all permutations f of Z where (f,e)\in H_{2}^{+}(\mathcal{Z}). Let H_{3}(\mathcal{Z}) be the group generated by the permutations of the form x\mapsto t(a_{1},\dots,a_{v},x) where a_{1},\dots,a_{v}\in Z and t is a term produced from the fundamental operations L,M.

We observe that for i\in\{0,1,2\}, the group H_{i}(\mathcal{X}) is isomorphic to a direct product H_{i}(\mathcal{X}_{0})\times\dots\times H_{i}(\mathcal{X}_{n-1}). Once we prove (using reasonable assumptions) that H_{i}(\mathcal{X}_{0})\times\dots\times H_{i}(\mathcal{X}_{n-1}) is the unique factorization of H_{i}(\mathcal{X}) into a direct product of directly indecomposable groups, we will be able to define the equivalence relations \simeq_{0},\dots,\simeq_{n-1}.

From the Krull-Schmidt theorem, we can conclude that for all factorizations of a group as a product of directly indecomposable members, the factors are unique up to reordering and isomorphism.

Theorem: (Krull-Schmidt) Suppose that P is a group that satisfies both the ascending and descending chain condition of normal subgroups. Suppose that P=P_{1}\times\dots\times P_{\alpha} and P=Q_{1}\times\dots\times Q_{\beta} are factorizations of P into indirectly indecomposable groups. Then \alpha=\beta and there is some permutation \rho:\{1,\dots,\alpha\}\rightarrow\{1,\dots,\beta\} where P_{i}\simeq Q_{\rho(i)} for 1\leq i\leq\alpha and where P=P_{1}\times\dots\times P_{\gamma}\times Q_{\rho(\gamma+1)}\times\dots\times Q_{\rho(\alpha)} whenever 1\leq\gamma<\alpha.

We say that a group C is strongly indecomposable if whenever A,B are subgroups of C with C=AB and where ab=ba whenever a\in A,b\in B, then A=C or B=C. Recall that the center of a group G is the subgroup Z(G)=\{g\in G\mid \forall h\in H,gh=hg\}, and that the group G is centerless if the center Z(G) is just \{e\}.

Proposition: A group C is strongly indecomposable and centerless if whenever A,B are subgroups of C with C=AB and where ab=ba whenever a\in A,b\in B, then |A|=1 or |B|=1.

Proof: \rightarrow Suppose that C is strongly indecomposable and centerless. Then whenever A,B are subgroups of C with C=AB and where ab=ba whenever a\in A,b\in B. Then either A=C or B=C. If we assume that A=C, then since ab=ba for a\in A,b\in B and since C is centerless, we conclude that |B|=1. For a similar reason, if B=C, then |A|=1.

\leftarrow. Observe that Z(C)C=C and if a\in Z(C), b\in C, then ab=ba. Therefore, we have |Z(C)|=1 or |C|=1. In either case, we have |Z(C)|=1, so C is centerless. Now assume that A,B are subgroups of C with AB=C and ab=ba for a\in A,b\in B. Then we have |A|=1 or |B|=1. If |A|=1, then C=AB=B, and if |B|=1, then C=AB=A. Q.E.D.

Lemma: Suppose that C is a strongly indecomposable centerless group. Then whenever A_{1},\dots,A_{r} are subgroups of C that generate C and where if a\in A_{i},b\in A_{j},i\neq j and ab=ba, then there is some i where if j\neq i, then |A_{j}|=1.

Proof: We shall prove this fact by induction on r. The case when r=1 is trivial. Now assume the induction hypothesis and that A_{1},\dots,A_{r} are subgroups of C where ab=ba for a\in A_{i},b\in A_{j},i\neq j and that G=A_{1}\dots A_{r}. Then let A=A_{1} and B=A_{2}\dots A_{r}. Then whenever a\in A,b\in B, we have ab=ba, and AB=C. Therefore, either |A|=1 or |B|=1. In the case that |B|=1, we have |A_{j}|=1 whenever j > 1. On the other hand, if |A|=1, then A_{2}\dots A_{r}=C, so by using the induction hypothesis, there is some i where if j\neq i and j>1, then |A_{j}|=1. Therefore, we have |A_{j}|=1 whenever 1\leq i\leq r and i\neq j. Q.E.D.

Lemma: Suppose that a finite group \Delta is an internal direct product of nontrivial subgroups \Delta_{1},\dots,\Delta_{n} and each \Delta_{i} is a strongly indecomposable centerless group. Then whenever \Delta is an internal direct product of nontrivial directly indecomposable subgroups \Delta^{\sharp}_{1},\dots,\Delta^{\sharp}_{m}, we have m=n, and there is a bijection \zeta:\{1,\dots,n\}\rightarrow\{1,\dots,n\} with \Delta_{i}=\Delta^{\sharp}_{\zeta(i)} for 1\leq i\leq n.

Proof: By the Krull-Schmidt theorem, we know that there exists an automorphism \phi:\Delta\rightarrow\Delta and a bijection \ell:\{1,\dots,n\}\rightarrow\{1,\dots,n\} such that \phi[\Delta_{i}]=\Delta^{\sharp}_{\ell(i)} for 1\leq i\leq n.

Now, let \iota_{i}:\Delta_{i}\rightarrow\Delta be the inclusion mapping, and let \pi_{j}:\Delta\rightarrow\Delta_{j} be the projection mapping whenever i,j\in\{1,\dots,n\}. Since each \Delta_{j} is generated by the set of subgroups \{\pi_{j}\phi\iota_{i}[\Delta_{i}]\mid 1\leq i\leq n\} and since if a\in\pi_{j}\phi\iota_{i_{1}}[\Delta_{i_{1}}],b\in\pi_{j}\phi\iota_{i_{2}}[\Delta_{i_{2}}], then ab=ba, we conclude by the above lemma that there is some function \rho:\{1,\dots,n\}\rightarrow\{1,\dots,n\} where if i\neq\rho(j), then |\pi_{j}\phi\iota_{i}[\Delta_{i}]|=1.

In particular, the mapping \pi_{j}\phi\iota_{\rho(j)}:\Delta_{\rho(j)}\rightarrow\Delta_{j} is a surjective mapping.

I now claim that the mapping \rho is surjective. Suppose that \rho is not surjective. Then if i is not in the image of \rho, then \pi_{j}\phi\iota_{i}(a)=e whenever a\in\Delta_{i},j\in\{1,\dots,n\}, and therefore, \phi\iota_{i}(a)=e, so a=e as well which is a contradiction, so we conclude that \rho is surjective. Since \rho is surjective, \rho must also be injective. Therefore, for each j, we have \phi[\Delta_{\rho(j)}]=\Delta_{j}. Therefore, for all i, we have \Delta^{\sharp}_{\ell(i)}=\phi[\Delta_{i}]=\Delta_{\rho^{-1}(i)}.

Q.E.D.

Proposition: Let i\in\{0,1,2\}. Suppose that for all j\in\{0,\dots,n-1\}, the group H_{i}(\mathcal{X}_{j}) is strongly indecomposable and centerless. Then the set of projections \{\simeq_{0},\dots,\simeq_{n-1}\} where \simeq_{j} is the kernel of the projection \pi_{j}:X\rightarrow V_{j} is definable in the structure (F,K,X).

Proof: The above lemma applies to the subgroups H_{i}(\mathcal{X}_{0}),\dots,H_{i}(\mathcal{X}_{n-1}) of the group H_{i}(\mathcal{X}), so up-to-reordering, H_{i}(\mathcal{X}_{0})\times\dots\times H_{i}(\mathcal{X}_{n-1}) is the only factorization of H_{i}(\mathcal{X}) into a direct product of directly indecomposable subgroups. For each j, let \hat{H}_{i,j} be the group generated by \bigcup_{k\neq j}H_{i}(\mathcal{X}_{k}). Then x\simeq_{j}y if and only if there exists some h\in\hat{H}_{i,j} with h(x)=y. Therefore, since \{\hat{H}_{i,0},\dots,\hat{H}_{i,n-1}\} is definable, the set \{\simeq_{0},\dots,\simeq_{n-1}\} is also definable. Q.E.D.

We observe that the above proposition applies to when there is some i\in\{0,1,2\} where H_{i}(\mathcal{X}_{j}) is the alternating or symmetric group for each j and where |\mathcal{X}_{j}|\geq 5 for all j. In particular, the above proposition applies when F is the AES round function since the group H_{i}(\mathcal{X}_{j}) is the alternating group for i\in\{0,1,2\} according to my previous post.

A universal algebraic approach

The equivalence relations \simeq_{0},\dots,\simeq_{n-1} are congruences on \mathcal{X}, so we shall now characterize the set \{\simeq_{0},\dots,\simeq_{n-1}\} based on the properties of the congruences \simeq_{0},\dots,\simeq_{n-1}.

We say that an algebra \mathcal{A} is congruence permutable if whenever \theta,\phi are congruences on \mathcal{A}, we have \theta\circ\phi=\phi\circ\theta. We say that a variety V is congruence permutable if every algebra in V is congruence permutable. We say that an algebra \mathcal{A} is congruence distributive if the lattice of congruences of \mathcal{A} is a distributive lattice. A variety V is congruence distributive if each algebra in V is congruence distributive. A variety V is said to be arithmetical if it is both congruence permutable and congruence distributive. If \mathcal{A} is an algebra, then we shall write V(\mathcal{A}) for the variety generated by \mathcal{A}.

A Mal’cev term is a ternary term t that satisfies the identity t(x,y,y)=t(y,y,x)=x. A majority term is a ternary term t that satisfies the identity t(y,x,x)=t(x,y,x)=t(x,x,y)=x. A 2/3-minority term is ternary term m that satisfies the identity m(y,x,x)=m(x,x,y)=m(y,x,y)=y.

Theorem: (Mal’cev) Let V be a variety. Then V is congruence permutable if and only if there exists a ternary term t that is a Mal’cev term for V.

Theorem: Let V be a variety. If V has a majority term, then V is congruence distributive.

Theorem: (Pixley) Let V be a variety. Then the following are equivalent:

  1. V is arithmetical.

2. V has a Mal’cev term and a majority term.

3. V has a 2/3 minority term.

For example, every heap operation is a Mal’cev term. Therefore, every variety that contains a heap operation is congruence permutable.

If L is a distributive lattice, then observe that the collection of all complemented elements of L is a complemented distributive lattice, and every complemented distributive lattice with a complementation operation is a Boolean algebra.

Proposition: Suppose that \mathcal{A} is a congruence distributive algebra and \mathcal{A}=\mathcal{A}_{0}\times\dots\times\mathcal{A}_{n-1}. Furthermore, suppose that for each i, the algebra \mathcal{A}_{i} has no non-trivial complemented congruence. Then the maximal elements in the Boolean algebra of complemented congruences in \mathcal{A} are the congruences \ker(\pi_{i}).

Corollary: If \mathcal{A}=\mathcal{A}_{0}\times\dots\times\mathcal{A}_{n-1}, no \mathcal{A}_{i} has a non-trivial complemented congruence, and there is a common majority term or a common 2/3 minority term for \mathcal{A}_{0},\dots,\mathcal{A}_{n-1}, then the set of equivalence relations \{\ker(\pi_{0}),\dots,\ker(\pi_{n-1})\} is definable in \mathcal{A}.

If \mathcal{A} is an algebra with underlying set A, then we shall say that \mathcal{A} is primal if it is finite and for each function f:A^{n}\rightarrow A with n\geq 1, there is a term t with f(a_{1},\dots,a_{n})=t^{\mathcal{A}}(a_{1},\dots,a_{n}) whenever a_{1},\dots,a_{n}\in A. For example, the 2 element Boolean algebra is primal. More generally, if p is a prime number, then the finite field F_{p} with operations +,\cdot,0,1 is primal.

If \mathcal{A} is an algebra with underlying set A, and B\subseteq A, then we shall let \mathcal{A}_{B} be the algebra \mathcal{A} where we add a nullary operation for each element a\in B. We say that the the algebra \mathcal{A} is functionally complete if it is finite and \mathcal{A}_{A} is primal. For example, every finite field is functionally complete.

Theorem: (Werner) Suppose that \mathcal{A} is a finite algebra with more than one element where V(\mathcal{A}) is congruence permutable. Then \mathcal{A} is functionally complete if and only if the lattice \text{Con}(\mathcal{A}^{2}) is a four element lattice.

Lemma: Suppose that \mathcal{A} is a functionally complete algebra with underlying set \mathcal{A}. Then for all M\geq 1, there is an N\geq M and an N-ary term t where if f:A^{M}\rightarrow A is a function, then there are a_{1},\dots,a_{N-M}\in A where if x_{1},\dots,x_{M}\in A, then f(x_{1},\dots,x_{M})=f(a_{1},\dots,a_{N-M},x_{1},\dots,x_{M}).

Proposition: (Simultaneous functional completeness) Suppose that \mathcal{A}_{0},\dots,\mathcal{A}_{n-1} are functionally complete algebras of the same type with underlying sets A_{0},\dots,A_{n-1}. Suppose that \mathcal{A}_{0},\dots,\mathcal{A}_{n-1} have a common heap operation L. Then whenever M\geq 1 and f_{i}:A_{i}^{M}\rightarrow A_{i} for 0\leq i<n, the function f_{0}\times\dots\times f_{n-1} is a polynomial function.

Proof outline: Select an element e\in\mathcal{A}_{0}\times\dots\times\mathcal{A}_{n-1} to be the basepoint. Then the group operation obtained by the heap operation L together with the basepoint e is a polynomial function.

There is some N\geq M and N-ary terms t_{0},\dots,t_{n-1} where for all i and f:A_{i}^{M}\rightarrow A_{i}, there are a_{1},\dots,a_{N-M}\in A_{i} where if x_{1},\dots,x_{M}\in A_{i}, then t_{i}(a_{1},\dots,a_{N-M},x_{1},\dots,x_{M})=f(x_{1},\dots,x_{M}).

Now let t be an M+(N-M)n-ary term defined by letting

t((a_{1,0},\dots,a_{N-M,0}),\dots,(a_{1,n-1},\dots,a_{N-M,n-1}),x_{1},\dots,x_{M})

=t_{0}(a_{1,0},\dots,a_{N-M,0},x_{1},\dots,x_{M})\dots t_{n-1}(a_{1,n-1},\dots,a_{N-M,n-1},x_{1},\dots,x_{M}).

Then for all i, there are (a_{1,0},\dots,a_{N-M,0}),\dots,(a_{1,n-1},\dots,a_{N-M,n-1}) where if x_{1},\dots,x_{M}\in A_{i}, then

t^{\mathcal{A}_{i}}((a_{1,0},\dots,a_{N-M,0}),\dots,(a_{1,n-1},\dots,a_{N-M,n-1}),x_{1},\dots,x_{M})=f_{i}(x_{1},\dots,x_{M}). Therefore, the function f_{0}\times\dots\times f_{n-1} can be represented by a polynomial function.

Q.E.D.

Proposition: Suppose that if 0\leq i<n, then |\mathcal{X}_{i}|>1 and the lattice \text{Con}(\mathcal{X}_{i}\times\mathcal{X}_{i}) has only four elements. Then:

  1. H_{3}(\mathcal{X}_{i})=\text{Sym}(V_{i}).

2. H_{3}(\mathcal{X})\simeq\text{Sym}(V_{0})\times\dots\times\text{Sym}(V_{n-1}) by the mapping (f_{0},\dots,f_{n-1})\mapsto f_{0}\times\dots\times f_{n-1}.

3. \{\simeq_{0},\dots,\simeq_{n-1}\} is definable from the underlying set X and the group H_{3}(\mathcal{X}) whenever |V_{i}|\geq 5 for 0\leq i<n.

4. The congruences on \mathcal{X} are simply the intersections of the congruences \simeq_{0},\dots,\simeq_{n-1}.

5. \{\simeq_{0},\dots,\simeq_{n-1}\} is definable from the lattice of congruence of \mathcal{X}.

Theorem: (A corollary to Jordan’s theorem) Suppose that X is a set and G is a transitive group of permutations of X. Then if some g\in G contains a cycle of prime length p with |X|/2<p\leq|X|-3, then X is either the symmetric group or the alternating group.

Proposition: Suppose that \mathcal{A} is a finite algebra with underlying set A that contains a heap operation. Suppose that |A|=n. If there exists a permutation f:A\rightarrow A representable by a term in \mathcal{A}_{A} that contains a cycle of prime length p where n/2<p\leq n-3, then \mathcal{A} is functionally complete.

Proof outline: To prove this result, one simply shows that there are only four congruences on \mathcal{A}\times\mathcal{A}, and as a consequence, \mathcal{A} is functionally complete by Werner’s theorem.

Projection pairs

Suppose that \mathcal{C} is a category that contains finite direct products. We say that a collection of objects (X_{0},\dots,X_{n-1}) is skew rigid for an object Y if whenever i\neq j and f:X_{i}\times X_{j}\rightarrow Y is a morphism, either there is some g:X_{i}\rightarrow Y where f=g\pi_{i} or there is some h:X_{j}\rightarrow Y where f=h\pi_{j}; here \pi_{i}:X_{i}\times X_{j}\rightarrow X_{i},\pi_{j}:X_{i}\times X_{j}\rightarrow X_{j} denote the projection mappings. We say that (X_{0},\dots,X_{n-1}) is skew rigid if (X_{0},\dots,X_{n-1}) is skew rigid for X_{k} for each k\in\{0,\dots,n-1\}.

Proposition: If (\mathcal{X}_{0},\dots,\mathcal{X}_{n-1}) is skew rigid, then whenever f:\mathcal{X}_{0}\times\dots\times\mathcal{X}_{n-1}\rightarrow\mathcal{X}_{j} is a homomorphism, there is some i and a morphism g:\mathcal{X}_{i}\rightarrow \mathcal{X}_{j} where f=g\pi_{i}.

Proof: Let F:\mathcal{X}_{0}\times\dots\times\mathcal{X}_{n-1}\rightarrow\mathcal{X}_{j} be the group homomorphism where there exists some r\in\mathcal{X}_{j} where f(\mathbf{x})=r\cdot F(\mathbf{x}) for all \mathbf{x}\in X. We only need to show that there is some i and a group homomorphism h:\mathcal{X}_{i}\rightarrow\mathcal{X}_{j} where F=h\pi_{i}.

We will prove that whenever F:\mathcal{X}_{0}\times\dots\times\mathcal{X}_{m-1}\rightarrow\mathcal{X}_{j} is a group homomorphism, there is some i and g:\mathcal{X}_{i}\rightarrow \mathcal{X}_{j} with F=g\pi_{i} by induction on m.

The result clearly holds for m=1, so assume the induction hypothesis and that m>1. Then let \iota:\mathcal{X}_{0}\times\dots\times\mathcal{X}_{m-2}\rightarrow\mathcal{X}_{0}\times\dots\times\mathcal{X}_{m-1} be the mapping such that \iota(x_{0},\dots,x_{m-2})=(x_{0},\dots,x_{m-2},e). Then F\circ \iota:X_{0}\times\dots\times\mathcal{X}_{m-2}\rightarrow \mathcal{X}_{j}, so there is some i\in\{0,\dots,m-2\} where F(x_{0},\dots,x_{m-2},e)=(F\circ\iota)(x_{0},\dots,x_{m-2})=\theta(x_{i}) for all x_{0},\dots,x_{m-2}.

For all \alpha, let \iota_{\alpha}:\mathcal{X}_{\alpha}\rightarrow\mathcal{X}_{0}\times\dots\times\mathcal{X}_{m-1} be the inclusion mapping. Define h:\mathcal{X}_{i}\times\mathcal{X}_{m-1}\rightarrow\mathcal{X}_{j} by letting h(x,y)=F(\iota_{i}(x)\iota_{m-1}(y)). Then since h is a group homomorphism, we know that there is a group homomorphism \theta where h(x,y)=\theta(x) for all x,y or h(x,y)=\theta(y) for all x,y. Observe that F(x_{0},\dots,x_{m-1})=h(x_{i},x_{m-1}), so either F(x_{0},\dots,x_{m-1})=h(x_{i},x_{m-1})=\theta(x_{i}) for all x_{0},\dots,x_{m-1} or F(x_{0},\dots,x_{m-1})=h(x_{i},x_{m-1})=\theta(x_{m-1}) for all x_{0},\dots,x_{m-1}.

Q.E.D.

Proposition: Suppose that \mathcal{X}_{0},\dots,\mathcal{X}_{n-1} is skew rigid. Then whenever \phi:\mathcal{X}\rightarrow\mathcal{X} is an endomorphism, there exists some function \rho:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\} along with homomorphisms \theta_{i}:\mathcal{X}_{\rho(i)}\rightarrow\mathcal{X}_{i} for 0\leq i<n where \phi(x_{0},\dots,x_{n-1})=(\theta_{0}(x_{\rho(0)}),\dots,\theta_{n-1}(x_{\rho(n-1)})) whenever (x_{0},\dots,x_{n-1})\in\mathcal{X}.

Let \mathcal{Z} be a heap. We say that a heap endomorphism F:\mathcal{Z}\rightarrow\mathcal{Z} is a retraction if F\circ F=F.

Proposition: Let \mathcal{Z} be a group. Suppose that F:\mathcal{Z}\rightarrow\mathcal{Z} is a heap endomorphism. Then let f:\mathcal{Z}\rightarrow\mathcal{Z} be the group endomorphism, and let s\in\mathcal{Z} be the element where F(x)=s\cdot f(x) for all x\in\mathcal{Z}. Then F is a retraction if and only if f is a retraction, and f(s)=e.

Proof: \leftarrow. We have (F\circ F)(x)=s\cdot f(F(x))=s\cdot f(s\cdot f(x))

=s\cdot f(s)\cdot f(f(x))=s\cdot f(f(x))=s\cdot f(x)=F(x).

\rightarrow. We have F(e)=s\cdot f(e)=s.

We have F(e)=F(F(e))=F(s f(e))=F(s)=s\cdot f(s). Therefore, f(s)=e.

Now, F(x)=s\cdot f(x), and F(F(x))=F(s\cdot f(x))=s\cdot f(s\cdot f(x))=s\cdot f(s)\cdot f(f(x))=s\cdot f(f(x)). Therefore, since s\cdot f(x)=F(x)=F(F(x))=s\cdot f(f(x)), we conclude that f(x)=f(f(x)).

Q.E.D.

We say that two heap retractions f,g:\mathcal{Z}\rightarrow\mathcal{Z} are complementary projections if there is some a\in\mathcal{Z} with a=f(a)=g(a) and where x=L(f(x),a,g(x))=L(g(x),a,f(x)) for all x\in\mathcal{Z}.

For example, the mappings f,g:\mathcal{X}_{0}\times\mathcal{X}_{1}\rightarrow \mathcal{X}_{0}\times\mathcal{X}_{1} defined by letting f(x,y)=(x,b),g(x,y)=(a,y) are complementary heap projections, and we observe that every pair of complementary heap projections is of this form.

Observation: Suppose \mathcal{Z} is a heap and f,g:\mathcal{Z}\rightarrow\mathcal{Z} are complementary projections where a=F(a)=G(a) and x=L(f(x),a,g(x))=L(g(x),a,f(x)). Then

  1. If we set a to be the identity of \mathcal{Z}, then the heap homomorphisms f,g are actually group homomorphisms.

2. a=f(g(x))=g(f(x)) for all x\in\mathcal{Z}.

3. The identity a is the unique element with a=f(a)=g(a).

4. The homomorphism \phi:\mathcal{Z}\rightarrow f[\mathcal{Z}]\times g[\mathcal{Z}] defined by letting \phi(x)=(f(x),g(x)) is a bijection. Furthermore, If we define mappings f^{\sharp},g^{\sharp}:f[\mathcal{Z}]\times g[\mathcal{Z}]\rightarrow f[\mathcal{Z}]\times g[\mathcal{Z}] by letting f^{\sharp}(x,y)=(x,a),g^{\sharp}(x,y)=(a,y), then f^{\sharp}\circ\phi=\phi\circ f,g^{\sharp}\circ \phi=\phi\circ g.

Proposition: Suppose that \mathcal{X}_{0},\dots,\mathcal{X}_{n-1} is skew rigid and each \mathcal{X}_{i} is directly indecomposable. Then whenever f,g:\mathcal{X}\rightarrow\mathcal{X} are complementary projections with f(g(x))=(a_{0},\dots,a_{n-1}) for all x, there is some A\subseteq\{0,\dots,n-1\} where f(x_{0},\dots,x_{n-1})=(y_{0},\dots,y_{n-1}) precisely when y_{i}=x_{i} for i\in A and y_{i}=a_{i} for i\not\in A. In particular, the set \{\simeq_{0},\dots,\simeq_{n-1}\} is definable in \mathcal{X}.

Proof: Suppose that 0\leq i < n. Then \pi_{i}\circ f,\pi_{i}\circ g:\mathcal{X}\rightarrow\mathcal{X}_{i} are homomorphisms. Therefore, there are homomorphisms u:\mathcal{X}_{j}\rightarrow\mathcal{X}_{i},v:\mathcal{X}_{k}\rightarrow\mathcal{X}_{i} with \pi_{i}\circ f=u\circ\pi_{j},\pi_{i}\circ g=v\circ \pi_{k} where if u is constant, then i=j and where if v is constant, then i=k. Observe that \pi_{i}(x)=(\pi_{i}\circ f)(x)(\pi_{i}\circ g)(x)=(u\circ\pi_{j}(x))((v\circ\pi_{k})(x)). In other words, x_{i}=u(x_{j})v(x_{k}) whenever x=(x_{0},\dots,x_{n-1})\in\mathcal{X}.

I now claim that i=j=k.

It is impossible to have i\neq j and i\neq k since that would mean that x_{i}=u(x_{j})v(x_{k}) which is impossible since that would mean that x_{i} is a function of x_{j},x_{k}.

If i=j,i\neq k, then we would have x_{i}=u(x_{j})v(x_{k}), so u(x_{i})^{-1}x_{i}=v(x_{k}) which is not possible since the only way for v(x_{k}) to be dependent solely on u(x_{i})^{-1}x_{i} would be if v were a constant function. Similarly, if i=k,j\neq i, then x_{i}=u(x_{j})v(x_{k}), so we would have u(x_{j})=x_{i}v(x_{i})^{-1} which is only possible if u is a constant function. Therefore, the only possibility is to have i=j=k.

We conclude that there are homomorphisms u_{i},v_{i}:\mathcal{X}_{i}\rightarrow\mathcal{X}_{i} where f(x_{0},\dots,x_{n-1})=(u_{0}(x_{0}),\dots,u_{n-1}(x_{n-1})) and g(x_{0},\dots,x_{n-1})=(v_{0}(x_{0}),\dots,v_{n-1}(x_{n-1})) whenever x=(x_{0},\dots,x_{n-1})\in\mathcal{X}.

We observe that u_{i}\circ u_{i}=u_{i},v_{i}\circ v_{i}=v_{i} and u_{i}(v_{i}(x_{i}))=v_{i}(u_{i}(x_{i}))=a_{i} and u_{i}(x)v_{i}(x_{i})=x_{i} for each x_{i}.

We conclude that the operators u_{i},v_{i} are complementary projections, so since each \mathcal{X}_{i} is directly indecomposable, for each i, either u_{i} is the identity function and v_{i} is constant or v_{i} is the identity function and u_{i} is constant.

Q.E.D.

We observe that the various conditions that allow us to define \{\simeq_{0},\dots,\simeq_{n-1}\} from the mapping F are conditions that the S-box mapping should satisfy in order for one to consider the SP-network F to be secure. Furthermore, for every SP-network F, the lattice of congruences of \mathcal{X} should be generated by \{\simeq_{0},\dots,\simeq_{n-1}\} in order for the block cipher to be considered secure, but whenever the lattice of congruences is generated by \{\simeq_{0},\dots,\simeq_{n-1}\}, the set \{\simeq_{0},\dots,\simeq_{n-1}\} is definable.

Some invariants of block cipher round functions

For the remainder of this post, we shall assume that the mapping F is an SP-network and that the set \{\simeq_{0},\dots,\simeq_{n-1}\} is definable from F. From the definability of \{\simeq_{0},\dots,\simeq_{n-1}\}, we shall be able to recover most of the important information about the non-linear layer S as well as the linear later \Gamma.

Let H^{+} be the group of all permutations f of X that can be factored as f_{0}\times\dots\times f_{n-1} where f_{i}:V_{i}\rightarrow V_{i} whenever 0\leq i<n.

We say that a pair (\Delta,T) is an SP-factorization of F if \Delta:X\rightarrow X is a heap automorphism, T\in H^{+}, and F_{k}=\Delta\circ T for some k\in K. If (\Delta,T) is an SP-factorization of F, then we shall say that \Delta is an affinization of F and T is a boxification of F.

Observation:

1. The SP-factorizations of F are precisely the pairs of the form (\iota_{k}\Gamma\circ R^{-1},R\circ S) for some k\in K where \iota_{k} is the mapping where \iota_{k}(x)=\iota(k)x and R\in H^{+} where R is a heap homomorphism. The k,R are uniquely determined by the SP-factorization.

2. A function \Delta is an affinization of F if and only if \Delta=\Gamma\circ R for some heap automorphism R\in H^{+}.

3. A function T is a boxification of F if and only if T=R\circ S for some heap automorphism R\in H^{+}.

While the mappings \Gamma,S are generally not definable in (K,X,F), the set of all SP-factorizations of F is definable in (K,X,F). Furthermore, an isomorphic copy of (K,X,F) can be obtained from the set of all SP-factorizations of F along with the heap operation on X.

Box invariant functions

We say that a function M is heap (group) box invariant if whenever G is a heap (group) that can be written as an internal direct product of G_{0},\dots,G_{n-1} and \simeq_{i}=\ker(\pi_{i}) for 0\leq i<n, and \Delta_{0},\Delta_{1}:G\rightarrow G are heap (group) automorphisms and \Delta_{1}=\Delta_{0}\circ(f_{0}\times\dots\times f_{n-1}) where f_{i}:G_{i}\rightarrow G_{i} is a heap (group) automorphism for 0\leq i<n, then M(G,\{\simeq_{0},\dots,\simeq_{n-1}\},\Delta_{0}) =M(G,\{\simeq_{0},\dots,\simeq_{n-1}\},\Delta_{1}).

The heap box invariant functions can be put into a one-to-one correspondence with the group box invariant functions.

If M is heap box invariant and definable, then one can define a block cipher round function invariant M^{\sharp} by defining M^{\sharp}(K,X,F)=M(X,\{\simeq_{0},\dots,\simeq_{n-1}\},\Delta) where \Delta is some affinization of F (of course, this function M^{\sharp} depends on a suitable way of defining \{\simeq_{0},\dots,\simeq_{n-1}\} from (K,X,F)).

Example 0: From a definable function M^{-} with range \mathbb{R}, one can produce a heap (group) box invariant function M by letting M(G,\{\sigma_{0},\dots,\sigma_{n-1}\},\Delta)=E[M^{-}(G,\{\sigma_{0},\dots,\sigma_{n-1}\},\Delta\circ(f_{0}\times\dots\times f_{n-1})] where f_{i}:G_{i}\rightarrow G_{i} is a uniform randomly selected heap (group) automorphism for each i and (f_{0},\dots,f_{n-1}) are independent.

Example 1: Let p be a prime number. Suppose that G=G_{0}\times\dots\times G_{n-1} and G_{i} is a vector space over the field F_{p}. For each i, let \iota_{i}:G_{i}\rightarrow G,\pi_{j}:G\rightarrow G_{j} be the inclusion and projection mappings. Then let M(G,\{\simeq_{0},\dots,\simeq_{n-1}\},\Gamma)=\sum_{i,j}Rank(\pi_{j}\Gamma\iota_{i}). Then M is a group box invariant. A higher value of M(G,\{\simeq_{0},\dots,\simeq_{n-1}\},\Gamma) indicates a greater level of cryptographic security.

Example 2: Define the Hamming distance d and hamming weight w on G by letting d(x,y) be the cardinality of the set of all i where x\not\simeq_{i}y and where w(x)=d(x,e) (whenever G is a group and not just a heap). Define the branch number of \Delta to be \min_{a\neq b}d(a,b)+d(\Delta(a),\Delta(b)). Observe, also that if \Delta is a group automorphism, then the branch number of \Delta is simply \min_{a\neq e}w(a)+w(\Delta(a)). The branch number of a heap homomorphism measures the amount of diffusion in that heap homomorphism. A higher branch number indicates a greater level of cryptographic security.

Affine invariant functions

A function M is said to be affine invariant if whenever G_{1},H_{1},G_{2},H_{2} are groups, and \phi:G_{2}\rightarrow G_{1},\theta:H_{1}\rightarrow H_{2} are heap isomorphisms, and F:G_{1}\rightarrow H_{1} is a function, then M(F)=M(\theta\circ F\circ \phi).

Set (x_{0},\dots,x_{n-1})\cong(y_{0},\dots,y_{n-1}) if and only if there is a permutation \rho of \{0,\dots,n-1\} such that y_{i}=x_{\rho(i)} for each i, then let [x_{0},\dots,x_{n-1}] denote the equivalence class containing (x_{0},\dots,x_{n-1}) with respect to \cong. It is not too hard to show that if (\Delta,T) is an SP-factorization, and T=t_{0}\times\dots\times t_{n-1}, then the quantity [M(s_{0}),\dots,M(s_{n-1})]= [M(t_{0}),\dots,M(t_{n-1})], so [M(t_{0}),\dots,M(t_{n-1})] does not depend on the SP-factorization that we choose. Therefore [M(s_{0}),\dots,M(s_{n-1})] is also a block cipher round function invariant.

Let us now look at a few examples of affine invariant functions.

Example 0: Let f:F_{2}^{n}\rightarrow F_{2} be a function. Then there exists a unique collection of constants (\alpha_{S})_{S\subseteq\{0,\dots,n-1\}} such that f(x_{0},\dots,x_{n-1})=\sum_{S\subseteq\{0,\dots,n-1\}}\alpha_{S}\prod_{i\in S}x_{i}. One can compute the constants \alpha_{S} using Mobius inversion. We say that \sum_{S\subseteq\{0,\dots,n-1\}}\alpha_{S}\prod_{i\in S}x_{i} is said to be the Zhegalkin polynomial or algebraic normal form of the function f. The degree of the Zhegalkin polynomial of f is known as the algebraic degree of the function f.

The algebraic degree of a function f:F_{2}^{m}\rightarrow F_{2}^{n} is simply the maximum value of \pi_{i}\circ f where \pi_{i}:F_{2}^{n}\rightarrow F_{2} is a projection function.

Example 1: Suppose that G,H are finite groups and \Gamma:G\rightarrow H is a function. Then whenever a\in G,b\in H, define \delta_{\Gamma}(a,b)=|\{x\in G\mid \Gamma(ax)\Gamma(x)^{-1}=b\}|. Then the uniformity of \Gamma is defined to be \max_{a\in G,a\neq e,b\in H}\delta_{\Gamma}(a,b). The uniformity of a function is a measure of the non-linearity of that function.

If F:A\rightarrow B is a function, then define Nb_{F}=\sum_{b\in B}(|F^{-1}[\{b\}]|-\frac{|A|}{|B|})^{2}=(\sum_{b\in B}|F^{-1}[\{b\}]|^{2})-\frac{|A|^{2}}{|B|}. The quantity Nb_{F} is known as the non-balancedness of the function F and Nb_{F} is proportional to the variance |F^{-1}[\{b\}]|. Suppose that A,B are abelian groups. Then define NB_{F}=\sum_{0\neq a\in A}Nb_{D_{a}F}.

If G,H are finite groups, and \Gamma:G\rightarrow H is a function, then let N_{F}=\min_{\ell\in L}d(F,\ell) where d refers to the Hamming distance and L is the set of all heap homomorphisms from G to H.

The algebraic degree, the quantity Nb_{F}, the uniformity, and the quantity N_{F} are all affine invariant.

Conclusion

From this discussion, we can conclude that for at least some block ciphers (including AES), many good measures of security of the block cipher are actually invariant under isomorphism. We can also conclude that block ciphers like AES are designed so that they can be easily analyzed mathematically. I expect that in the future, cryptographers will use block cipher round function invariants in order to objectively and automatically evaluate the security level of block ciphers in the future (we will eventually need to replace AES for another block cipher that is better adapted to reversible computing hardware).

Future posts

In future posts, we shall go over block ciphers that can be put into a nearly unique normal form. Such a normal form allows us to compute many block cipher round function invariants that will allow us to rate the security levels of these block ciphers. In future posts, we shall also discuss invariants consisting of spectral radii of matrices obtained from F. These spectral radii invariants apply to all block ciphers, and it is not too hard to compute these spectral radii in the extreme case when both K and X are very small.

References

  1. [Textbook for universal algebra] “A course in universal algebra”, by Stanley Burris and H.P. Sankappanavar, Graduate Texts in Mathematics #78, Springer-Verlag, New York-Berlin, 1981.
  2. [Textbook for algebra including group theory] Hungerford, T.W. (1974) Algebra. Springer-Verlag, New York.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: