Return to Answer

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):

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.

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.

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):

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.

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.

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

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

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 state before (14) in the article linked to the title of this section, with 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$:

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$: