[Corrected thanks to tylo's [comment][1]]  First, remark that **for a [_deterministic_ encryption][2] scheme at least, the desired commutativity is incompatible with security under [Chosen Plaintext Attack][3]**, which (under the modern name [IND-CPA][4]) is considered a requirement for modern encryption systems. Proof:

- the adversary chooses a random key $r$, a random plaintext $P$, and computes $M_0=E_r(P)$ using the cipher's definition, until $M_0\ne P$ (which is true with overwhelming odds anyway);
- in the so-called training phase, the adversary submits $P$ for encryption and obtains $Q=E_k(P)$ (note: the IND-CPA model for deterministic ciphers, including but not limited to block ciphers, includes such phase; see e.g. page 9 [here][5]);
- in the challenge phase, the adversary submits $M_0$, and any $M_1$ that is neither $P$ nor $M_0$ (submitting what was submitted in the training phase would be against the rules of the game, and submitting $M_1=M_0$ would be poor strategy);
- the referee secretly chooses $b$ randomly in $\{0,1\}$ and returns $C=E_k(M_b)$;
- the adversary return $b'=0$ if $C=E_r(Q)$ which is computable using the cipher's definition, or $b'=1$ otherwise;
- if the referee has picked $b=0$, $C=E_k(M_0)=E_k(E_r(P))$; applying the commutativity property of the cipher, we get $C=E_r(E_k(P))=E_r(Q)$, thus $b'=0$;
- if the referee picked $b=1$, since $M_1\ne M_0$, $C=E_k(M_1)$ is different from $E_k(M_0)$ which (as shown above) is $E_r(Q)$, thus $b'=1$;
- thus with certainty, $b'=b$ (this is a perfect [distinguisher][6]).

Note: I do not know how even a probabilistic encryption scheme could be both commutative and IND-CPA secure, and would not be so surprised if that was provably impossible, using a more complex argument than the above.

---
As [remarked][7] by [figlesquidge][8], the [One Time Pad][9] has the desired commutativity property, in some sense. That's also true for any [Stream Cipher][10] with an out-of-band method for synchronization (including a [block cipher][11] such as [AES][12] in [OFB][13] or [CTR][14] mode, with out-of-band [IV][15]); by _out-of-band_ I mean: not part of the [ciphertext][16] 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 have been shuffled but out-of-band data has not, which is the situation in Mental Poker), thus we may want a cipher with a reusable key and no out-of-bad data. The simplest one in the cryptographic folklore, used for Mental Poker, is the [Pohlig-Hellman Exponentiation Cipher][17].

### Standard 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][18] 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))$$

There are 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$$

Also 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][19], 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][20] 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][21] by [Ricky Demer][22], [OAEP+][23] is preferable to OAEP.


  [1]: http://crypto.stackexchange.com/questions/15289/cryptographic-system-with-double-keys-with-reversible-order#comment31969_15293
  [2]: http://en.wikipedia.org/wiki/Deterministic_encryption
  [3]: http://en.wikipedia.org/wiki/Chosen-plaintext_attack
  [4]: http://en.wikipedia.org/wiki/Ciphertext_indistinguishability#Indistinguishability_under_chosen-plaintext_attack_.28IND-CPA.29
  [5]: https://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect08.pdf
  [6]: http://en.wikipedia.org/wiki/Distinguishing_attack
  [7]: http://crypto.stackexchange.com/questions/15289/cryptographic-system-with-double-keys-with-reversible-order#comment31788_15289
  [8]: http://crypto.stackexchange.com/users/8911/figlesquidge
  [9]: http://en.wikipedia.org/wiki/One_Time_Pad
  [10]: http://en.wikipedia.org/wiki/Stream_Cipher
  [11]: http://en.wikipedia.org/wiki/Block_cipher
  [12]: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
  [13]: http://en.wikipedia.org/wiki/Output_feedback#Output_feedback_.28OFB.29
  [14]: http://en.wikipedia.org/wiki/Output_feedback#Counter_.28CTR.29
  [15]: http://en.wikipedia.org/wiki/Initialization_vector
  [16]: http://en.wikipedia.org/wiki/Ciphertext
  [17]: http://www-ee.stanford.edu/~hellman/publications/28.pdf
  [18]: http://en.wikipedia.org/wiki/Coprime_integers
  [19]: http://en.wikipedia.org/wiki/Related-key_attack
  [20]: http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding
  [21]: http://crypto.stackexchange.com/questions/15289/cryptographic-system-with-double-keys-with-reversible-order#comment31808_15293
  [22]: http://crypto.stackexchange.com/users/991/ricky-demer
  [23]: http://www.shoup.net/papers/oaep.pdf