# 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\pmod 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.

-