Page 38 says that Key Exchange implies the existence of one-way functions.
When I try to work out the proof myself, I get that in the hypothetical case
where there is Key Exchange but no one-way functions, an eavesdropper
would have a non-negligible probability of obtaining a random bits that would
have produced that communication actually observed, and then I get stuck.
As far as I can see, it could be that when the eavesdropper finds such bits,
the probability that the bits found would give the same key as
the parties get from the random bits actually used is negligible.
Does the existence of a secure Key Exchange protocol imply the existence of one-way functions?
If yes, how is that proven?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ You have to use the property of key exchange that Alice and Bob eventually agree on a key based on: (1) their local randomness, r_A, r_B, and (2) the transcript that is induced by this randomness. $\endgroup$– Alon RosenOct 24, 2011 at 7:47
-
$\begingroup$ Alice and Bob get each get a key from their own local randomness plus the transcript, such that the probability the keys are different is negligible. I don't see how the existence of a OWF follows from that. (That is, after all, why I'm asking.) $\endgroup$– user6973Oct 24, 2011 at 8:34
-
$\begingroup$ It seems more intuitive to me that the impossibility of one way functions makes key exchange impossible. But this is equivalent (invert the implication). $\endgroup$– Craig GidneyOct 24, 2011 at 12:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Your question suggests the following tentative reduction to obtain a OWF from a secure KE: Given an input, interpret it as the private random coins of two simulated parties to the KE protocol. Based on their private randomness, there will be some sequence of public messages between them, and at some point they will stop and agree on a private shared key (with some high probability). Then the public transcript of their communications is the output of the OWF.
You are right to be worried about this approach in the case when Alice and Bob may not agree with probability 1. In fact, this construction is NOT necessarily a OWF in that case. Rather, it is a weaker primitive known as a "distributionally one-way function," which is, informally, a function for which it is hard to generate a uniformly random preimage of $f(x)$, when $x$ is selected at random. It is known (but non-obvious) that one can construct a true one-way function using a distributionally one-way function. See e.g. Exercise 17 on page 96 of Goldreich "Foundations of Cryptography: Basic Tools," which is available for limited viewing on Google preview.
To directly see why the above reduction does not suffice, we can use the common "make a stupid modification" technique. Namely, suppose there exists a secure KE protocol where Alice and Bob agree with probability $1 - \epsilon$. Consider a stupidly-modified KE protocol that works as follows: Alice and Bob first each flip 100 coins. For each of Alice, Bob individually: If all 100 coins are zero, their remaining randomness is interpreted as encoding a sequence of messages which they send to the other party, ignoring whatever the other one says; then they just output a random "shared key." (Otherwise they follow the original protocol.) Given any public transcript, it is possible (with negligible probability) that it was generated by an Alice and Bob who BOTH flipped 100 zeroes and happened to have their remaining randomness specify that exact sequence of messages.
This is still a secure KE protocol, where Alice and Bob will agree with probability at least $1 - \epsilon - 2^{-100}$. On the other hand, it utterly fails to be a OWF in the hoped-for manner, since an attacker who sees some public transcript can always trivially invert by choosing 100-zeroes randomness for each of Alice and Bob.
-
$\begingroup$ First, you would need $n$ bits (or something like that) instead of 100, since it needs to be negligible. Second, while that function intuitively should be distributionally one-way, how is that shown? $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ I feel like there's a simple counting argument I'm missing. $\endgroup$– user6973Oct 24, 2011 at 23:58
-
$\begingroup$ Right, I was writing informally. To be precise, you would indeed need to replace "100" with the relevant security parameter. $\endgroup$ Oct 25, 2011 at 2:31
-
$\begingroup$ As for showing that it's distributionally one-way, I believe the following sketch works: With high probability over A and B's randomness, the resulting transcript will be "good" i.e. it will be such that conditioned on its being the public transcript, then with high probability A and B's randomness was such that they do in fact agree on a key. Since their randomness was uniform to begin with, an attacker who samples uniformly from preimages will hit a good one (which allows them to recover the correct shared key) with high probability. $\endgroup$ Oct 25, 2011 at 2:40
-
$\begingroup$ I don't see why the transcript must have a high probability of being "good", or why uniformly sampling preimages of a "good" transcript will work. My guess is that the right definition of "good" transcripts would have there be a particular key which there is a high probability A and B agreed on, although then it would be even harder to show that there is a high probability of a good transcript. $\endgroup$– user6973Oct 25, 2011 at 4:12
-
$\begingroup$ If a noticeable fraction of transcripts are bad, then conditioning on the event that the transcript is bad, we see that (by definition of "bad") with noticeable probability A and B will NOT agree on a key. This contradicts security of the KE scheme. If the transcript is good, then they will agree on a key with high probability. This, and the fact that each one's private coins are independent of the other's private coins, implies that there's in fact a UNIQUE key, defined by the good transcript, which they both output whp. Admittedly it's only a sketch, so it's possible I've missed something. $\endgroup$ Oct 25, 2011 at 4:54