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.

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?

share|improve this question
1  
This property means that the encryption is commutative. One example of a commutative encryption operation would be xor. Here are some related questions. In general a secure scheme is unlikely to have this property since unless required it exposes a potential weakness –  figlesquidge Mar 28 at 14:45
add comment

1 Answer 1

up vote 5 down vote accepted

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, 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.

share|improve this answer
1  
One could use OAEP+ instead of OEAP. $\;$ –  Ricky Demer Mar 28 at 16:14
1  
Actually, does commutativity survive inserting either of those padding schemes? $\;$ –  Ricky Demer Mar 28 at 16:47
    
Thank you for your answer! Could you provide any papers on the protocol you've described? Like, if it's secure, why isn't it widespread? –  modchan Mar 29 at 17:53
1  
In the IND-CPA game the adversary usually only gets one challenge ciphertext. This still breaks all deterministic encryption, but if $E$ is probabilistic it isn't necessarily the case. However, probabilistic schemes can probably not provide this commutativity. –  tylo Mar 31 at 16:42
1  
out-of-bad $\mapsto$ out-of-band $\;$ –  Ricky Demer Apr 2 at 15:20
show 2 more comments

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.