Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

FAST: Fair Auctions via Secret Transactions

  • Conference paper
  • First Online:
Applied Cryptography and Network Security (ACNS 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13269))

Included in the following conference series:

Abstract

Sealed-bid auctions are a common way of allocating an asset among a set of parties but require trusting an auctioneer who analyses the bids and determines the winner. Many privacy-preserving computation protocols for auctions have been proposed to eliminate the need for a trusted third party. However, they lack fairness, meaning that the adversary learns the outcome of the auction before honest parties and may choose to make the protocol fail without suffering any consequences. In this work, we propose efficient protocols for both first and second-price sealed-bid auctions with fairness against rational adversaries, leveraging secret cryptocurrency transactions and public smart contracts. In our approach, the bidders jointly compute the winner of the auction while preserving the privacy of losing bids and ensuring that cheaters are financially punished by losing a secret collateral deposit. We guarantee that it is never profitable for rational adversaries to cheat by making the deposit equal to the bid plus the cost of running the protocol, i.e., once a party commits to a bid, it is guaranteed that it has the funds and it cannot walk away from the protocol without forfeiting the bid. Moreover, our protocols ensure that the winner is determined and the auction payments are completed even if the adversary misbehaves so that it cannot force the protocol to fail and then rejoin the auction with an adjusted bid. In comparison to the state-of-the-art, our constructions are both more efficient and furthermore achieve stronger security properties, i.e., fairness. Interestingly, we show how the second-price can be computed with a minimal increase of the complexity of the simpler first-price case. Moreover, in case there is no cheating, only collateral deposit and refund transactions must be sent to the smart contract, significantly saving on-chain storage.

B. David—This work was supported by the Concordium Foundation and by the Independent Research Fund Denmark with grants number 9040-00399B (TrA2C) and number 9131-00075B (PUMA).

L. Gentile—This work was supported by the Concordium Foundation.

M. Pourpouneh—This work was supported by the Center for Blockchains and Electronic Markets funded by the Carlsberg Foundation under grant no. CF18-1112.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In fact, showing such a proof of knowledge \(\pi '\) of \(r_{\mathtt {out}_i}\) together with \(h^{r_{\mathtt {out}_i}}\) and \(\mathtt {out}_i\) makes it easy to adapt reduction of the binding property of the Pedersen commitment scheme to the Discrete Logarithm assumption. Instead of obtaining \(r_{\mathtt {out}_i}\) from the adversary, the reduction simply extracts it from \(\pi '\).

  2. 2.

    We need \(m/2+2\) honest members to instantiate our packed publicly verifiable secret sharing based solution where two group elements are secret shared with a single share vector.

References

  1. Abe, M., Suzuki, K.: M + 1-st price auction using homomorphic encryption. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 115–124. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45664-3_8

    Chapter  Google Scholar 

  2. Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 443–458. IEEE Computer Society Press, May 2014

    Google Scholar 

  3. Bag, S., Hao, F., Shahandashti, S.F., Ray, I.G.: Seal: sealed-bid auction without auctioneers. IEEE Trans. Inf. Forensics Secur. 15, 2042–2052 (2019)

    Article  Google Scholar 

  4. Baudron, O., Stern, J.: Non-interactive private auctions. In: Syverson, P. (ed.) FC 2001. LNCS, vol. 2339, pp. 364–377. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46088-8_28

    Chapter  Google Scholar 

  5. Baum, C., David, B., Dowsley, R.: A framework for universally composable publicly verifiable cryptographic protocols. IACR Cryptol. ePrint Arch. 2020, 207 (2020)

    Google Scholar 

  6. Baum, C., David, B., Dowsley, R.: Insured MPC: efficient secure computation with financial penalties. In: Bonneau, J., Heninger, N. (eds.) FC 2020. LNCS, vol. 12059, pp. 404–420. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51280-4_22

    Chapter  MATH  Google Scholar 

  7. Benhamouda, F., et al.: Can a public blockchain keep a secret? In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 260–290. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64375-1_10

    Chapter  Google Scholar 

  8. Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_24

    Chapter  Google Scholar 

  9. Bentov, I., Kumaresan, R., Miller, A.: Instantaneous decentralized poker. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 410–440. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_15

    Chapter  Google Scholar 

  10. Bogetoft, P., Damgård, I., Jakobsen, T., Nielsen, K., Pagter, J., Toft, T.: A practical implementation of secure auctions based on multiparty integer computation. In: Di Crescenzo, G., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 142–147. Springer, Heidelberg (2006). https://doi.org/10.1007/11889663_10

    Chapter  Google Scholar 

  11. Brandt, F.: Fully private auctions in a constant number of rounds. In: Wright, R.N. (ed.) FC 2003. LNCS, vol. 2742, pp. 223–238. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45126-6_16

    Chapter  Google Scholar 

  12. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334. IEEE Computer Society Press, May 2018

    Google Scholar 

  13. Camenisch, J., Stadler, M.: Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, vol. 260 (1997)

    Google Scholar 

  14. Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  15. Cascudo, I., David, B.: ALBATROSS: publicly AttestabLe BATched randomness based on secret sharing. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12493, pp. 311–341. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64840-4_11

    Chapter  Google Scholar 

  16. Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: 18th ACM STOC, pp. 364–369. ACM Press, May 1986

    Google Scholar 

  17. Cramton, P., et al.: Spectrum auctions. In: Handbook of Telecommunications Economics, vol. 1, pp. 605–639 (2002)

    Google Scholar 

  18. David, B., Dowsley, R., Larangeira, M.: Kaleidoscope: an efficient poker protocol with payment distribution and penalty enforcement. In: Meiklejohn, S., Sako, K. (eds.) FC 2018. LNCS, vol. 10957, pp. 500–519. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-58387-6_27

    Chapter  Google Scholar 

  19. David, B., Gaži, P., Kiayias, A., Russell, A.: Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 66–98. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_3

    Chapter  Google Scholar 

  20. David, B., Gentile, L., Pourpouneh, M.: FAST: fair auctions via secret transactions. Cryptology ePrint Archive, Report 2021/264 (2021). https://ia.cr/2021/264

  21. Deuber, D., Döttling, N., Magri, B., Malavolta, G., Thyagarajan, S.A.K.: Minting mechanism for proof of stake blockchains. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds.) ACNS 2020. LNCS, vol. 12146, pp. 315–334. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57808-4_16

    Chapter  Google Scholar 

  22. Dreier, J., Dumas, J.-G., Lafourcade, P.: Brandt’s fully private auction protocol revisited. J. Comput. Secur. 23(5), 587–610 (2015)

    Article  MATH  Google Scholar 

  23. Franklin, M.K., Reiter, M.K.: The design and implementation of a secure auction service. IEEE Trans. Softw. Eng. 22(5), 302–312 (1996)

    Article  Google Scholar 

  24. Galal, H.S., Youssef, A.M.: Trustee: full privacy preserving Vickrey auction on top of ethereum. In: Bracciali, A., Clark, J., Pintore, F., Rønne, P.B., Sala, M. (eds.) FC 2019. LNCS, vol. 11599, pp. 190–207. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-43725-1_14

    Chapter  Google Scholar 

  25. Hao, F., Zieliński, P.: A 2-round anonymous veto protocol. In: Christianson, B., Crispo, B., Malcolm, J.A., Roe, M. (eds.) Security Protocols 2006. LNCS, vol. 5087, pp. 202–211. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04904-0_28

    Chapter  Google Scholar 

  26. Ishai, Y., Ostrovsky, R., Zikas, V.: Secure multi-party computation with identifiable abort. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 369–386. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_21

    Chapter  Google Scholar 

  27. Juels, A., Szydlo, M.: A two-server, sealed-bid auction protocol. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 72–86. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36504-4_6

    Chapter  Google Scholar 

  28. Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357–388. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_12

    Chapter  Google Scholar 

  29. Kiayias, A., Zhou, H.-S., Zikas, V.: Fair and robust multi-party computation using a global transaction ledger. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 705–734. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_25

    Chapter  Google Scholar 

  30. Klemperer, P.: Auctions: Theory and Practice. Princeton University Press, Princeton (2004)

    Book  MATH  Google Scholar 

  31. Krishna, V.: Auction Theory. Academic Press, Cambridge (2009)

    Google Scholar 

  32. Kurosawa, K., Ogata, W.: Bit-slice auction circuit. In: Gollmann, D., Karjoth, G., Waidner, M. (eds.) ESORICS 2002. LNCS, vol. 2502, pp. 24–38. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45853-0_2

    Chapter  Google Scholar 

  33. Lipmaa, H., Asokan, N., Niemi, V.: Secure Vickrey auctions without threshold trust. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 87–101. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36504-4_7

    Chapter  Google Scholar 

  34. Mas-Colell, A., Whinston, M.D., Green, J.R., et al.: Microeconomic Theory, vol. 1. Oxford University Press, New York (1995)

    MATH  Google Scholar 

  35. Maxwell, G.: Confidential transactions (2016). https://people.xiph.org/~greg/confidential_values.txt

  36. Miltersen, P.B., Nielsen, J.B., Triandopoulos, N.: Privacy-enhancing auctions using rational cryptography. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 541–558. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_32

    Chapter  Google Scholar 

  37. Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)

    Google Scholar 

  38. Nurmi, H., Salomaa, A.: Cryptographic protocols for Vickrey auctions. Group Decis. Negot. 2(4), 363–373 (1993). https://doi.org/10.1007/BF01384489

    Article  Google Scholar 

  39. Pass, R., Shi, E.: Hybrid consensus: efficient consensus in the permissionless model. In: Richa, A.W. (ed.) 31st International Symposium on Distributed Computing, DISC 2017, volume 91 of LIPIcs, Vienna, Austria, 16–20 October 2017, pp. 39:1–39:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

    Google Scholar 

  40. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_9

    Chapter  Google Scholar 

  41. Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1), 8–37 (1961)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IT University of Copenhagen, Copenhagen, Denmark

    Bernardo David & Lorenzo Gentile

  2. Copenhagen University, Copenhagen, Denmark

    Mohsen Pourpouneh

Authors
  1. Bernardo David
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lorenzo Gentile
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mohsen Pourpouneh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lorenzo Gentile .

Editor information

Editors and Affiliations

  1. Stevens Institute of Technology, Hoboken, NJ, USA

    Giuseppe Ateniese

  2. Sapienza University of Rome, Rome, Italy

    Daniele Venturi

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

David, B., Gentile, L., Pourpouneh, M. (2022). FAST: Fair Auctions via Secret Transactions. In: Ateniese, G., Venturi, D. (eds) Applied Cryptography and Network Security. ACNS 2022. Lecture Notes in Computer Science, vol 13269. Springer, Cham. https://doi.org/10.1007/978-3-031-09234-3_36

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-09234-3_36

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-09233-6

  • Online ISBN: 978-3-031-09234-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation