Can encryption twice with two keys in different sequences lead to the same result?

Question

I am looking for an encryption algorithm for one of my current papers. The basic requirement is that, suppose I have two keys k1 and k2, and the E(k1,t) means encrypt t with key k1.

Are there any encryption algorithm satisfy that E(k2, E(k1,t)) = E(k1, E(k2,t))?

I know that Caesar cipher satisfies the requirement. But it seems too weak. Are there any more secure algorithms that can be used for my requirement? Thanks!

Answer 1

You may use any symmetric encryption which works by generating a key-dependent stream of bytes which is then XORed with the data to encrypt. This is the case of most stream ciphers; this also applies to a block cipher in CTR mode (which practically turns a block cipher into a stream cipher).

Such ciphers are a bit delicate to use, because you shall never reuse a given key-dependent stream (that would be the infamous "two-times pad"). This means that either a given key will be used to encrypt only one message, or that you use a stream cipher with an initialization vector which will need its own management. Crucially, in your case, this means that potential attackers should not be allowed to observe E(k1,t), E(k2,t) and E(k1,E(k2,t)), because this would enable them to recover t (namely by XORing all three streams together).

If your specific scenario make the stream cipher solution inapplicable, then you would have to use more esoteric solutions which are non-standard, thus cannot be recommended in practice (but are fine for research). For instance, given Diffie-Hellman group parameters (a modulus p, and a generator g which is such that g^q = 1 mod p for a prime q which divides p-1), a subgroup element (a g^x for some integer x) can be "encrypted" with key a by raising it to the power a (E(a,h) = h^a mod p). "Decryption" implies raising to power 1/a mod q (inverse modulo q is computed with the extended euclidean algorithm). With this "encryption" algorithm, you get the commutativity you look for (E(a,E(b,h)) = E(b,E(a,h))) AND you can publish E(a,h), E(b,h) and E(a,E(b,h)) without revealing h.

... but that's just a variant of Diffie-Hellman. The good question is then: why do you want your commutative encryption thing ? What are you trying to do, that Diffie-Hellman cannot do ?

Answer 2

RSA (unpadded) follows this requirement, if you use two different key pairs but the same modulus: (Update: no it doesn't, as Thomas Pornin pointed out in the comments)

(t^k1)^k2 = t^(k1*k2) = (t^k2)^k1

If you need a symmetric cipher, a simple One-Time-Pad will also work (though in this case, the key lengths must be at least as big as the message, and should never be reused):

(t xor k1) xor k2 = (t xor k2) xor k1

There might be others as well. I'd suggest looking at homomorphic encryption algoritms for more, though I'm not sure they are actually commutative the way you want to (and probably not as strong as the ones that don't have this restriction).

Update: Some notes based on your feedback:

• Since the keys will never have to be exchanged (i.e. the party which encrypts is the only one that knows the key) then the OTP key length is not really a concern;
• If the channel the parties use to communicate to each other is secure, then there's no need to protect the data against a third-party attacker;

• If you perform a cryptographic operation but never discloses the result then it doesn't really matter whether or not you reused your key. Here's my understanding of the protocol (disclaimer: I'm not a cryptographer, have very limited knowledge of the subject and can be totally wrong; my advice would be, if possible, to follow an established protocol, such as Yao's Millionaires' problem):

  Alice                    Bob
  a1, k1, a1 xor k1        a2, k2, a2 xor k2
  a2 xor k2          <==>  a1 xor k1
  a2 xor k2 xor k1         a1 xor k1 xor k2
  

  If a1 == a2, then Alice's and Bob's results will be equals. The problem now is: how to compare them? Alice reused k1, so she can't send a2 xor k2 xor k1 to Bob or he would be able to recover k1 (by xor'ing it with a2 xor k2).

  But assuming k1 is large enough, she can send a hash of the result, so Bob can compare to his hash of his result. As long as Bob can not reverse the hash, he doesn't learn anything about k1. If k1 was generated by a CSPRNG then even a fast hash such as SHA-512 should be safe enough.

  (Note: Bob would also need to send Alice his hash for she to compare; while this protocol ensures neither gain any information about a1 or a2 other than whether or not they're equals, nothing prevents either of them to cheat - both can send an unrelated hash to convince the other that the values are different, or the first receiver can re-send the same hash to convince the first sender that the values are equals)

Answer 3

I'm surprised that nobody has mentioned Zero Knowledge Proofs yet. It sounds like the definition of what you're looking for.

Additionally, is it the requirement that the system be reversable? If it's simply proving that you know a certain value, taking the HMAC of the attribute/value combination can prove that you know the value without saying what the value is (assuming the other side has the same values to be able to verify the HMAC).