# Can a commutative block cipher be indistinguishable from a random one, assuming a random permutation of keyspace?

Define a commutative block cipher with keyspace the finite set $K$, and message space the finite set $S$, to be an application \begin{align} E:K\times S&\mapsto S\\ (k,x)&\mapsto E(k,x)\text{ also noted }E_k(x)\\ \text{such that }&\forall k\in K,\forall x\in S, \forall y\in S,\text{ if }E(k,x)=E(k,y)\text{ then }x=y\\ \text{and }&\forall k\in K,\forall k'\in K, \forall x\in S,E(k',E(k,x))=E(k,E(k',x))\\ \end{align} Note: The last property is what makes the block cipher commutative. The rest is the standard definition of a block cipher: the application $E_k$ from $S$ to $S$ is injective, implying that it is a permutation of $S$ given this is a finite set; $E_k$ is encryption with key $k$, ${E_k}^{-1}$ is decryption with key $k$.

Informal question: Can we make a practical commutative block cipher which does not exhibit other distinguishing properties that a random commutative block cipher is not expected to have? In other words, something that's to commutative block ciphers what AES is to block ciphers (without perhaps the performance)?

Motivation: the Pohlig-Hellman Exponentiation Cipher $(k,x)\mapsto E_k(x)=x^k\bmod p$ [with public prime $p$, keyspace $K$ the integers $k$ with $0<k<p$ and $\gcd(k,p-1)=1$, message space $S$ the integers $x$ with $0\le x<p$] is a commutative block cipher. It is conjectured secure under unknown random key and known random plaintext, but has other properties beyond commutativity:

• The multiplicative property: $\forall k\in K,\forall x\in S, \forall y\in S, E_k(x\cdot y\bmod p)=E_k(x)\cdot E_k(y)\bmod p$
• Three fixed points: $\forall x\in\{0,1,p-1\},\forall k\in K,E_k(x)=x$
• A symmetry in the message space: $\forall x\in \mathbb Z_p,\forall k\in K,E_k(p-x\bmod p)=\big(p-E_k(x)\big)\bmod p$
• The set of permutations $E_k$ forms a group under composition, isomorphic to $K$ under multiplication modulo $p-1$, with $\forall k\in K,\forall k'\in K, E_k\circ E_{k'}=E_{k\cdot k'\bmod(p-1)}$; which in turn allows related-key attacks.

We can remove the later three properties, see the variant here. But for the multiplicative property, the best I manage to do while keeping commutativity is a poor camouflage, by inserting some practical reversible public permutation of the message space before applying the cipher, and undoing it after; but that still allows an adversary to observe (and perhaps take advantage of) the multiplicative property under a chosen-message attack.

Tentative formalization

Exhibit a commutative block cipher $E$ (or prove there can't be one)

• with a concise description independent of the sizes of $K$ and $S$, while allowing these to grow without bounds (or at least big enough for practical purposes)
• practical, that is allowing encryption and decryption in time and space polynomial in the logarithms of the sizes of $K$ and $S$;
• conjectured secure in the sense that (knowing the full description of $E$) we can't exhibit (or better, we can show there can't be under plausible assumptions) a polynomial algorithm that wins the following game with some constant positive advantage when the sizes of $K$ and $S$ grow:
• an omnipotent referee randomly choses either
1. a random permutation $P$ of the keyspace $K$
2. a random commutative block cipher $F: K\times S\mapsto S$
• the algorithm is run and given the possibility to (iteratively) make a polynomial number of queries for chosen $(k,x)\in K\times S$ and obtain $(y,z)\in S\times S$ verifying, according to said choice
1. the relations $E(P(k),x)=y$ and $E(P(k),z)=x$
2. the relations $F(k,x)=y$ and $F(k,z)=x$
• the algorithm must announce the referee's choice.

Note 1: When $E$ is any practical variant of the Pohlig-Hellman Exponentiation Cipher that I can imagine, the game can be won with overwhelming advantage due to the underlying multiplicative property.

Note 2: Without the practical requirement, we could make a variant of the Pohlig-Hellman Exponentiation Cipher that pass the test as far as I see, by inserting some secure one-way permutation of the message space on input, and the reverse permutation on output; however neither encryption nor decryption is practical.

Note 3: The definition of security given does not cover related-key attacks, and weak keys; however, given an hypothetical commutative block cipher passing the test, we can strengthen it w.r.t. such threats while keeping commutativity, by inserting on the key input an efficient public pseudo-random injection from a (possibly reduced) key space to the original key space.

1. there is no commutative block cipher that could pass your test, and
2. in any case, indistinguishability from a random commutative block cipher is probably not a good measure of cryptographic quality, since it turns out that a random commutative block cipher is, with overwhelming likelihood, a pretty useless thing for crypto.

Since this is an SE answer and not a research paper, the arguments I present below to support these claims are sketchy at best. Nonetheless, I at least find them personally convincing.

First, let me start by noting that the trick used in poncho's answer to your earlier question can be adapted to almost prove claim 1 above, except for a few minor conjectural gaps that I have not managed to rigorously bridge.

Specifically, assume that there exists a key $k \in K$ and a block $x \in S$ such that $E(k,x) \ne x$. (If no such $k$ and $x$ exist, then $E$ is the trivial "null cipher", and should be easily distinguishable from a random commutative block cipher — although, as noted below, perhaps not quite as easily as one might expect.) Let the adversary:

1. compute $y = E(k,x)$, and query the oracle for $z = F(k,y)$;
2. query the oracle for $y' = F(k,x)$ and compute $z' = E(k,y')$; and
3. output "1" if $z = z'$, and "2" otherwise.

Clearly, in case 1, where $F$ is $E$ with a shuffled keyspace: $$z = E(P(k),E(k,x)) = E(k,E(P(k),x)) = z',$$ and so in this case the adversary will always guess correctly.

In case 2, where $F$ is a random commutative block cipher, the adversary will only guess wrong if either:

• a) $x$ and $y$ are both fixed points of the random permutation $F(k,\cdot)$, or
• b) neither $x$ nor $y$ is a fixed point of $F(k,\cdot)$ and it just happens that $F(k,y)$ is the image of $F(k,x)$ under $E(k,\cdot)$.

Both of these possibilities seem intuitively unlikely, although I will argue below that, for random commutative block ciphers, (a) may actually happen with a non-negligible probability. Still, as long as the probability that neither (a) nor (b) occurs is not negligible, the adversary described above will return the correct result with a non-negligible advantage. I have not proven this, but I would be quite surprised if it wasn't true.

Filling out the gaps in the proof sketch above would seem to require a closer examination of what a "random commutative block cipher" actually looks like. Such an examination turns out to yield some rather unexpected results, at least when contrasted with the behavior of random non-commutative block ciphers.

In particular, let me first state a few rather surprising conclusions, which I will attempt to justify below:

• For large $K$ and $S$, the probability that $F(k,x) = x$ for a random commutative block cipher $F: K \times S \to S$ is approximately $1/3$.
• Let $\mathcal{G}_F$ denote the (Abelian) group of permutations of $S$ generated by the permutations $\{x \mapsto F(k,x): k \in K\}$, and let $\mathcal{G}_F(x) \subset S$ denote the orbit of $x$ under $\mathcal{G}_F$. For reasonably large $K$ and $S$, the orbit $\mathcal{G}_F(x)$ of most points $x \in S$ should consist of 2 to 4 points, with 3-point orbits becoming the norm as $|K|$ grows.

To show how I came up with these conclusions, let me start by noting that, for any fixed message space $S$, we can iteratively construct all commutative $n$-key block ciphers over $S$.

Specifically, let us WLOG fix the keyspace $K_n = \{1,2,\dots,n\}$, and represent each block cipher $F: K_n \times S \to S$ by the corresponding sequence of permutations $f = (f_1, f_2, \dots, f_n)$, where $f_i = F(i,\cdot)$. Let $\mathcal{C}_n$ denote the set of such sequences corresponding to $n$-key commutative block ciphers, i.e. $n$-element sequences of mutually commuting permutations of $S$.

Clearly, $\mathcal{C}_1$ consists of the one-element sequences $(p)$ for every permutation $p$ of $S$. To construct $\mathcal{C}_n$ for $n > 1$, we simply take each sequence $(f_1, \dots, f_{n-1}) \in \mathcal{C}_{n-1}$ and append to it every possible permutation $f_n$ of $S$ that commutes with all the permutations already in it:

$$\mathcal{C}_n = \{ (f_1,\dots,f_n) \mid (f_1,\dots,f_{n-1}) \in \mathcal{C}_{n-1} \land \forall 1 \le i < n: f_i \circ f_n = f_n \circ f_i \}.$$

In particular, this construction should yield a recipe for reasonably efficient Monte Carlo importance sampling of the set of commutative block ciphers over any key and message space: simply start with a random permutation of $S$ and repeatedly append a new random permutation chosen so as to commute with all the previously chosen permutations, while also multiplying the relative weight of the sample by the fraction of all permutations eligible to be so chosen. As far as I can tell, it should be possible to select (and count) these eligible permutations efficiently by keeping track of the orbits on $S$ induced by the current set of permutations, and of the algebraic relations the hold between the permutations within each orbit, as described below.

I have not yet actually implemented the sampling algorithm described above. However, simply considering the process in an abstract way yields some useful insights.

First of all, we can consider the cycle structure of the first permutation $f_1$, and note that it imposes significant constraints on the second permutation $f_2$: namely, $f_2$ must map each cycle of $f_1$ either onto itself, or onto another cycle of the same size (which must then be mapped onto either the original cycle or yet another cycle of the same size, and so on). Furthermore, for each cycle of $f_1$, once we choose the image of one element of the cycle under $f_2$, this uniquely determines the corresponding images of all other elements of the cycle.

Thus, while for $f_1$ we have all $|S|!$ possible permutations to choose from, only $\prod_{k=1}^{|S|} k^{n_k}\, n_k!$ of those are eligible to be chosen as $f_2$, where $n_k$ denotes the number of $k$-element cycles of $f_1$. (The formula $k^{n_k}\, n_k!$ comes from the observation that, first, we have $n_k!$ ways to map the $n_k$ cycles onto each other, and then $k$ independent choices for how much to shift each of the $n_k$ cycles.)

For $f_3$ and higher, similar constraints apply, but with a further restriction: while we may always choose to map each orbit of the subgroup generated by $f_1$ and $f_2$ onto itself (and, again, choosing the image of any element of the orbit is enough to fix the images of all elements in the same orbit), we can only map two (or more) previously separate orbits onto each other if they are compatible, in the sense that the same algebraic relations between $f_1$ and $f_2$ must hold within each orbit. That is to say, if $x$ and $y$ are arbitrary elements of the two respective orbits, and if $f_1^{(a)}(x) = f_2^{(b)}(x)$ for some integers $a$ and $b$, then the same relation must also hold for $y$.

Now, an important (but, alas, not 100% rigorous) observation is that, as we keep adding new random permutations to the sequence $f$, its orbit structure will, with high probability, tend to very quickly (I suspect this happens in $O(\log |S|)$ steps on average) become "locked" so that no two orbits remain compatible with each other, either because any formerly compatible orbits get merged, or because they become incompatible due to new relations between the added permutations.

Once this happens, it is no longer possible for any further permutation in the sequence to connect two orbits, and so the number of eligible new permutations becomes fixed at $R = \prod_{k=1}^{|S|} k^{n_k}$, where, again, $n_k$ is the number of $k$-element orbits of the cipher. Thus, once the orbit structure of a particular cipher becomes locked in this way, increasing $|K|$ by one simply splits this cipher into $R$ new variants, each with the same orbits (and thus the same splitting factor $R$) as their parent cipher had.

Thus, once we're past the initial steps, and the orbit structure of most ciphers has become locked, $\mathcal{C}_n(S)$ is effectively divided into "families" of ciphers with the same $R$ factor, with the size of each family growing in proportion to $R^n$.

The outcome should be obvious to anyone familiar with replicator dynamics in ecology: as $n$ grows, the "population" of ciphers becomes dominated by the family with the highest exponential growth rate $R$.

What does this family look like? First, as far as the size of the message space allows, all its orbits should have the same size, since otherwise we could increase $R$ by moving points from larger orbits into smaller ones. Now, if all the orbits have size $k$, then $R = k^{n/k}$; maximizing this is equivalent to maximizing $\log R = \frac nk \log k$. Dropping the constant factor $n$ leaves us with $\frac{\log k}{k}$, an expression that, for real $k > 0$, attains its maximum at $k = e$.

Over the positive integers, the maximum is attained at $k = 3 \approx e$, with $k = 2$ and $k = 4$ tied for second place. Thus, for a given $|S|$, one would expect the maximum growth factor $R$ to be attained by ciphers that divide $S$ into 3-element orbits, possibly with a single 2- or 4-element orbit if $|S|$ is not a multiple of 3.

Since all the permutations in a cipher must commute with each other, each permutation in the cipher must act one any given 3-element orbit by shifting the elements of the orbit forward by 0, 1 or 2 places, each with equal probability. In particular, this implies that, for any given element of $S$, a randomly chosen permutation in a maximal-$R$ cipher will leave that element untouched with probability approximately $1/3$.

Obviously, this is very much unlike the behavior of random block ciphers in general, and it's quite remarkable that the imposition of commutativity should have such a drastic effect. Yet, even though there are surely gaps and inaccuracies in my reasoning above, I don't believe that any of them should significantly affect the main conclusions.

A natural verification step would be to test these conclusions computationally, either using stochastic sampling as I suggest above, or by simply enumerating all the possible commutative block ciphers (modulo obvious symmetries to speed up the search) by brute force over sufficiently small key and message spaces to keep this feasible.

In any case, assuming I haven't made any really silly mistakes in what I've written above, this should clearly suggest that, insofar there may be any commutative block ciphers with useful cryptographic properties, they almost certainly will not look anything like uniformly random families of mutually commutative permutations.