Breaking and repairing optimistic fair exchange from PODC 2003

ABSTRACT

In PODC 2003, Park, Chong, Siegel and Ray [22] 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 [22] 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 [6], we obtain an efficient and provably secure (in the random oracle model) fair exchange protocol, which is based on GDH signatures [9].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 [8] and two-signatures, both of which are sufficient for fair exchange.

REFERENCES

• 1: N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. In K. Nyberg, editor, Advances in Cryptology---EUROCRYPT~98, volume 1403 of Lecture Notes in Computer Science, pages 591--606. Springer-Verlag, May~31--June~4 1998.
• 2: N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. IEEE Journal on Selected Areas in Communication, 18(4):593--610, 2000.
• 3: Giuseppe Ateniese, Efficient verifiable encryption (and fair exchange) of digital signatures, Proceedings of the 6th ACM conference on Computer and communications security, p.138-146, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319728]
• 4: F. Bao, R. Deng, and W. Mao. Efficient and practical fair exchange protocols with off-line TTP. In Proceedings of the IEEE Symposium on Security and Privacy, pages 77--85, 1998.
• 5: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 6: Alexandra Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.31-46, January 06-08, 2003
• 7: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 8: D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In E. Biham, editor, Advances in Cryptology---EUROCRYPT 2003, Lecture Notes in Computer Science, pages 416--432. Springer-Verlag, 4 May--8 May 2003.
• 9: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 10: Jan Camenisch , Ivan Damgård, Verifiable Encryption, Group Encryption, and Their Applications to Separable Group Signatures and Signature Sharing Schemes, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.331-345, December 03-07, 2000
• 11: J. Camenisch and A. Lysyanskaya. Signature schemes with efficient protocols. In Conference on Security in Communication Networks (SCN), 2002.
• 12: D. Chaum. Designated confirmer signatures. In A. De Santis, editor, Advances in Cryptology---EUROCRYPT~94, volume 950 of Lecture Notes in Computer Science, pages 86--91. Springer-Verlag, 1995, 9--12 May 1994.
• 13: J.-S. Coron and D. Naccache. Boneh et al's k-element aggregate extraction assumption is equivalent to the Diffie-Hellman assumption. In C. Laih, editor, Advances in Cryptology---ASIACRYPT-2003, Taipei, Taiwan, Nov 30--Dec 4, 2003. Springer-Verlag.
• 14: Y. Desmedt, editor. 6th International Workshop on Practice and Theory in Public Key Cryptosystems --- PKC 2003, volume 2567 of Lecture Notes in Computer Science. Springer-Verlag, Jan. 2003.
• 15: Yevgeniy Dodis, Efficient Construction of (Distributed) Verifiable Random Functions, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.1-17, January 06-08, 2003
• 16: Craig Gentry , Alice Silverberg, Hierarchical ID-Based Cryptography, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.548-566, December 01-05, 2002
• 17: Antoine Joux, A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.385-394, July 02-07, 2000
• 18: A. Joux and K. Nguyen. Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. IACR E-print Archive. Available from http://eprint.iacr.org/2001/003/, 2001.
• 19: Neal Koblitz, A course in number theory and cryptography, Springer-Verlag New York, Inc., New York, NY, 1987
• 20: Anna Lysyanskaya, Unique Signatures and Verifiable Random Functions from the DH-DDH Separation, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.597-612, August 18-22, 2002
• 21: Silvio Micali , Kazuo Ohta , Leonid Reyzin, Accountable-subgroup multisignatures: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502017]
• 22: Jung Min Park , Edwin K. P. Chong , Howard Jay Siegel, Constructing fair-exchange protocols for E-commerce via distributed computation of RSA signatures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.172-181, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872060]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Distributed commercial transactions
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

General Terms:
Algorithms, Design, Security, Theory

Keywords:
digital signatures, fair exchange, multisignatures, verifiably committed signatures, verifiably encrypted signatures