{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T20:44:37Z","timestamp":1759092277805,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BR 2312\/1-1"],"award-info":[{"award-number":["BR 2312\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-9800994ITR IIS-0081246ITR IIS-0121678ITR IIS-0427858"],"award-info":[{"award-number":["IIS-9800994ITR IIS-0081246ITR IIS-0121678ITR IIS-0427858"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-9800994ITR IIS-0081246ITR IIS-0121678ITR IIS-0427858"],"award-info":[{"award-number":["IIS-9800994ITR IIS-0081246ITR IIS-0121678ITR IIS-0427858"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2008,3]]},"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.<\/jats:p>","DOI":"10.1145\/1330332.1330338","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["On the Existence of Unconditionally Privacy-Preserving Auction Protocols"],"prefix":"10.1145","volume":"11","author":[{"given":"Felix","family":"Brandt","sequence":"first","affiliation":[{"name":"University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tuomas","family":"Sandholm","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"<\/scp>","author":"Abe M.","year":"2002","unstructured":" Abe , M. and Suzuki , K . <\/scp> 2002 . M+1-st price auction using homomorphic encryption. In <it>Proceedings of the 5th International Conference on Public Key Cryptography (PKC'02)<\/it>. Lecture Notes in Computer Science, vol. 2274 . Springer-Verlag , 115--224. Abe, M. and Suzuki, K.<\/scp> 2002. M+1-st price auction using homomorphic encryption. In <it>Proceedings of the 5th International Conference on Public Key Cryptography (PKC'02)<\/it>. Lecture Notes in Computer Science, vol. 2274. Springer-Verlag, 115--224."},{"key":"e_1_2_1_2_1","volume-title":"<\/scp>","author":"Bar-Yehuda R.","year":"1990","unstructured":" Bar-Yehuda , R. , Chor , B. , and Kushilevitz , E . <\/scp> 1990 . Privacy, additional information, and communication. In <it>Proceedings of the 5th IEEE Conference on Structure in Complexity Theory <\/it>. 55--65. Bar-Yehuda, R., Chor, B., and Kushilevitz, E.<\/scp> 1990. Privacy, additional information, and communication. In <it>Proceedings of the 5th IEEE Conference on Structure in Complexity Theory<\/it>. 55--65."},{"key":"e_1_2_1_3_1","volume-title":"<\/scp>","author":"Baudron O.","year":"2001","unstructured":" Baudron , O. and Stern , J . <\/scp> 2001 . Non-interactive private auctions. In <it>Proceedings of the 5th Annual Conference on Financial Cryptography (FC'01)<\/it>. Lecture Notes in Computer Science, vol. 2339 . Springer-Verlag , 300--313. Baudron, O. and Stern, J.<\/scp> 2001. Non-interactive private auctions. In <it>Proceedings of the 5th Annual Conference on Financial Cryptography (FC'01)<\/it>. Lecture Notes in Computer Science, vol. 2339. Springer-Verlag, 300--313."},{"key":"e_1_2_1_4_1","volume-title":"<\/scp>","author":"Beimel A.","year":"1999","unstructured":" Beimel , A. , Malkin , T. , and Micali , S . <\/scp> 1999 . The all-or-nothing nature of two-party secure computation. In <it>Advances in Cryptology - Proceedings of the 19th Annual International Cryptology Conference (CRYPTO'99)<\/it>. Lecture Notes in Computer Science, vol. 1666 . Springer-Verlag , 80--97. Beimel, A., Malkin, T., and Micali, S.<\/scp> 1999. The all-or-nothing nature of two-party secure computation. In <it>Advances in Cryptology - Proceedings of the 19th Annual International Cryptology Conference (CRYPTO'99)<\/it>. Lecture Notes in Computer Science, vol. 1666. Springer-Verlag, 80--97."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_6_1","volume-title":"Lecture Notes in Computer Science","volume":"263","author":"Benaloh J.","year":"1987","unstructured":" Benaloh , J. <\/scp> 1987 . Secret sharing homomorphisms: Keeping shares of a secret secret. In <it>Advances in Cryptology---Proceedings of the 13th Annual International Cryptology Conference (CRYPTO'87)<\/it> . Lecture Notes in Computer Science , vol. 263 . Springer-Verlag, 251--260. Benaloh, J.<\/scp> 1987. Secret sharing homomorphisms: Keeping shares of a secret secret. In <it>Advances in Cryptology---Proceedings of the 13th Annual International Cryptology Conference (CRYPTO'87)<\/it>. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, 251--260."},{"volume-title":"Department for Computer Science","author":"Brandt F.","key":"e_1_2_1_7_1","unstructured":" Brandt , F. <\/scp> 2002. Secure and private auctions without auctioneers. Tech. rep. FKI-245-02 , Department for Computer Science , Technical University of Munich . ISSN 0941-6358. Brandt, F.<\/scp> 2002. Secure and private auctions without auctioneers. Tech. rep. FKI-245-02, Department for Computer Science, Technical University of Munich. ISSN 0941-6358."},{"volume-title":"Fully private auctions in a constant number of rounds. In <it>Proceedings of the 7th Annual Conference on Financial Cryptography (FC'03)<\/it>","author":"Brandt F.","key":"e_1_2_1_8_1","unstructured":" Brandt , F. <\/scp> 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. Brandt, F.<\/scp> 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-006-0001-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11507840_26"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/319709.319726"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_13_1","first-page":"53","article-title":"On the structure of the privacy hierarchy. <it>J","volume":"1","author":"Chor B.","year":"1994","unstructured":" Chor , B. , Ger\u00e9b-Graus , M. , and Kushilevitz , E. <\/scp> 1994 . On the structure of the privacy hierarchy. <it>J . Crypto. 7,<\/it> 1 , 53 -- 60 . Chor, B., Ger\u00e9b-Graus, M., and Kushilevitz, E.<\/scp> 1994. On the structure of the privacy hierarchy. <it>J. Crypto. 7,<\/it> 1, 53--60.","journal-title":"Crypto. 7,<\/it>"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73013"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.502223"},{"volume-title":"Basic Tools<\/it>","author":"Goldreich O.","key":"e_1_2_1_16_1","unstructured":" Goldreich , O. <\/scp> 2001. <it> Foundations of Cryptography : Volume 1 , Basic Tools<\/it> . Cambridge University Press . Goldreich, O.<\/scp> 2001. <it>Foundations of Cryptography: Volume 1, Basic Tools<\/it>. Cambridge University Press."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"key":"e_1_2_1_18_1","volume-title":"<\/scp>","author":"Harkavy M.","year":"1998","unstructured":" Harkavy , M. , Tygar , J. D. , and Kikuchi , H . <\/scp> 1998 . Electronic auctions with private bids. In <it>Proceedings of the 3rd USENIX Workshop on Electronic Commerce <\/it>. 61--74. Harkavy, M., Tygar, J. D., and Kikuchi, H.<\/scp> 1998. Electronic auctions with private bids. In <it>Proceedings of the 3rd USENIX Workshop on Electronic Commerce<\/it>. 61--74."},{"key":"e_1_2_1_19_1","volume-title":"<\/scp>","author":"Juels A.","year":"2002","unstructured":" Juels , A. and Szydlo , M . <\/scp> 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. Juels, A. and Szydlo, M.<\/scp> 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."},{"key":"e_1_2_1_20_1","series-title":"Lecture Notes in Computer Science","volume-title":"<it>Proceedings of the 5th Annual Conference on Financial Cryptography (FC'01)<\/it>","author":"Kikuchi H.","unstructured":" Kikuchi , H. <\/scp> 2001. (M+1)st-price auction protocol. In <it>Proceedings of the 5th Annual Conference on Financial Cryptography (FC'01)<\/it> . Lecture Notes in Computer Science , vol. 2339 . Springer-Verlag , 351--363. Kikuchi, H.<\/scp> 2001. (M+1)st-price auction protocol. In <it>Proceedings of the 5th Annual Conference on Financial Cryptography (FC'01)<\/it>. Lecture Notes in Computer Science, vol. 2339. Springer-Verlag, 351--363."},{"key":"e_1_2_1_21_1","volume-title":"<\/scp>","author":"Kikuchi H.","year":"1998","unstructured":" Kikuchi , H. , Harkavy , M. , and Tygar , J. D . <\/scp> 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. Kikuchi, H., Harkavy, M., and Tygar, J. D.<\/scp> 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."},{"key":"e_1_2_1_22_1","unstructured":"Krishna V.<\/scp> 2002. <it>Auction Theory<\/it>. Academic Press. Krishna V.<\/scp> 2002. <it>Auction Theory<\/it>. Academic Press."},{"volume-title":"Privacy and communication complexity. In <it>Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS'89)<\/it>","author":"Kushilevitz E.","key":"e_1_2_1_23_1","unstructured":" Kushilevitz , E. <\/scp> 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. Kushilevitz, E.<\/scp> 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."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_25_1","volume-title":"<\/scp>","author":"Lipmaa H.","year":"2002","unstructured":" Lipmaa , H. , Asokan , N. , and Niemi , V . <\/scp> 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. Lipmaa, H., Asokan, N., and Niemi, V.<\/scp> 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."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120694.1120696"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337028"},{"key":"e_1_2_1_28_1","volume-title":"<\/scp>","author":"Nurmi H.","year":"1993","unstructured":" Nurmi , H. and Salomaa , A . <\/scp> 1993 . Cryptographic protocols for Vickrey auctions. <it>Group Decision and Negotiation 2<\/it>, 363--373. Nurmi, H. and Salomaa, A.<\/scp> 1993. Cryptographic protocols for Vickrey auctions. <it>Group Decision and Negotiation 2<\/it>, 363--373."},{"key":"e_1_2_1_29_1","volume-title":"<\/scp>","author":"Peng K.","year":"2002","unstructured":" Peng , K. , Boyd , C. , Dawson , E. , and Viswanathan , K . <\/scp> 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. Peng, K., Boyd, C., Dawson, E., and Viswanathan, K.<\/scp> 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."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.dss.2004.08.006","article-title":"On cheating in sealed-bid auctions. <it>Decision","volume":"1","author":"Porter R.","year":"2005","unstructured":" Porter , R. and Shoham , Y. <\/scp> 2005 . On cheating in sealed-bid auctions. <it>Decision Supp. Syst. 39,<\/it> 1 , 41 -- 54 . Porter, R. and Shoham, Y.<\/scp> 2005. On cheating in sealed-bid auctions. <it>Decision Supp. Syst. 39,<\/it> 1, 41--54.","journal-title":"Supp. Syst. 39,<\/it>"},{"key":"e_1_2_1_31_1","first-page":"17","article-title":"Analyzing the privacy of a Vickrey auction mechanism. <it>Int","volume":"3","author":"Rodr\u00edguez I.","year":"2006","unstructured":" Rodr\u00edguez , I. and L\u00f3pez , N. <\/scp> 2006 . Analyzing the privacy of a Vickrey auction mechanism. <it>Int . J. E-Busin. Resear. 2,<\/it> 3 , 17 -- 27 . Rodr\u00edguez, I. and L\u00f3pez, N.<\/scp> 2006. Analyzing the privacy of a Vickrey auction mechanism. <it>Int. J. E-Busin. Resear. 2,<\/it> 3, 17--27.","journal-title":"J. E-Busin. Resear. 2,<\/it>"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1086\/296663"},{"key":"e_1_2_1_33_1","first-page":"94","article-title":"Why are Vickrey auctions rare? <it>J. Politi","volume":"1","author":"Rothkopf M. H.","year":"1990","unstructured":" Rothkopf , M. H. , Teisberg , T. J. , and Kahn , E. P. <\/scp> 1990 . Why are Vickrey auctions rare? <it>J. Politi . Econo. 98,<\/it> 1 , 94 -- 109 . Rothkopf, M. H., Teisberg, T. J., and Kahn, E. P.<\/scp> 1990. Why are Vickrey auctions rare? <it>J. Politi. Econo. 98,<\/it> 1, 94--109.","journal-title":"Econo. 98,<\/it>"},{"key":"e_1_2_1_34_1","series-title":"Lecture Notes in Computer Science","volume-title":"An auction protocol which hides bids of losers. In <it>Proceedings of the 3rd International Conference on Public Key Cryptography (PKC'00)<\/it>","author":"Sako K.","unstructured":" Sako , K. <\/scp> 2000. An auction protocol which hides bids of losers. In <it>Proceedings of the 3rd International Conference on Public Key Cryptography (PKC'00)<\/it> . Lecture Notes in Computer Science , vol. 1751 . Springer-Verlag , 422--432. Sako, K.<\/scp> 2000. An auction protocol which hides bids of losers. In <it>Proceedings of the 3rd International Conference on Public Key Cryptography (PKC'00)<\/it>. Lecture Notes in Computer Science, vol. 1751. Springer-Verlag, 422--432."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/10864415.2000.11518374"},{"key":"e_1_2_1_36_1","volume-title":"<\/scp>","author":"Sandholm T.","year":"2006","unstructured":" Sandholm , T. and Boutilier , C . <\/scp> 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. Sandholm, T. and Boutilier, C.<\/scp> 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."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1330332.1330338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1330332.1330338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:31Z","timestamp":1750258051000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1330332.1330338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1330332.1330338"],"URL":"https:\/\/doi.org\/10.1145\/1330332.1330338","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}