Paper 2006/041

Reactively Simulatable Certified Mail

Birgit Pfitzmann, Matthias Schunter, and Michael Waidner


(Revision of Sept. 2004 of a journal submission from Dec. 2000.) Certified mail is the fair exchange of a message for a receipt, i.e., the recipient gets the message if and only if the sender gets a receipt. It is an important primitive for electronic commerce and other atomicity services. Certified-mail protocols are known in the literature, but there was no rigorous definition yet, in particular for optimistic protocols and for many interleaved executions. We provide such a definition via an ideal system and show that a specific real certified-mail protocol is as secure as this ideal system in the sense of reactive simulatability in the standard model of cryptography and under standard assumptions. As certified mail without any third party is not practical, we consider optimistic protocols, which involve a third party only if one party tries to cheat. The real protocol resembles prior protocols, but we had to use a different cryptographic primitive to achieve simulatability. The communication model is synchronous. This proof first demonstrated that a cryptographic multi-step protocol can fulfil a general definition of reactive simulatability enabling concurrent composition. We also first showed how formal-method style reasoning can be applied over the ideal system in a cryptographically sound way. Moreover, the treatment of multiple protocol runs and their modular proof in spite of the use of common cryptographic primitives for all runs can be seen as a first example of what is now known as joint-state composition.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Certified MailFair ExchangeReactive SimulatabilityComposabilityFormal Methods
Contact author(s)
bpf @ zurich ibm com
2006-02-06: received
Short URL
Creative Commons Attribution


      author = {Birgit Pfitzmann and Matthias Schunter and Michael Waidner},
      title = {Reactively Simulatable Certified Mail},
      howpublished = {Cryptology ePrint Archive, Paper 2006/041},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.