Paper 2009/262

Computationally Secure Two-Round Authenticated Message Exchange

Klaas Ole Kuertz, Henning Schnoor, and Thomas Wilke


We study two-round authenticated message exchange protocols consisting of a single request and a single response, with the realistic assumption that the responder is long-lived and has bounded memory. We first argue that such protocols necessarily need elements such as timestamps to be secure. We then present such a protocol and prove that it is correct and computationally secure. In our model, the adversary provides the initiator and the responder with the payload of their messages, which means our protocol can be used to implement securely any service based on authenticated message exchange. We even allow the adversary to read and reset the memory of the principals and to use, with very few restrictions, the private keys of the principals for signing the payloads or parts thereof. The latter corresponds to situations in which the keys are not only used by our protocol. We use timestamps to secure our protocol, but only assume that each principal has access to a local clock.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ASIACCS 2010
authenticated message exchangeimplementationdigital signatures
Contact author(s)
kuertz @ ti informatik uni-kiel de
2010-01-11: last of 2 revisions
2009-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Klaas Ole Kuertz and Henning Schnoor and Thomas Wilke},
      title = {Computationally Secure Two-Round Authenticated Message Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2009/262},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.