# Are there any secure commutative ciphers?

This answer lists two commutative cipher algorithms - Pohlig-Hellman and SRA. However, they don't appear to be too secure.

My question is, here there any commutative ciphers out there that are secure enough for sensitive data encryption / decryption (money is involved) and at the same time not burdening enough on the computer to be run in real time on less powerful devices (say, a smartphone)?

-
Can you use a hybrid scheme, where you apply the commutative cipher to a symmetric key? And how long are your messages? –  CodesInChaos Mar 3 '13 at 22:09
RSA suffers from pretty much the same issues, so we apply randomized padding and use it as hybrid encryption. –  CodesInChaos Mar 3 '13 at 22:11
This question probably has to be rephrased. Commutativity is, by itself, more of a security vulnerability than a security feature. If you really need this commutativity, you probably have to build an entire protocol around it, to make sure it can't be exploited by an attacker. Just asking for the security of the commutative cipher itself doesn't make much sense. –  Henrick Hellström Mar 4 '13 at 1:59
@CodesInChaos The application is mental poker - the messages are very short. –  ThePiachu Mar 4 '13 at 5:50
@HenrickHellström - I asked about it in a separate question - crypto.stackexchange.com/q/6575/843 . –  ThePiachu Mar 4 '13 at 5:51

For a set of $B$ elements (e.g. $B = 2^n$ for all the "blocks of $n$ bits"), there are $B!$ possible permutations. An ideal block cipher is such that an instance with an unknown key is indistinguishable from a permutation chosen at random, uniformly, in these $B!$ permutations.

Since permutations don't commute in general, a "perfect" commutative block cipher must work over a subset of these $B!$ permutations, where all elements of the subset actually commute with each other, and this makes a commutative block cipher highly distinguishable from a randomly chosen permutation. Namely, suppose that there is a black box which implements either the block cipher $E_K$ (for some unknown key $K$), or a randomly chosen permutation. The attacker can submit plaintexts to encrypt (that's a chosen-plaintext attack scenario), and observe the result; his goal is to determine whether the box really implements $E_K$ for some $K$, or not. He then does the following:

• He selects a key $K'$ randomly, as well as a plaintext block $x$.
• He sends $x$ and $y = E_{K'}(x)$ as plaintexts to encrypt with the box.
• The box returns, respectively, $u$ and $v$.
• The attacker checks whether $E_{K'}(u) = v$. That equation will hold with probability $1$ if the box implements $E_K$, but only $1/B$ (i.e. almost zero) if the box implements a randomly chosen permutation.

In that sense, a commutative block cipher cannot be secure "as a block cipher". Commutative encryption can be secure only as part of a protocol in which the commutative encryption primitive is not used in the same way as, say, AES. What the scenario explained above means is that a deterministic commutative cipher cannot be "IND-CPA secure" (indistinguishable from a random permutation in a chosen-plaintext attack setup). So you need some randomness injected "somewhere", which may be some padding or an other feature of the overall protocol (e.g. encryption is only applied on values chosen randomly and uniformly in a given set, which are then used to derive a "normal" symmetric key, aka hybrid encryption).

-