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:

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:

the mapping $\theta$ is a heap action.
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$ .
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.

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:

$\Omega(a,b,\mho(b,a,x))=\mho(a,b,\Omega(b,a,x))=x$ and
$\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:

Suppose that $\mathcal{G}$ is a heap with permutation coset. Then $\mathcal{G}^{*}$ is a one-sorted heap torsor.
Suppose that $\mathcal{G}$ is a one-sorted heap torsor. Then $\mathcal{G}^{*}$ is a heap with permutation coset.
If $\mathcal{G}$ is a heap with permutation coset, then $\mathcal{G}=\mathcal{G}^{**}$ .
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:

$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:

$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

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

[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.
[Textbook for algebra including group theory] Hungerford, T.W. (1974) Algebra. Springer-Verlag, New York.

Defining heap operations and other structure in a block cipher

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

Some invariants of block cipher round functions

References

Share this:

Like this:

Leave a Reply Cancel reply