On the Existence of Unconditionally Privacy-Preserving Auction Protocols

ABSTRACT

We investigate whether it is possible to preserve privacy in sealed-bid auctions to a maximal extent. In particular, this paper focuses on <it>unconditional full privacy</it>, i.e., privacy that relies neither on trusted third parties (like auctioneers), nor on computational intractability assumptions (like the hardness of factoring). These constraints imply a scenario in which bidders exchange messages according to some predefined protocol in order to jointly determine the auction outcome without revealing any additional information. It turns out that the first-price sealed-bid auction can be emulated by an unconditionally fully private protocol. However, the protocol's round complexity is exponential in the bid size, and there is no more efficient protocol. On the other hand, we prove the impossibility of privately emulating the second-price sealed-bid auction for more than two bidders. This impossibility holds even when relaxing various privacy constraints such as allowing the revelation of all but one losing bid (while maintaining anonymity) or allowing the revelation of the second highest bidder's identity.

REFERENCES

• 1: Masayuki Abe , Koutarou Suzuki, M+1-st Price Auction Using Homomorphic Encryption, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.115-124, February 12-14, 2002
• 2: Bar-Yehuda, R., Chor, B., and Kushilevitz, E. 1990. Privacy, additional information, and communication. In <it>Proceedings of the 5th IEEE Conference on Structure in Complexity Theory</it>. 55--65.
• 3: Olivier Baudron , Jacques Stern, Non-interactive Private Auctions, Proceedings of the 5th International Conference on Financial Cryptography, p.364-378, February 19-22, 2002
• 4: Amos Beimel , Tal Malkin , Silvio Micali, The All-or-Nothing Nature of Two-Party Secure Computation, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.80-97, August 15-19, 1999
• 5: 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]
• 6: Josh Cohen Benaloh, Secret sharing homomorphisms: keeping shares of a secret secret, Proceedings on Advances in cryptology---CRYPTO '86, p.251-260, January 1987, Santa Barbara, California, United States
• 7: Brandt, F. 2002. Secure and private auctions without auctioneers. Tech. rep. FKI-245-02, Department for Computer Science, Technical University of Munich. ISSN 0941-6358.
• 8: Brandt, F. 2003. Fully private auctions in a constant number of rounds. In <it>Proceedings of the 7th Annual Conference on Financial Cryptography (FC'03)</it>, R. N. Wright, Ed. Lecture Notes in Computer Science, vol. 2742. Springer-Verlag, 223--238.
• 9: Felix Brandt, How to obtain full privacy in auctions, International Journal of Information Security, v.5 n.4, p.201-216, September 2006 [doi>10.1007/s10207-006-0001-y]
• 10: Brandt, F. and Sandholm, T. 2005. Efficient privacy-preserving protocols for multi-unit auctions. In <it>Proceedings of the 9th International Conference on Financial Cryptography and Data Security (FC'05)</it>, A. Patrick and M. Yung, Eds. Lecture Notes in Computer Science, vol. 3570. Springer-Verlag, 298--312.
• 11: Christian Cachin, Efficient private bidding and auctions with an oblivious third party, Proceedings of the 6th ACM conference on Computer and communications security, p.120-127, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319726]
• 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: Chor, B., Geréb-Graus, M., and Kushilevitz, E. 1994. On the structure of the privacy hierarchy. <it>J. Crypto. 7,</it> 1, 53--60.
• 14: B. Chor , E. Kushilevitz, A zero-one law for Boolean privacy, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.62-72, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73013]
• 15: 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]
• 16: Oded Goldreich, Foundations of Cryptography: Volume 1, Cambridge University Press, New York, NY, 2006
• 17: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 18: Michael Harkavy , J. D. Tygar , Hiroaki Kikuchi, Electronic auctions with private bids, Proceedings of the 3rd conference on USENIX Workshop on Electronic Commerce, p.6-6, August 31-September 03, 1998, Boston, Massachusetts
• 19: Juels, A. and Szydlo, M. 2002. A two-server, sealed-bid auction protocol. In <it>Proceedings of the 6th Annual Conference on Financial Cryptography (FC'02)</it>, M. Blaze, Ed. Lecture Notes in Computer Science, vol. 2357. Springer-Verlag, 72--86.
• 20: Hiroaki Kikuchi, (M+1)st-Price Auction Protocol, Proceedings of the 5th International Conference on Financial Cryptography, p.351-363, February 19-22, 2002
• 21: Kikuchi, H., Harkavy, M., and Tygar, J. D. 1998. Multi-round anonymous auction protocols. In <it>Proceedings of the 1st IEEE Workshop on Dependable and Real-Time E-Commerce Systems</it>. 62--69.
• 22: Krishna, V. 2002. <it>Auction Theory</it>. Academic Press.
• 23: Kushilevitz, E. 1989. Privacy and communication complexity. In <it>Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS'89)</it>. IEEE Computer Society Press, 416--421.
• 24: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 25: Lipmaa, H., Asokan, N., and Niemi, V. 2002. Secure Vickrey auctions without threshold trust. In <it>Proceedings of the 6th Annual Conference on Financial Cryptography (FC'02)</it>, M. Blaze, Ed. Lecture Notes in Computer Science, vol. 2357. Springer-Verlag, 87--101.
• 26: Natalia López , Manuel Núñez , Ismael Rodríguez , Fernando Rubio, Improving privacy in Vickrey auctions, ACM SIGecom Exchanges, v.5 n.1, p.1-12, July, 2004 [doi>10.1145/1120694.1120696]
• 27: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 28: Nurmi, H. and Salomaa, A. 1993. Cryptographic protocols for Vickrey auctions. <it>Group Decision and Negotiation 2</it>, 363--373.
• 29: Peng, K., Boyd, C., Dawson, E., and Viswanathan, K. 2002. Non-interactive auction scheme with strong privacy. In <it>Proceedings of the 5th International Conference on Information Security and Cryptology (ICISC'02)</it>. Lecture Notes in Computer Science, vol. 2587. Springer-Verlag, 407--420.
• 30: Ryan Porter , Yoav Shoham, On cheating in sealed-bid auctions, Decision Support Systems, v.39 n.1, p.41-54, March 2005 [doi>10.1016/j.dss.2004.08.006]
• 31: Rodríguez, I. and López, N. 2006. Analyzing the privacy of a Vickrey auction mechanism. <it>Int. J. E-Busin. Resear. 2,</it> 3, 17--27.
• 32: Rothkopf, M. H. and Harstad, R. M. 1995. Two models of bid-taker cheating in Vickrey auctions. <it>J. Busin. 68,</it> 2, 257--267.
• 33: Rothkopf, M. H., Teisberg, T. J., and Kahn, E. P. 1990. Why are Vickrey auctions rare? <it>J. Politi. Econo. 98,</it> 1, 94--109.
• 34: Kazue Sako, An Auction Protocol Which Hides Bids of Losers, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.422-432, January 18-20, 2000
• 35: Tuomas Sandholm, Issues in computational Vickrey auctions, International Journal of Electronic Commerce, v.4 n.3, p.107-129, March 2000
• 36: Sandholm, T. and Boutilier, C. 2006. Preference elicitation in combinatorial auctions. In <it>Combinatorial Auctions</it>, P. Cramton, Y. Shoham, and R. Steinberg, Eds. MIT Press, Chapter 10, 233--263.
• 37: Vickrey, W. 1961. Counter speculation, auctions, and competitive sealed tenders. <it>J. Finance 16,</it> 1, 8--37.
• 38: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

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

Keywords:
auctions, multiparty computation