2
$\begingroup$

Fully Homomorphic Encryption (FHE) allows computations be done on ciphertexts. Can this technique be used to exchange keys?

For example, Alice and Bob need to agree on a 4-bit secret key. Alice sends Bob 4 different strings, which are ciphertexts for 0001, 0010, 0100, 1000, respectively. Now Bob chooses the secret key 0101. He performs bitwise-or computation on the ciphertexts corresponding to 0100 and 0001, and sends the result back to Alice. Alice deciphers the result and gets 0101.

Would this scheme be secure? (Aside from the fact that secret keys are usually much longer)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In short

It can be secure, but it will be very inefficient.

In detail

Those bit strings 0001, 0010, 0100, 1000, etc are just powers of two if you look them as integers (i.e., $2^0, 2^1, 2^2, 2^3$, etc) and applying logical bitwise or to some of them is equivalent to adding up some of the powers of two.

Therefore, what you have proposed is a scenario where Alice publishes several encryptions of powers of two, $c_i := Enc(2^i)$ and Bob combines them in some random way, that is, Bob chooses $b_i \in \{0,1\}$ and compute $$c_B := \sum_{i=0}^{n-1} b_i\cdot c_i = Enc\left(\sum_{i=0}^{n-1} b_i\cdot 2^i\right).$$

It is easy to see that if each $b_i$ is chosen uniformly, then the distribution of the value encrypted by $c_B$ is uniform on $\{0, 1, ..., 2^n-1\}$, which is a perfect scenario (the exchanged key is uniform, then, hard to guess).

However, the problem with this approach is that an attacker could look at $c_B$ and all the $c_i$'s and try to figure out the values of $b_i$'s. Notice that if we manage to discover at least one $b_i$, then we know what is the $i$-th bit of the exchanged key. So, we must rule out that possibility.

A standard way of doing it is to use the Leftover Hash Lemma to guarantee that the distribution of $c_B$ is statistically close to the uniform on the set of ciphertexts $\mathcal C$, but it would require $n$ much bigger than the security parameters $\lambda$. It means that Alice would need to publish much more than $\lambda$ ciphertexts, each one having more than $\lambda$ bits, which means publishing much more than $\lambda^2$ bits (likely to be more than $\lambda^3$). And we still have to take into account the time required to encrypt and combine all those values...

Moreover, I don't think that there is another known way of making this key-exchange secure, since the problem of hiding these $b_i$'s is basically the same problem that the homomorphic encryption schemes face when they are turned into public-key schemes, and the solution I always see on the papers is the one I said (using Leftover Hash Lemma).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Doesn't semantical security prevents the However part? $\endgroup$
    – kelalaka
    Sep 30, 2019 at 9:21
  • $\begingroup$ No. Semantic security means that given a fresh encrypted ciphertext $c$, we can't know the message it encrypts. That is a totally different property. Here we are talking about discovering the binary coefficients used in the linear combination. This is more like a subset sum problem. For instance, imagine that $c_0$ is the only odd value. Then $c_B$ is odd iff $b_0 = 1$ (regardless the value that $c_0$ encrypts). $\endgroup$
    – Hilder Vitor Lima Pereira
    Sep 30, 2019 at 9:35
  • $\begingroup$ Ah, ok. I misunderstood your solution then. Maybe a simpler solution is to encrypt the four 1's 1 1 1 1 then Bob select random 4 bits and encrypts them, and multiply them with each bit. $\endgroup$
    – kelalaka
    Sep 30, 2019 at 9:53
  • $\begingroup$ Well, it is not my solution, I basically just restated the protocol proposed in the question, since doing bit-wise ors in that case is equivalent to adding powers of two (: So, how can Bob encrypt the 4 bits in your proposed key-exchange? $\endgroup$
    – Hilder Vitor Lima Pereira
    Sep 30, 2019 at 10:09
  • $\begingroup$ Quest. about 'However'-part: In Homomorphic Encryption there is a random factor involved. Those random factors are already involved in those encrypted bit values which are send from Alice to Bob, right? If so the security is related to the used bits and not equal for all values from ${0,...2^n-1}$. Less bit count can quickly resolved with trying. The 'However'-part is about avoiding this, right? $\endgroup$
    – J. Doe
    Oct 1, 2019 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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