Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 15:01

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  fgrieu Mar 31 at 15:54
    
@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? –  D.W. Mar 31 at 16:30
    
@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 at 21:51
    
@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. –  fgrieu Apr 1 at 6:57
    
@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 at 7:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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