research-article

Open access

Secure Vickrey Auctions with Rational Parties

Authors:

Bhavana Kanukurthi,

Girisha ShankarAuthors Info & Claims

CCS '24: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security

Pages 4062 - 4076

https://doi.org/10.1145/3658644.3670311

Published: 09 December 2024 Publication History

Abstract

In this work, we construct a second price (Vickrey) auction protocol (SPA), which does not require any auctioneers and ensures total privacy in the presence of rational parties participating in the auction. In particular, the confidentiality of the highest bid and the identity of the second highest bidder are protected. We model the bidders participating in the second price auction as rational, computationally bounded and privacy-sensitive parties. These are self-interested agents who care about winning the auction more than learning about the private bids of other parties. A rational party does not deviate from the protocol arbitrarily but does so only for its own individual 'advantage' -- without any consideration for others. Such an advantage is modelled using suitable utility functions.

We show that for rational and computationally bounded parties participating in our second-price auctions protocol, there exists a privacy-preserving dominant strategy equilibrium in which every party prefers to follow the protocol rather than to deviate.

Our protocol is implemented using open-source cryptographic constructs. Running our SPA protocol on commodity hardware with 15 bidders, with bids of length 10 bits, completes in 1.26sec and has total communication of 0.77MB whereas, under similar conditions, Atlas (semi-honest) protocol takes 40% more time (2.11 sec) and 87% more communication (6.09MB).

References

[1]

Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Y. Halpern. 2006. Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In 25th ACM PODC, Eric Ruppert and Dahlia Malkhi (Eds.). ACM, 53--62. https://doi.org/10.1145/1146381.1146393

Digital Library

[2]

Christian Badertscher, Juan A. Garay, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. 2018. But Why Does It Work? A Rational Protocol Design Treatment of Bitcoin. In EUROCRYPT 2018, Part II (LNCS, Vol. 10821), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer, Heidelberg, 34--65. https://doi.org/10.1007/978--3--319--78375--8_2

[3]

Samiran Bag, Feng Hao, Siamak F Shahandashti, and Indranil Ghosh Ray. 2019. SEAL: Sealed-bid auction without auctioneers. IEEE Transactions on Information Forensics and Security, Vol. 15 (2019), 2042--2052.

[4]

Osman Biccer, Burcu Yildiz, and Alptekin Küpccü. 2021. m-stability: Threshold security meets transferable utility. In Proceedings of the 2021 on Cloud Computing Security Workshop. 73--82.

Digital Library

[5]

Felix Brandt. 2001. Cryptographic protocols for secure second-price auctions. In International Workshop on Cooperative Information Agents. Springer, 154--165.

[6]

Jan Camenisch and Markus Stadler. 1997. Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, Vol. 260 (1997).

[7]

Ran Canetti, Pratik Sarkar, and Xiao Wang. 2020. Efficient and Round-Optimal Oblivious Transfer and Commitment with Adaptive Security. In ASIACRYPT 2020, Part III (LNCS, Vol. 12493), Shiho Moriai and Huaxiong Wang (Eds.). Springer, Heidelberg, 277--308. https://doi.org/10.1007/978--3-030--64840--4_10

Digital Library

[8]

Boaz Catane and Amir Herzberg. 2013. Secure second price auctions with a rational auctioneer. In 2013 International Conference on Security and Cryptography (SECRYPT). IEEE, 1--12.

[9]

Bernardo David, Lorenzo Gentile, and Mohsen Pourpouneh. 2022. FAST: fair auctions via secret transactions. In International Conference on Applied Cryptography and Network Security. Springer, 727--747.

Digital Library

[10]

Alan Deckelbaum and Silvio Micali. 2016. Collusion, efficiency, and dominant strategies. (2016).

[11]

Yevgeniy Dodis, Shai Halevi, and Tal Rabin. 2000. A Cryptographic Solution to a Game Theoretic Problem. In CRYPTO 2000 (LNCS, Vol. 1880), Mihir Bellare (Ed.). Springer, Heidelberg, 112--130. https://doi.org/10.1007/3--540--44598--6_7

[12]

Chaya Ganesh, Shreyas Gupta, Bhavana Kanukurthi, and Girisha Shankar. 2024. Secure Vickrey Auctions with Rational Parties. Cryptology ePrint Archive, Paper 2024/1011. https://doi.org/10.1145/3658644.3670311 https://eprint.iacr.org/2024/1011.

Digital Library

[13]

Chaya Ganesh, Bhavana Kanukurthi, and Girisha Shankar. 2022. Secure Auctions in the Presence of Rational Adversaries. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 1173--1186.

Digital Library

[14]

Juan A. Garay, Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. 2013. Rational Protocol Design: Cryptography against Incentive-Driven Adversaries. In 54th FOCS. IEEE Computer Society Press, 648--657. https://doi.org/10.1109/FOCS.2013.75

Digital Library

[15]

Juan A. Garay, Jonathan Katz, Björn Tackmann, and Vassilis Zikas. 2015. How Fair is Your Protocol? A Utility-based Approach to Protocol Optimality. In 34th ACM PODC, Chryssis Georgiou and Paul G. Spirakis (Eds.). ACM, 281--290. https://doi.org/10.1145/2767386.2767431

Digital Library

[16]

S. Dov Gordon and Jonathan Katz. 2006. Rational Secret Sharing, Revisited. In SCN 06 (LNCS, Vol. 4116), Roberto De Prisco and Moti Yung (Eds.). Springer, Heidelberg, 229--241. https://doi.org/10.1007/11832072_16

Digital Library

[17]

Vipul Goyal, Hanjun Li, Rafail Ostrovsky, Antigoni Polychroniadou, and Yifan Song. 2021. ATLAS: Efficient and Scalable MPC in the Honest Majority Setting. In CRYPTO 2021, Part II (LNCS, Vol. 12826), Tal Malkin and Chris Peikert (Eds.). Springer, Heidelberg, Virtual Event, 244--274. https://doi.org/10.1007/978--3-030--84245--1_9

[18]

Joseph Y. Halpern. 2008. Beyond nash equilibrium: solution concepts for the 21st century. In 27th ACM PODC, Rida A. Bazzi and Boaz Patt-Shamir (Eds.). ACM, 1--10. https://doi.org/10.1145/1400751.1400752

Digital Library

[19]

Joseph Y. Halpern and Rafael Pass. 2010. Game Theory with Costly Computation: Formulation and Application to Protocol Security. In ICS 2010, Andrew Chi-Chih Yao (Ed.). Tsinghua University Press, 120--142.

[20]

Joseph Y. Halpern and Vanessa Teague. 2004. Rational secret sharing and multiparty computation: Extended abstract. In 36th ACM STOC, László Babai (Ed.). ACM Press, 623--632. https://doi.org/10.1145/1007352.1007447

Digital Library

[21]

Feng Hao and Piotr Zieli'nski. 2006. A 2-round anonymous veto protocol. In International Workshop on Security Protocols. Springer, 202--211.

[22]

Po-Chu Hsu and Atsuko Miyaji. 2021. Bidder Scalable M 1st-Price Auction with Public Verifiability. In 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, 34--42.

[23]

Sergei Izmalkov, Silvio Micali, and Matt Lepinski. 2005. Rational Secure Computation and Ideal Mechanism Design. In 46th FOCS. IEEE Computer Society Press, 585--595. https://doi.org/10.1109/SFCS.2005.64

Digital Library

[24]

Jonathan Katz. 2008. Bridging Game Theory and Cryptography: Recent Results and Future Directions (Invited Talk). In TCC 2008 (LNCS, Vol. 4948), Ran Canetti (Ed.). Springer, Heidelberg, 251--272. https://doi.org/10.1007/978--3--540--78524--8_15

[25]

Marcel Keller. 2020. MP-SPDZ: A versatile framework for multi-party computation. In Proceedings of the 2020 ACM SIGSAC conference on computer and communications security. 1575--1590.

Digital Library

[26]

Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. In ACM CCS 2016, Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM Press, 830--842. https://doi.org/10.1145/2976749.2978357

Digital Library

[27]

Gillat Kol and Moni Naor. 2008. Cryptography and Game Theory: Designing Protocols for Exchanging Information. In TCC 2008 (LNCS, Vol. 4948), Ran Canetti (Ed.). Springer, Heidelberg, 320--339. https://doi.org/10.1007/978--3--540--78524--8_18

[28]

Vijay Krishna. 2009. Auction Theory. (2009).

[29]

Kaoru Kurosawa and Wakaha Ogata. 2002. Bit-Slice Auction Circuit. In Proceedings of the 7th European Symposium on Research in Computer Security. 24--38.

Digital Library

[30]

Yehuda Lindell, Benny Pinkas, Nigel P Smart, and Avishay Yanai. 2019. Efficient constant-round multi-party computation combining BMR and SPDZ. Journal of Cryptology, Vol. 32, 3 (2019), 1026--1069.

Digital Library

[31]

Helger Lipmaa, N Asokan, and Valtteri Niemi. 2002. Secure Vickrey auctions without threshold trust. In Proceedings of the 6th international conference on Financial cryptography. 87--101.

Digital Library

[32]

Silvio Micali. 2014. Rational and resilient protocols. In 33rd ACM PODC, Magnús M. Halldórsson and Shlomi Dolev (Eds.). ACM, 1. https://doi.org/10.1145/2611462.2611516

Digital Library

[33]

Peter Bro Miltersen, Jesper Buus Nielsen, and Nikos Triandopoulos. 2009. Privacy-Enhancing Auctions Using Rational Cryptography. In CRYPTO 2009 (LNCS, Vol. 5677), Shai Halevi (Ed.). Springer, Heidelberg, 541--558. https://doi.org/10.1007/978--3--642-03356--8_32

[34]

Moni Naor, Benny Pinkas, and Reuban Sumner. 1999. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM Conference on Electronic Commerce. 129--139.

Digital Library

[35]

Yadati Narahari. 2014. Game theory and mechanism design. Vol. 4. World Scientific.

[36]

Mehrdad Nojoumian and Douglas R Stinson. 2014. Efficient sealed-bid auction protocols using verifiable secret sharing. In International Conference on Information Security Practice and Experience. Springer, 302--317.

Digital Library

[37]

Kazumasa Omote and Atsuko Miyaji. 2003. A Second-price Sealed-bid Auction with the Discriminant of the p0-th Root. In FC 2002 (LNCS, Vol. 2357), Matt Blaze (Ed.). Springer, Heidelberg, 57--71.

[38]

Nikolaj Ignatieff Schwartzbach. 2022. Payment Schemes from Limited Information with Applications in Distributed Computing. In Proceedings of the 23rd ACM Conference on Economics and Computation. 129--149.

Digital Library

Cited By

Ganesh CGupta SKanukurthi BShankar GLuo BLiao XXu JKirda ELie D(2024)Secure Vickrey Auctions with Rational PartiesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670311(4062-4076)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670311

Index Terms

Secure Vickrey Auctions with Rational Parties
1. Security and privacy
  1. Security services
    1. Privacy-preserving protocols

Recommendations

Binary Vickrey auction - A robust and efficient multi-unit sealed-bid online auction protocol against buyer multi-identity bidding

The multi-unit Vickrey-Clark-Groves (VCG) mechanism has two major weaknesses: it has high computational complexity and monotonicity problems [Paul Milgrom. Putting Auction Theory to Work. Cambridge University Press, Cambridge, UK, 2004] such that if ...
Implementing private Vickrey auctions
SAC '05: Proceedings of the 2005 ACM symposium on Applied computing

Vickrey auctions have the interesting property of eliminating any incentive for bidders to bid values that are different from their reserve prices (i.e., the true value they give to the item being auctioned). For several reasons, it is desirable that ...
Vickrey vs. eBay: Why Second-Price Sealed-Bid Auctions Lead to More Realistic Price-Demand Functions

Knowledge of consumers' willingness-to-pay (WTP) is critical for marketing managers when designing optimal pricing policies. The large-scale applicability, reliability, and validity of Vickrey auctions as an incentive-compatible method for eliciting WTP ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '24: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security

December 2024

5188 pages

ISBN:9798400706363

DOI:10.1145/3658644

General Chairs:
Bo Luo
University of Kansas, USA
,
Xiaojing Liao
Indiana University Bloomington, USA
,
Jun Xu
University of Utah, USA
,
Program Chairs:
Engin Kirda
Northeastern University, USA
,
David Lie
University of Toronto, Canada

Copyright © 2024 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 December 2024

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Science and Engineering Research Board, India

Conference

CCS '24

Sponsor:

SIGSAC

CCS '24: ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

UT, Salt Lake City, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
43
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)43

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ganesh CGupta SKanukurthi BShankar GLuo BLiao XXu JKirda ELie D(2024)Secure Vickrey Auctions with Rational PartiesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670311(4062-4076)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670311

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents