First, remark that the desired **commutativity is incompatible with security under [Chosen Plaintext Attack][1]**, which (under the name [IND-CPA][2]) is considered a requirement for modern encryption systems. Proof, expanded following [tylo][3]'s [comment][4], 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][5], also [here][6] 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][7] or [probabilistic][8]; 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 what 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][9]).
---
As [remarked][10] by [figlesquidge][11], the [One Time Pad][12] has the desired commutativity property, in some sense. That's also true for any [Stream Cipher][13] with an out-of-band method for synchronization (including a [block cipher][14] such as [AES][15] in [OFB][16] or [CTR][17] mode, with out-of-band [IV][18]); by _out-of-band_ I mean: not part of the [ciphertext][19] 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).
---
The simplest commutative cipher in the cryptographic folklore, used for Mental Poker, is the [Pohlig-Hellman Exponentiation Cipher][20].
### 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][21] 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][22], 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][23] 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][24] by [Ricky Demer][25], [OAEP+][26] is preferable to OAEP.
Both paddings hide the multiplicative property, by means including making the cipher probabilistic.
[1]: http://en.wikipedia.org/wiki/Chosen-plaintext_attack
[2]: http://en.wikipedia.org/wiki/Ciphertext_indistinguishability#Indistinguishability_under_chosen-plaintext_attack_.28IND-CPA.29
[3]: http://crypto.stackexchange.com/users/4082/tylo
[4]: http://crypto.stackexchange.com/questions/15289/cryptographic-system-with-double-keys-with-reversible-order#comment31969_15293
[5]: http://www.crcpress.com/product/isbn/9781584885511
[6]: http://www3.nd.edu/~cse/2013fa/60622/lecture05.pdf
[7]: http://en.wikipedia.org/wiki/Deterministic_algorithm
[8]: http://en.wikipedia.org/wiki/Probabilistic_encryption
[9]: http://en.wikipedia.org/wiki/Distinguishing_attack
[10]: http://crypto.stackexchange.com/questions/15289/cryptographic-system-with-double-keys-with-reversible-order#comment31788_15289
[11]: http://crypto.stackexchange.com/users/8911/figlesquidge
[12]: http://en.wikipedia.org/wiki/One_Time_Pad
[13]: http://en.wikipedia.org/wiki/Stream_Cipher
[14]: http://en.wikipedia.org/wiki/Block_cipher
[15]: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
[16]: http://en.wikipedia.org/wiki/Output_feedback#Output_feedback_.28OFB.29
[17]: http://en.wikipedia.org/wiki/Output_feedback#Counter_.28CTR.29
[18]: http://en.wikipedia.org/wiki/Initialization_vector
[19]: http://en.wikipedia.org/wiki/Ciphertext
[20]: http://www-ee.stanford.edu/~hellman/publications/28.pdf
[21]: http://en.wikipedia.org/wiki/Coprime_integers
[22]: http://en.wikipedia.org/wiki/Related-key_attack
[23]: http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding
[24]: http://crypto.stackexchange.com/questions/15289/cryptographic-system-with-double-keys-with-reversible-order#comment31808_15293
[25]: http://crypto.stackexchange.com/users/991/ricky-demer
[26]: http://www.shoup.net/papers/oaep.pdf