Simple and fast optimistic protocols for fair electronic exchange

ABSTRACT

Assume each of two parties has something the other wants. Then, a fair exchange is an electronic protocol guaranteeing that either both parties get what they want, or none of them does. Protocols relying on traditional trusted parties easily guarantee such exchanges, but are inefficient (because a trusted party must be part of every execution) and expensive (because trusted parties want to be paid for each execution).In this paper we• Quickly review fair exchanges that are optimistic, that is, relying on a trusted party that (1) does not participate at all in an honest execution, and yet (2) guarantees the fairness of all executions; and• Present some older and surprisingly simple optimistic protocols for fair certified e-mail and contract signing that never appeared in the scientific literature.

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: Asokan, N., Shoup, V., and Waidner, M. Optimistic Fair Exchange of Digital Signatures. IEEE Journal on Selected Areas of Communication, vol. 18, pp. 591--610, April 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: Giuseppe Ateniese , Cristina Nita-Rotaru, Stateless-Recipient Certified E-Mail System Based on Verifiable Encryption, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.182-199, February 18-22, 2002
• 5: Ban, F., Deng, R. H., and Mao, W. Efficient and Practical Fair Exchange Protocols. IEEE Symp. On Security and Privacy, pp. 77--85, 1998.
• 6: Ben-Or, M., Goldreich, O., Micali, S., and Rivest, R. A Fair Protocol for Signing Contracts. IEEE Transactions on Information Theory 36/1 (1990) 40--46.
• 7: Blum, M. Three Applications of the Oblivious Transfer: Part I: Coin Flipping by the telephone; Part II: How to Exchange Secrets; Part III: How to Send Certified Electronic Mail. Manuscript. University of California, Berkeley, 1981. (Also described in Cryptographers gather to discuss Research. By G. Kolata. Science, Vol. 214, November 6, 1981.)
• 8: Christian Cachin , Jan Camenisch, Optimistic Fair Secure Computation, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.93-111, August 20-24, 2000
• 9: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 10: Dolev, D., Dwork, D., and Naor, N. Non-Malleable Cryptography. Proc. 33rd Symposium on Foundations of Computer Science, IEEE, 1992.
• 11: 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]
• 12: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 13: Herzog, J., Liskov, M., and Micali, S. Plain-Text Awareness Via Key Registration. To appear, Proc. CRYPTO 2003.
• 14: Luby M., Micali, S., and Rackoff, C. How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. Proc. 24th ann. IEEE Symp. on Foundations of Computer Science, November 1983, Arizona, pp. 11--22
• 15: Micali, S. Simultaneous Electronic Transactions. U.S. Patent No. 5,666,420, continuation of application No. 408,551, filed March 21, 1995, issued September 9, 1997. (Also presented at the 1997 RSA Data Security Conference, San Francisco, January 1997--Not included in the printed version of the proceedings.)
• 16: Micali, S. Ideal Electronic Negotiations. U.S. Patent No. 5,615,269, filed February 22, 1996, issued March 25, 1997.
• 17: Pfitzmann, B., Schunter, M., and Waidner, M. Provably Secure Certified Mail. Tech Report RZ 3207 (93253), IBM Research Division, Zurich, Switzerland, February 2000.
• 18: Rabin, M. Transaction Protection by Beacons. Harvard Tech. Report 29--81, 1981. Subsequent version: JCSS 27(2) 1983.

INDEX TERMS

General Terms:
Algorithms, Legal Aspects, Reliability, Security, Theory

Keywords:
Optimistic Protocols, certified e-mail, contract signing, fair exchange, invisible trusted parties