Cryptographic system with double keys with reversible order

Question

While reading Shamir, Rivest and Adleman's paper on "Mental Poker", I've met a mention of system such that $E_a(E_b(x)) = E_b(E_a(x))$, without however disclosing details on it, with $E_a(x)$ being “encrypt plaintext $x$ with key $a$”.

Do any existing secure modern cryptosystems have this property, and how is it called for later reference?

Answer 1

First, remark that the desired commutativity is incompatible with security under Chosen Plaintext Attack, which (under the name IND-CPA) is considered a requirement for modern encryption systems. Proof, expanded following tylo's comment, using the IND-CPA game as played for symmetric encryption (see the CPA indistinguishability experiment in section 3.5 of Katz and Lindell's Introduction to modern cryptography, also here on page 4):

• We assume a cipher $E$:
  • commutative as in the question, that is: $\forall a,\forall b,\forall x, E_a(E_b(x))=E_b(E_a(x))$;
  • injective: $\forall a,\forall x,\forall y, E_a(x)=E_a(y)\implies x=y$ (a necessity for reliable decryption);
  • $E$ can be deterministic or probabilistic; in the later case $E$ has some randomness source as a hidden input beyond key (the subscript) and data (the explicit parameter), and the above properties hold for all values of the random inputs in each instance of $E$;
  • the cipher has a public definition (except for its randomness soure if any) allowing its practical implementation by the adversary (an algorithm with time and space complexity polynomial in the size of the parameters);
• the game starts with the referee choosing and announcing the size of parameters;
• the referee secretly chooses a random key $k$;
• the adversary chooses a random key $r$, a random plaintext $X$, and computes $M_0=E_r(X)$ using the cipher's definition, until $M_0\ne X$ (which holds with high odds for any secure cipher);
• in a training phase, the adversary submits $X$ for encryption and obtains $Y=E_k(X)$;
• in the challenge phase
  • the adversary submits $M_0$, and any $M_1$ that is neither $M_0$ nor $X$ (submitting $M_1=M_0$ would be poor strategy; submitting $M_0$ or $M_1$ that was submitted in the training phase would be against the rules of the game played for deterministic encryption);
  • the referee secretly chooses $i$ randomly in $\{0,1\}$ by fair coin toss, and returns $C=E_k(M_b)$;
• (here the rule of the game allows the adversary to make other queries for encryption under key $k$, bound to be for messages different from $M_0$ and $M_1$ in the game played for deterministic encryption);
• the adversary returns $i'=0$ if $C=E_r(Y)$, which is computable using the cipher's definition, or $i'=1$ otherwise;
• the adversary wins if $i'=i$ (and we want the odds of that, which should be better than $1/2$ by some $\epsilon>0$ independent of the size of the parameters);
  • if the referee picked $i=0$: $C=E_k(M_0)=E_k(E_r(X))$, and applying the commutativity property of the cipher we get $C=E_r(E_k(X))=E_r(Y)$, thus $i'=0$;
  • if the referee picked $i=1$: since $M_1\ne M_0$, and because the cipher is injective, $C=E_k(M_1)$ must be different from whatever $E_k(M_0)$ would have been, which (as shown above) is bound to match $E_r(Y)$ that was computed by the adversary and used to find $i'$, thus $i'=1$ (note: in the case of a probabilistic algorithm, one could think there potentially could be several $E_k(M_0)$, but the commutativity property makes it necessary that they all match $E_r(Y)$ as computed by the adversary: in order to be commutative, the cipher is bound to be deterministic for inputs $M_0$ and $Y$ given how these have been generated);
  • thus with certainty, $i'=i$ (this is a perfect distinguisher).

---

As remarked by figlesquidge, XOR with a One Time Pad has the desired commutativity property, in some sense. That's also true for any Stream Cipher with an out-of-band method for synchronization (including a block cipher such as AES in OFB or CTR mode, with out-of-band IV); by out-of-band I mean: not part of the ciphertext for which the commutativity property is thought.

However the OTP or other out-of-band data is often impractical (in particular it won't work in use cases where several ciphertexts are shuffled but out-of-band data has not, which is the situation in Mental Poker), and do not match the definition of a cipher (which requires reusable key and no out-of-band data).

---

We study the simplest commutative cipher in the cryptographic folklore, sometime used for Mental Poker:

The Pohlig-Hellman Exponentiation Cipher

For a given public odd prime $p$, let $K$ be the set of $k\in\mathbb N$ with $0<k<p$ that are coprime with $p-1$, and $*$ multiplication modulo $p-1$, so that $(K,*)$ is a commutative group with $k=1$ the neutral element.

The Pohlig-Hellman Exponentiation Cipher over $\mathbb Z_p$ with key in $k$ is $$\begin{align} E:K\times\mathbb Z_p&\mapsto \mathbb Z_p\\ (k,x)&\mapsto E(k,x)=x^k\bmod p=E_k(x) \end{align}$$

Encryption with key $k$ is $E_k: x\mapsto E_k(x)$ and is a permutation of $\mathbb Z_p$. The set of the permutations obtained form a group under function composition (noted $\circ$), isomorphic to $(K,*)$: $$\forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p,E_b(E_a(x))=(E_b\circ E_a)(x)=E_{b*a}(x)$$ As a consequence, decryption is $D_k=E_\overline k$, with $\overline k=k^{-1}\bmod(p-1)$ the inverse of $k$ in group $(K,*)$; and the desired commutativity property holds: $$\forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p, E_a(E_b(x))=E_b(E_a(x))$$

For appropriate $p$ (making the Discrete Logarithm Problem hard), the cipher is conjectured secure for multiple random plaintexts related to the same random key [that's stated before (15) in the original article, linked to the title of this section; and justified by an argument I do not get]. However, it has a number of other properties that a random commutative cipher would not obviously have, including the multiplicative property $\pmod p$:

$$\forall k\in K,\forall x\in \mathbb Z_p,\forall y\in \mathbb Z_p, E_k(x\cdot y\bmod p)=E_k(x)\cdot E_k(y)\bmod p$$

There are a number of other undesirable properties:

1. Three fixed points: $\forall x\in\{0,1,p-1\},\forall k\in K,E_k(x)=x$
2. 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$
3. The isomorphism with $(K,*)$ allows some related-key attacks, and implies a weak key ($k=1$).
4. The keyspace is not an interval of $\mathbb N$, which is inconvenient.

A variant

We can fix these 4 issues. Let $p$ be a large public prime with $(p-1)/2$ prime, such as $p=\lfloor\pi\cdot2^{2046}\rfloor+3,617,739$. Let $P$ be the set of $(p-3)/2$ integers $\{2,3\dots,(p-3)/2,(p-1)/2\}$. For key $k$ of 256 bits and data $x\in P$, define $$\begin{align} k_E&=2^{320}\cdot\small\text{SHA-256}(k)+2^{64}\cdot k+1\\ k_D&=\overline{k_E}={k_E}^{-1}\bmod (p-1)\\ \mathbf E_k(x)&=\min\big(x^{k_E}\bmod p,p-(x^{k_E}\bmod p)\big)\\ \mathbf D_k(x)&=\min\big(x^{k_D}\bmod p,p-(x^{k_D}\bmod p)\big) \end{align}$$ Fixed points and symmetry are removed by the definition of $P$ and the use of $\min$. The construction of the exponent $k_E$ makes it coprime with $p-1$ (since $k_E$ is odd and too small to divide the single odd divisor of $p-1$), ensures that any 256-bit $k$ makes a fine key, and provides fair protection against related-key attacks. The construction of $k_D$ ensures that $\forall k,\forall x,\mathbf D_k(\mathbf E_k(x))=x$.

The desired commutativity property still holds, as well as the multiplicative property (be it wanted or not). We can artificially get rid of the multiplicative property by inserting a pseudo-random permutation $M$ of the set $P$ before encryption, and its reverse afterwards: $x\mapsto (M^{-1}\circ\mathbf E_k\circ M)(x)$ still has the commutativity property, but not the multiplicative property; however an adversary knowing $M$ can still potentially get advantage of the multiplicative property.

Using RSA encryption padding

If $\small\text{OAEP}(x)$ designates the padding used for RSA-OAEP with a modulus of $\lceil\log_2(p)\rceil$ bits, then $x\mapsto E(\small\text{OAEP}(x))$ seems to be IND-CPA-secure, and decipherable (the desired commutativity property is lost: that padding must be external to whatever step of the protocol requires commutativity). As pointed by Ricky Demer, OAEP+ is preferable to OAEP.

Both paddings hide the multiplicative property, by means including making the cipher probabilistic.