# Can you exchange a shared key without any hardness assumptions?

Imagine that P=NP, and one way functions don't exist. Can two people end up with a random shared key of arbitrary length, if every exchange is public? They have true RNGs, and know who they are talking to (we're not worried about mitm attacks).

There is also someone else sharing the channel, who has one time pads with both of them. The two people want to get their own one time pad, without the third person having it. They can obviously check afterwards if they have the same pad by sending random bits in it to each other.

It seems like there should be some way to have one person send a secure message to the third person (who shares a otp with him), and send that on and back with different layers added on each time, then unlayering afterwards, but I don't see exactly if it can work. A solution should make it that the two sides only end up with the same key if the middle person has no way of getting it.

The motivation for this was that CAs could act as middlemen for secure communication in a post-P=NP world, with every computer shipping with the CAs OTPs.

• – user991
Feb 6 '15 at 0:22
• @RickyDemer But what if many possible inputs would result in the same transcript? Then the transcript would tell you nothing, but could still be useful to those that have either sides random numbers.
– ike
Feb 6 '15 at 0:48
• Must they know whether or not key exchange succeeded? Feb 6 '15 at 2:00
• Does Quantum Key Distribution count? Feb 6 '15 at 2:00
• @poncho Isn't quantum key exchange incompatible with "every exchange is public?" I was under the impression the whole point of it was that you can't eavesdrop due to the laws of physics. Feb 6 '15 at 2:02

In cases where Alice and Bob are guaranteed to arrive at the same key, this is impossible: the function that takes Alice and Bob's private info as input, and produces the public transcript as output, must be a one-way function if the scheme is to be secure and if it always negotiates a shared key. If it sometimes fails, then you don't necessarily get a OWF; you get a function which can be turned into a OWF, but it's more complicated. Assuming that either Alice or Bob knows if it succeeded, you can make this construction work.

It should be pretty clear why the nonexistence of OWFs implies that you can, given a transcript, compute a possible set of private info for Alice and for Bob that gives that transcript. In comments, you suggested many inputs giving the same transcript but different keys. This is impossible if, after the protocol, either Alice or Bob knows if they successfully negotiated a key or not (and the other one doesn't think they know but actually have it wrong). In that case, any two inputs that lead to successful key exchange and produce the same transcript must negotiate the same key.

Each party has private information for any particular run; it's just whatever secret they had, plus the result of every single coin flip that happened during that run of the protocol. We can specify this in advance; if you need more coin flips than are in the private information, the algorithm just fails. Then at any step, whatever message is sent is a deterministic function of the transcript so far and the private information the sender has (all randomness got embedded in the private info). Also, include whatever check you're doing to verify key exchange worked in the protocol.

Suppose the set of private info $A_0,B_0$ and the set $A_1,B_1$ produced the same transcript. WLOG, Alice sent the first message each time. Consider what happens with $A_0,B_1$; we want it to be the same transcript as well. Alice sends the first message again; this is based only on $A_0$, so it's the same as the first message there. Now, suppose the first $k$ messages are the same in this new transcript as in $A_0,B_0$. Alice has exactly the same information as after the first $k$ messages in $A_0,B_0$, so she does the same thing (either doesn't send or sends the same message as there). Bob has exactly the same info as after $k$ messages in $A_1,B_1$, so does the same thing he did there. As the transcripts of $A_0,B_0$ and $A_1,B_1$ are the same, Bob did the same thing in the latter as in the former, so after message $k$, Alice and Bob behave the same as they did in $A_0,B_0$. So the first $k+1$ messages are the same if the first $k$ are. So, $A_0,B_1$ produces the same transcript as $A_0,B_0$.

Alice now computes a key from $A_0$ and the transcript. She can't know whether Bob had $B_0$ or $B_1$, so the key is the same. Likewise, Bob can't know if Alice had $A_0$ or $A_1$, so he produces the same key as $A_1,B_1$. If Alice and Bob know whether or not key exchange was successful, and Alice knew $A_0,B_0$ led to successful exchange, then she also knows $A_0,B_1$ did. That means the key from $A_0,B_0$ is that from $A_0,B_1$ is that from $A_1,B_1$. The only other option is that $A_0,B_1$ failed; in that case, Alice did not know it failed, so she doesn't ever know if her key exchange succeeded or failed.

The reason one party has to know if it succeeded or failed in this proof is that that's how we get that $A_0,B_1$ necessarily succeeded. It may be possible to prove that without someone having to know, but even without that, just extend the private info to contain the actual message being sent (e.g. if it's a one-way message, then Alice has it in her private info and the negotiated key is really the message itself). If the proof doesn't work because neither one knows, then that means neither Alice nor Bob knows whether or not Bob got Alice's message correctly, which is a bit of a problem.

• What if the probability of failure is 1e-20? Does your proof imply that the attacker can get the key with a similar likelihood of failure?
– ike
Feb 6 '15 at 14:17
• @Ike : $\;\;\;$ Not quite; his proof implies that the attacker can make their failure probability an arbitrarily small inverse-polynomial function of the security parameter. $\:$ Choose some length $L$, and consider the function from strings of length $L$ to the union of $\{\hspace{-0.02 in}\perp\}$ with the set of transcripts which is given by trying to run Alice and Bob using the input string as the random bits, $\:$ (continued ...) $\;\;\;\;\;\;\;$
– user991
Feb 6 '15 at 18:36
• (... continued) $\:$ outputting $\perp$ if more than $L$ bits of randomness would've been used or either of them would've reported failure, and outputting the resulting transcript otherwise. $\:$ If Alice and Bob together use at most $L$ random bits and succeed, then a preimage of the transcript under that function yields the agreed-on key. $\:$ If there might be undetected failure, then one would have to read Clint's comments to his answer on the page I linked to in the other comment thread. $\;\;\;\;\;\;\;$
– user991
Feb 6 '15 at 18:37