4

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!

|improve this question
  • 1
    Is this just a hypothetical scenario, or is there a specific use case for that? If the former, this question would be more on topic at crypto.SE, otherwise more context is needed. – mgibsonbr Mar 1 '13 at 3:46
  • It is a research paper in ad hoc networks to keep information privacy. The general usage case is that two nodes want to compare the values of some attributes but do not want the other node to know too much of the information, i.e., do not want the other to know which attribute match which value. – kevin123 Mar 1 '13 at 14:39
  • 1
    Are you familiar with the Socialist millionaire problem? (a variant of Yao's Millionaires' problem) That seems exactly what you want to do - determine if two values are equal or not, without disclosing them to each other. – mgibsonbr Mar 1 '13 at 18:56
4

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 gq = 1 mod p for a prime q which divides p-1), a subgroup element (a gx for some integer x) can be "encrypted" with key a by raising it to the power a (E(a,h) = ha 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 ?

|improve this answer
  • Thanks Thomas! My scenario is, suppose two nodes have attributes: a, b, c, and associated values. Two nodes want to compare the values of their attributes but do not want the other to know its values. Then, my design is, each node send below to the other, E(a,k_i)+10, E(b,k_i)+5...., where k_i is the key adopted by node_i, and 10 and 5 are values of the two attributes. After receiving it, each node further encrypt with its key. Then, one node has E(E(a,k_i), k_j)+10... and the other has E(E(a,k_j), k_i)+7... As E(E(a,k_i), k_j) = E(E(a,k_j), k_i), they can compare and do not disclose values. – kevin123 Mar 1 '13 at 14:23
1

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)

|improve this answer
  • 1
    If both RSA key pairs use the same modulus, they cannot really be called distinct keys. Knowledge of the modulus, public exponent and private exponent is sufficient to factor the modulus. – Thomas Pornin Mar 1 '13 at 12:16
  • Thanks mgibsonbr! I do need symmetric cipher. I have looked at the One-Time-Pad. It satisfied the requirement. But I may need to use the key to encrypt more than one items....otherwise the cost would be too huge since I have a lot of items to encrypt. Then how would that degrade its security level? And in this case, can the unpadded RSA still be used? – kevin123 Mar 1 '13 at 14:26
  • @ThomasPornin that's right! It's been 12 years since I studied the internals of RSA, and my memory totally failed me. I thought the public exponent was equal to p*q, and the modulus was unimportant (just had to be coprime to something I didn't remember). Now I see that it's the opposite, which makes the first part of my answer void... – mgibsonbr Mar 1 '13 at 19:27
  • @kevin123 Unfortunatly, as commented above, RSA can not be used. However, see my updated answer, it might be what you're looking for. Generating new keys for OTP is easy, since they're just random numbers... Exchanging them if you don't have a secure channel, that is the hard part, but it seems it doesn't apply to your case (you don't need to exchange them, you do have a secure channel, or both). – mgibsonbr Mar 1 '13 at 20:22
0

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

|improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.