An anonymous key exchange protocol $P$ is pair of probabilistic machines $(A,B)$ that sends messages to each other and at the end, both $A$ and $B$ will share the same key $k$.

The attacker can see the protocol transcript $T_P$ of $P$, that is, the sequence of messages exchanged between the parties in one execution of $P$.

How can a computationally unbounded attacker break an anonymous key exchange protocol?

  • 1
    $\begingroup$ An unbounded attacker can just run the protocol for all initial states of A and B and for all randomness coin results and stop when the given configuration yields a transcript that matches the given transcript (and then because they have the randomness results and the initial states, they have the key) $\endgroup$ – SEJPM Jun 23 '18 at 11:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.