Paper 2003/146

Breaking and Repairing Optimistic Fair Exchange from PODC 2003

Yevgeniy Dodis and Leonid Reyzin


In PODC 2003, Park, Chong, Siegel and Ray [PCSR03] proposed an optimistic protocol for fair exchange, based on RSA signatures. We show that their protocol is *totally breakable* already in the registration phase: the honest-but-curious arbitrator can easily determine the signer's secret key. On a positive note, the authors of [PCSR03] informally introduced a connection between fair exchange and "sequential two-party multisignature schemes" (which we call two-signatures), but used an insecure two-signature scheme in their actual construction. Nonetheless, we show that this connection *can* be properly formalized to imply *provably secure* fair exchange protocols. By utilizing the state-of-the-art non-interactive two-signature of Boldyreva (PKC 2003), we obtain an efficient and provably secure (in the random oracle model) fair exchange protocol, which is based on GDH signatures of Boneh, Lynn and Shacham (Asiacrypt 2001). Of independent interest, we introduce a unified model for non-interactive fair exchange protocols, which results in a new primitive we call *verifiably committed signatures*. Verifiably committed signatures generalize (non-interactive) verifiably encrypted signatures and two-signatures, both of which are sufficient for fair exchange.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. DRM 2003
fair exchangeoptimistic protocolsmulti-signaturesverifiably encrypted signaturescontract signingGDH signaturescommitted signatures
Contact author(s)
dodis @ cs nyu edu
2003-09-03: last of 3 revisions
2003-07-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yevgeniy Dodis and Leonid Reyzin},
      title = {Breaking and Repairing Optimistic Fair Exchange from {PODC} 2003},
      howpublished = {Cryptology ePrint Archive, Paper 2003/146},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.