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.

  • $\begingroup$ 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}$ $\endgroup$
    – user991
    Commented Mar 31, 2014 at 15:01

1 Answer 1


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.

  • $\begingroup$ That's very true! I used that very argument in the beginning of my answer linked to the question, but failed to apply it!! I need to find a different wording of the question, on the tune of: "indistinguishable from a random set of permutations with the commutativity property". I lean towards making that a different question, though. $\endgroup$
    – fgrieu
    Commented Mar 31, 2014 at 15:54
  • $\begingroup$ @fgrieu, yes, maybe posting a separate question would be best. When you do, can you spell out how we choose a random set of permutations with the commutativity property? Is that notion uniquely defined? $\endgroup$
    – D.W.
    Commented Mar 31, 2014 at 16:30
  • $\begingroup$ @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? $\endgroup$
    – poncho
    Commented Mar 31, 2014 at 21:51
  • $\begingroup$ @poncho: I think that I see how to make a variant of Pohlig-Hellman Exponentiation Cipher secure under known-plaintext while keeping commutativity, so that's not my question. I essentially add a fixed pseudo-random permutation on block input, its inverse on block output. However it inherits properties beyond what a commutative cipher is bound to have. I have a reworded question here. $\endgroup$
    – fgrieu
    Commented Apr 1, 2014 at 6:57
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Commented Apr 1, 2014 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.