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, 2018 at 11:44


Your Answer

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

Browse other questions tagged or ask your own question.