# Can a commutative block cipher be indistinguishable from a random permutation, for fixed key?

Define a commutative block cipher with keyspace the finite set $K$, and data 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 first property states that the application $E_k$ from $S$ to $S$ is injective, implying that it is a permutation of $S$ given this is a finite set, and that's standard for a cipher; the second property is what makes the cipher commutative.

Question: what commutative block cipher do we have that is

• conjectured computationally indistinguishable with effort polynomial in $\log(|K|)$ from a random permutation for unknown random fixed key $k$, assuming the attacker can obtain ciphertext for iteratively chosen plaintext;
• efficiently computable, at least in the encryption direction (and preferably for decryption as well)?

If there was none: do we have some proof this can't be achieved?

In this answer, I explored a variant of the Pohlig-Hellman Exponentiation Cipher $(k,x)\mapsto E_k(x)=x^k\pmod p$ but stalled with something that remains distinguishable from a random permutation due to a multiplicative property similar to that of naked RSA: $\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$.

Update: the question as is was perfectly answered by poncho. Here is take two.

-
There could conceivably be a commutative block cipher whose outputs for a given key on an entry-wise unpredictable list of inputs are indistinguishable from being independently-and-uniformly distributed. $\hspace{.42 in}$ – Ricky Demer Mar 31 '14 at 15:01

It can't be achieved under the assumptions you are making, because the attacker can distinguish it by selecting an arbitrary $k'$, and checking if $E(k')$ commutes with the permutation in question. That is, to check a permutation $P$, we pick an arbitrary $x$, and check if:
$E(k', P(x)) = P(E(k',x))$
This equation always holds if $P = E(k)$ for some value $k$, and rarely holds if $P$ is a random permutation.
@fgrieu: actually, it sounds like what you really ask about are known plaintext attacks; given a random set of $(x, P(x))$ pairs, can we distinguish a random $P$ from $E(k)$? Given the Pohlig-Hellman cipher, we can distinguish it in this model; is that a fundamental property of all commutative ciphers, or is that just a side effect of how Pohlig-Hellman achieves commutativity and another commutative cipher might be secure in this model? – poncho Mar 31 '14 at 21:51
@D.W.: In the definition of my new question, I leave it to an omnipotent referee to choose a random commutative cipher, and I do not see a problem with this: among the $(|S|!)^{|K|}$ ciphers with message space $S$ and keyspace $K$, some subset is commutative, and the hypothetical referee can pick a random element in that subset. BTW I fail to determine how many elements this subset has, even roughly. – fgrieu Apr 1 '14 at 7:21