Efficient private bidding and auctions with an oblivious third party

ABSTRACT

We describe a novel and efficient protocol for the following problem: A wants to buy some good from B if the price is less than a. B would like to sell, but only for more than b, and neither of them wants to reveal the secret bounds. Will the deal take place? Our solution uses an oblivious third party T who learns no information about a or b, not even whether a > b. The protocol needs only a single round of interaction, ensures fairness, and is not based on general circuit evaluation techniques. It uses a novel construction, which combines homomorphic encryption with the &phgr;-hiding assumption and which may be of independent interest. Applications include bargaining between two parties and secure and efficient auctions in the absence of a fully trusted auction service.

REFERENCES

• 1: M. Abadi , J. Feigenbaum, Secure circuit evaluation, Journal of Cryptology, v.2 n.1, p.1-12, 1990 [doi>10.1007/BF02252866]
• 2: 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]
• 3: ASOKAN: N., SHOUP, V., AND WAtDNER, M. Optimistic fair exchange of digital signatures. In Advances in Cryptology: EUROCRYPT '98 (1998), K. Nyberg, Ed., vol. 1403 of Lecture Notes m Computer Science, Springer.
• 4: BEAM, C., AND SEGEV, A. Auctions on the internet: A field study. Working Paper 98-WP-1032, Fisher Center for Management and Information Technology, Haas School of Business, University of California, Berkeley, 1998.
• 5: B~AVER, D. Secure multiparty protocols and zeroknowledge proof systems tolerating a faulty minority. Journal of Cryp~oloyy 4, 2 (1991), 75-122.
• 6: BEN-OR, M., GOLDREICH, O., MICALI, S., AND RJVEST, R. L. A fair protocol for signing contracts. IEEE :l~nsact~ons on lnforrnatton Theory 36, 1 (Jan. 1990), 40-46.
• 7: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 8: BENALOH, J. Dense probabilisLic encryption. In Proc. Workshop on Selected Areas of Cryptography (Kingston, ON, May 1994), pp. 120-128.
• 9: CACH~N, C. Efficient private bidding and auctions with an oblivious third party. IBM Research Report, RZ 3131, 1999.
• 10: CACHIN, C., MICALI, S., AND STADLER, M. Computationally private information retrieval with polylogarithmic communication. In Advances in Crypiology: EUROCRYPT '99 (1999), J. Stern, Ed., vol. 1592 of Lecture Notes in Computer Sczence, Springer, pp. 402- 414.
• 11: CANETTI, R. Security and composition of multi-party cryptographic protocols. Report 98-18, Theory of Cryptography Library, 1998.
• 12: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 13: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, 1987
• 14: Matthew K. Franklin , Michael K. Reiter, The Design and Implementation of a Secure Auction Service, IEEE Transactions on Software Engineering, v.22 n.5, p.302-312, May 1996 [doi>10.1109/32.502223 ]
• 15: Matthew K. Franklin , Michael K. Reiter, Fair exchange with a semi-trusted third party (extended abstract), Proceedings of the 4th ACM conference on Computer and communications security, p.1-5, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266424]
• 16: GOLDREICH, O. Secure multi-party computation. Manuscript, 1998. (Version 1.1).
• 17: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 18: GOLDWASSER, S., AND MICALI, S. Probabilistic encryption. Journal of Computer and System Sciences 28 (~9s4), 270-299.
• 19: I-}ARKAVY, }VI., TYOAR, D., AND K1KUCHI, H. Electronic auctions with private bids. In Proc. 3rd USENIX Workshop on Electromc Commerce (Boston, 1998).
• 20: KUMAR, M., AND Ft!~LDMAN, S. I. Internet auctions. In Proc. 3rd USENIX Workshop on Electronic Commerce (Boston, 1998).
• 21: MICAh.I, S. Certified e-mail with invisible post offices. invited presentation at the RSA '97 coaference, 1997.
• 22: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 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: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 25: YAO, A. C.-C. Protocols for secure computation. In Prac. ~3rd IEEE Symposium on Foundations of Computer Science. (FOGS) (1982), pp. 160~t64.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

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

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY

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

Keywords:
&Fgr;-hiding assumption, auctions, bidding, homomorphic cryptosytems, multiparty computation, private information retrieval