Efficient verifiable encryption (and fair exchange) of digital signatures

ABSTRACT

A fair exchange protocol allows two users to exchange items so that either each user gets the other's item or neither user does. In [2], verifiable encryption is introduced as a primitive that can be used to build extremely efficient fair exchange protocols where the items exchanged represent digital signatures. Such protocols may be used to digitally sign contracts.This paper presents new simple schemes for verifiable encryption of digital signatures. We make use of a trusted third party (TTP) but in an optimistic sense, i.e., the TTP takes part in the protocol only if one user cheats or simply crashes. The performance of our schemes significantly surpasses that of prior art.

REFERENCES

• 1: N. Asokan , Matthias Schunter , Michael Waidner, Optimistic protocols for fair exchange, Proceedings of the 4th ACM conference on Computer and communications security, p.7-17, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266426]
• 2: N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. In Advances m Cryptology - EUROCRYPT 'g8, volume 1403 of Lecture Notes in Computer Science, pages 591-606, Springer-Verlag, 1998.
• 3: N. Asokan, V. Shoup, and M. Waidner. Asynchronous Protocols for Optimistic Fair Exchange. In IEEE Syraposura on Security and Privacy, Oakland, California, 1998.
• 4: F. Bao, R. H. Dead, and W. Mac. Efficient and Practical Fair Exchange Protocols with Off-line TTP. In IEEE Symposium on Security and Privacy, Oakland, California, 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: M. Ben-Or, O. Goldreich, S. Micali, and R. Rivest. A fair protocol for signing contracts. In IEEE Transactions on Information Theorid, IT-36(1), pp. 40-46, 1990
• 7: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 8: J. Camenisch and I. B. Damgnrd. Verifiable EnctTption and Applications to Group Signatures and Signature Sharing. BRICS Technical Report, RS-98-32.
• 9: Jan Camenisch , Markus Michels, A Group Signature Scheme with Improved Efficiency, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.160-174, October 18-22, 1998
• 10: J. Camenisch and M. Micheis. A group signature scheme based on an RSA-variant. Tech. Report RS-98-27, BRICS, Aarhus, November 1998. An earlier version appears in {9}.
• 11: J. Camenisch and M. Miehels. Proving in zero-knowledge that a number is the product of two safe primes. In Advances In Cryptology - EUROCRYPT '99, Lecture Notes in Computer Science, Springer-Verlag. To appear, 1999.
• 12: Jan Camenisch , Markus Michels, Separability and Efficiency for Generic Group Signature Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.413-430, August 15-19, 1999
• 13: A. Chan, Y. Frankel and Y. Tsiounis. Easy come - easy go divisible cash. In Advances in Cryptology - EURO- CRYPT '98, volume 1403 of Lecture Notes in Computer Sczence, pages 561-575, Springer-Verlag, 1998. Updated and corrected version available as GTE Technical Report.
• 14: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 15: Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, Proceedings of the 6th ACM conference on Computer and communications security, p.46-51, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319716]
• 16: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 17: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 18: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 19: R. Gennaro, S. Halevi, and T. Rabin. Secure signatures, without trees or random oracles. In Advances m Cryptology - EUROCRYPT '99, volume 1592 of Lecture Notes m Computer Sczence, pages 123-139, Springer-Verlag, 1999
• 20: L. C. Guillou , J. J. Quisquater, A “paradoxical” identity-based signature scheme resulting from zero-knowledge, Proceedings on Advances in cryptology, p.216-231, February 1990, Santa Barbara, California, United States
• 21: K. S. McCurley, A key distribution system equivalent to factoring, Journal of Cryptology, v.1 n.2, p.95-105, Aug. 1988 [doi>10.1007/BF02351718]
• 22: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 23: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 24: T. Okamoto and S. Uchiyama. A New Public-Key Cryptosystem as Secure as Factoring. In Advances in Cryptology - EUROCRYPT '98, volume 1403 of Lecture Notes in Computer Scsence, pages 308-318, Springer-Verlag, 1998.
• 25: D. Pointcheval and J. Stern. Security proofs for signature schemes. In Advances in Cryptology - EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 387-398, Springer-Verlag, 1996.
• 26: G. Poupard and J. Stern. Security anMysis of a practical "on the fly" authentication and signature generation. In Advances in Cryptology - EUROCRYPT "98, volume 1403 of Lecture Notes in Computer Science, pages 422-436, Springer-Verlag, 1998.
• 27: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 28: C.P. Schnorr. Efficient signature generation by smart-cards. Journal of Cryptology , 4(3):161-174, 1991.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Payment schemes

General Terms:
Economics, Human Factors, Reliability, Security, Theory, Verification

Keywords:
contract signing problem, digital signatures, fair exchange, proof of knowledge, public-key cryptography, verifiable encryption