Privacy preserving auctions and mechanism design

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Privacy preserving auctions and mechanism design

Full text

Pdf (278 KB)

Source

Electronic Commerce archive
Proceedings of the 1st ACM conference on Electronic commerce table of contents

Denver, Colorado, United States

Pages: 129 - 139

Year of Publication: 1999

ISBN:1-58113-176-3

Authors

Moni Naor	Dept. of Computer Science and Applied Math, Weizmann Institute of Science, Rehovot 76100, Israel
Benny Pinkas	Dept. of Computer Science and Applied Math, Weizmann Institute of Science, Rehovot 76100, Israel
Reuban Sumner	Dept. of Computer Science and Applied Math, Weizmann Institute of Science, Rehovot 76100, Israel

Sponsor

SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 108, Citation Count: 48

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/336992.337028 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	http://auction.eecs.umich.edu
	2	D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100287]
	3	Mihir Bellare , Anand Desai , David Pointcheval , Phillip Rogaway, Relations Among Notions of Security for Public-Key Encryption Schemes, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.26-45, August 23-27, 1998
	4	Mihir Bellare , Silvio Micali, Non-interactive oblivious transfer and applications, Proceedings on Advances in cryptology, p.547-557, July 1989, Santa Barbara, California, United States
	5	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]
	6	K. Chui and R. Zwick, "Auction on the Internet - A preliminary study", manuscript, 1999. Available at http://home.ust.hk/mkzwick/Internet_Auction.html
	7	E. Clarke, "Multiparty pricing of public goods", Public Choice, 11:17-23, 1971.
	8	Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
	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	Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
	11	R. Engelbrecht-Wiggans and C. M. Kahn, "Protecting the winner: second price vs. ascending bid auctions", Economic Letters, Vol. 35, 1991, 243-248.
	12	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]
	13	Uri Feige , Joe Killian , Moni Naor, A minimal model for secure computation (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.554-563, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195408]
	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	J. Glazer and A. Rubinstein, "Motives and implementation: on the design of mechanisms to elicit opinions", J. of Economic Theory 79, 157-173, 1998.
	16	O. Goldreich, Secure Multi-Party Computation (working draft) Version 1.1, 1998. Available at http://philby.ucsd.edu/books.html
	17	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	18	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]
	19	T. Groves, "Incentives in teams", Econometrica, 41:617-631, 1973.
	20	Dan Gusfield , Robert W. Irving, The stable marriage problem: structure and algorithms, MIT Press, Cambridge, MA, 1989
	21	M. Harkavy, J. D.Tygar and H. Kikuchi, "Electronic auctions with private bids", 3rd USENIX Workshop on Electronic Commerce, pp. 61-73, 1999.
	22	Q. Huai and T. Sandholm, "Mobile Agents in an Electronic Auction House", Mobile Agents in the Context of Competition and Cooperation (MAC3-workshop), 1999.
	23	R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
	24	N. Kfir-Dahav, D. Monderer and M. Tennenholtz, "Mechanism design for resource bounded agents", 1998.
	25	M. Kumar and S. I. Feldman, "Internet auctions", 3rd USENIX Workshop on Electronic Commerce, 1999.
	26	Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
	27	J. K. MacKie-Mason and H. R. Varian, "Generalized Vickrey auctions", 1994.
	28	D. Monderer and M. Tennenholtz, "K-Price auctions", Working Paper, 1998.
	29	D. Monderer and M. Tennenholtz, "Internet auctions", Working Paper, 1998.
	30	Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
	31	A. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press, 1994.
	32	M. O. Rabin, "How to exchange secrets by oblivious transfer", Tech. Memo TR-81, Aiken Computation Laboratory, 1981.
	33	A. E. Roth and M. A. Sotomayor, Two-Sided Matching : A Study in Game-Theoretic Modeling and Analysis, Cambridge Univ Press, 1990.
	34	Stuart G. Stubblebine , Paul F. Syverson, Fair On-Line Auctions without Special Trusted Parties, Proceedings of the Third International Conference on Financial Cryptography, p.230-240, February 01, 1999
	35	H. R. Varian, "Economic mechanism design for computerized agents", First USENIX Workshop on Electronic Commerce, 1995.
	36	D. Vickrey,"Counter speculation, auctions, and competitive sealed tenders", Journal of Finance, March 1961, pp. 9-37.
	37	W. Walsh, M. Wellman, P. Wurman and J.K. MacKie- Mason, "Auction protocols for decentralized scheduling", 18th Int. Conf. on Distributed Computing Sys., 1998.
	38	M. Wellman and P. Wurman, "Real time issues for Internet auctions", First IEEE Workshop on Dependable and Real-Time E-commerce Systems, 1998.
	39	Peter R. Wurman , William E. Walsh , Michael P. Wellman, Flexible double auctions for electionic commerce: theory and implementation, Decision Support Systems, v.24 n.1, p.17-27, Nov. 1998 [doi>10.1016/S0167-9236(98)00060-8]
	40	A.C. Yao, "How to generate and exchange secrets", Proc. of the 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 162-167.

CITED BY 49

	Wei Jiang , Chris Clifton , Murat Kantarcıoğlu, Transforming semi-honest protocols to ensure accountability, Data & Knowledge Engineering, v.65 n.1, p.57-74, April, 2008
	Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece
	Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
	Yuko Sakurai , Makoto Yokoo , Atsushi Iwasaki , Koutarou Suzuki, Secure Keyword Auction: Preserving Privacy of Bidding Prices and CTRs, Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, p.419-422, September 15-18, 2009
	Yuji Watanabe , Hideki Imai, Reducing the round complexity of a sealed-bid auction protocol with an off-line TTP, Proceedings of the 7th ACM conference on Computer and communications security, p.80-86, November 01-04, 2000, Athens, Greece
	Makoto Yokoo , Koutarou Suzuki, Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	Sergio Rajsbaum, ACM SIGACT news distributed computing column 9, ACM SIGACT News, v.33 n.4, December 2002
	Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Athena Vakali , Lefteris Angelis , Dimitra Pournara, Internet based auctions: a survey on models and applications, ACM SIGecom Exchanges, v.2 n.2, p.6-15, Spring, 2001
	Jaideep Vaidya , Chris Clifton, Leveraging the "Multi" in secure multi-party computation, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC
	Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Moni Naor, Cryptography and mechanism design, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	Keith Frikken , Mikhail Atallah , Chen Zhang, Privacy-preserving credit checking, Proceedings of the 6th ACM conference on Electronic commerce, p.147-154, June 05-08, 2005, Vancouver, BC, Canada
	Benny Pinkas, Cryptographic techniques for privacy-preserving data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.12-19, December 2002
	Ryan Porter , Yoav Shoham, On cheating in sealed-bid auctions, Decision Support Systems, v.39 n.1, p.41-54, March 2005
	Luis von Ahn , Nicholas Hopper , John Langford, Covert two-party computation, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Jiangtao Li , Ninghui Li, Policy-hiding access control in open environment, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Sumit Joshi , Yu-An Sun , Poorvi L. Vora, The privacy cost of the second-chance offer, Proceedings of the 2005 ACM workshop on Privacy in the electronic society, November 07-07, 2005, Alexandria, VA, USA
	Dov Monderer , Moshe Tennenholtz, k-Implementation, Proceedings of the 4th ACM conference on Electronic commerce, p.19-28, June 09-12, 2003, San Diego, CA, USA
	Ismael Rodriguez , Natalia López, Implementing private Vickrey auctions, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Ryan Porter , Yoav Shoham, On cheating in sealed-bid auctions, Proceedings of the 4th ACM conference on Electronic commerce, p.76-84, June 09-12, 2003, San Diego, CA, USA
	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
	Jarrod Trevathan, Security, anonymity and trust in electronic auctions, Crossroads, v.11 n.3, p.2-2, Spring 2005
	Kris Bubendorfer, Improving resource utilisation in market oriented grid management and scheduling, Proceedings of the 2006 Australasian workshops on Grid computing and e-research, p.25-31, January 16-19, 2006, Hobart, Tasmania, Australia
	Ivan Damgard , Martin Geisler , Mikkel Kroigard, Homomorphic encryption and secure comparison, International Journal of Applied Cryptography, v.1 n.1, p.22-31, February 2008
	Louis Kruger , Somesh Jha , Eu-Jin Goh , Dan Boneh, Secure function evaluation with ordered binary decision diagrams, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
	Sven Laur , Helger Lipmaa , Taneli Mielikäinen, Cryptographically private support vector machines, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Liad Blumrosen , Michal Feldman, Implementation with a bounded action space, Proceedings of the 7th ACM conference on Electronic commerce, p.62-71, June 11-15, 2006, Ann Arbor, Michigan, USA
	Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
	Tuomas Sandholm , Andrew Gilpin, Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Laura Kang , David C. Parkes, Passive verification of the strategyproofness of mechanisms in open environments, Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet, August 13-16, 2006, Fredericton, New Brunswick, Canada
	D. C. Parkes , M. O. Rabin , S. M. Shieber , C. A. Thorpe, Practical secrecy-preserving, verifiably correct and trustworthy auctions, Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet, August 13-16, 2006, Fredericton, New Brunswick, Canada
	Rajiv T. Maheswaran , Jonathan P. Pearce , Emma Bowring , Pradeep Varakantham , Milind Tambe, Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications, Autonomous Agents and Multi-Agent Systems, v.13 n.1, p.27-60, July 2006
	Felix Brandt , Tuomas Sandholm, (Im)Possibility of Unconditionally Privacy-Preserving Auctions, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.810-817, July 19-23, 2004, New York, New York
	Felix Brandt, Social choice and preference protection: towards fully private mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Felix Brandt , Tuomas Sandholm, On the Existence of Unconditionally Privacy-Preserving Auction Protocols, ACM Transactions on Information and System Security (TISSEC), v.11 n.2, p.1-21, March 2008
	Shuo Zheng , Luke McAven , Yi Mu, First price sealed bid auction without auctioneers, Proceedings of the 2007 international conference on Wireless communications and mobile computing, August 12-16, 2007, Honolulu, Hawaii, USA
	Justin Brickell , Donald E. Porter , Vitaly Shmatikov , Emmett Witchel, Privacy-preserving remote diagnostics, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA
	Edith Elkind, Designing and learning optimal finite support auctions, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.736-745, January 07-09, 2007, New Orleans, Louisiana
	Konstantinos Chatzikokolakis , Catuscia Palamidessi, A framework for analyzing probabilistic protocols and its application to the Partial Secrets Exchange, Theoretical Computer Science, v.389 n.3, p.512-527, December, 2007
	Jan Camenisch , Thomas Groß , Thomas S. Heydt-Benjamin, Rethinking accountable privacy supporting services: extended abstract, Proceedings of the 4th ACM workshop on Digital identity management, October 31-31, 2008, Alexandria, Virginia, USA
	Kay-Yut Chen , Tad Hogg, Experiments with probabilistic quantum auctions, Quantum Information Processing, v.7 n.4, p.139-152, August 2008
	Phillip G. Bradford , Sunju Park , Michael H. Rothkopf , Heejin Park, Protocol completion incentive problems in cryptographic Vickrey auctions, Electronic Commerce Research, v.8 n.1-2, p.57-77, June 2008
	Assaf Ben-David , Noam Nisan , Benny Pinkas, FairplayMP: a system for secure multi-party computation, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA
	David C. Parkes , Michael O. Rabin , Stuart M. Shieber , Christopher Thorpe, Practical secrecy-preserving, verifiably correct and trustworthy auctions, Electronic Commerce Research and Applications, v.7 n.3, p.294-312, November, 2008
	Jan Camenisch , Thomas Groß, Efficient attributes for anonymous credentials, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA
	Florian Kerschbaum , Daniel Dahlmeier , Axel Schröpfer , Debmalya Biswas, On the practical importance of communication complexity for secure multi-party computation protocols, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Dov Monderer , Moshe Tennenholtz, K-implementation, Journal of Artificial Intelligence Research, v.21 n.1, p.37-62, January 2004