Order-independent ciphers

Question

Is there exist a ciphering approach such that encrypting and decrypting order is arbitrary? Like using two padlocks on the same lock loop.

That is, if there are two keys (or keypairs) K1, K2, message M, and the cryptogram C is obtained as (for example) C=M*K1*K2 (where * denotes ciphering), then the message M can be retrieved in each of the following ways: 1) M=C*K1*K2, 2) M=C*K2*K1 (here * denotes deciphering).

Obviously, XOR is a trivial candidate. Do any cryptographically strong examples exist?

Answer 1

Take any strong block cipher (e.g. AES) and run it in Output Feedback Mode or Counter Mode.

Since OFB and CTR are essentially just XOR with a cryptographic pseudo-random stream, this will have the property you seek. Just make sure your K1 and K2 are independent.

Also, since OFB and CTR are NIST-approved (and widely-used) block cipher modes, they will be "cryptographically strong" as long as you implement them correctly and use a strong underlying block cipher.

Answer 2

What you ask for is known as a commutative cipher. One application of such ciphers is Shamir's three pass protocol (which is often explained using padlocks).

It is unclear what you mean by "cryptographically strong". I.e. one requirement that is frequently necessary is that an adversary can not learn the message if he learns the encryption of the message with K1, then encryption of the message with K2 and the encryption of the message with both K1 and K2. This requirement is obvious in the case of Shamir's three pass protocol.

It is easy to see that stream ciphers do not satisfy the requirement above. Hence it would misleading to call a stream cipher a "cryptgraphically strong commutative cipher". Equally easy to break under the assumptions above is Rasmus Fabers proposal (which I think is a construction proposed by Bruce Schneier for something a little different).

Strong commutative ciphers can be based for example on modular exponentiation. The Massey-Omura protocol is a great example.

Answer 3

If the size of the cryptogram is not an issue, you can easily construct such a cipher based on any other cipher:

Have the first encryptor generate a random bitmask B1 of size >= M. Encrypt the bitmask with the original cipher and key and transmit this encryption together with B1 ^ M.

Similarly, the next encryptor generate a new random bitmask B2, encrypts it with his key and transmits both encrypted bitmasks and B2^(B1^M). (and so on for N encryptors).

To decrypt, just decrypt each of the bitmasks in any order and xor them onto the masked message.