Skip to main content
SpringerLink
Log in

Secure Generalized Vickrey Auction Using Homomorphic Encryption

  • Conference paper
Financial Cryptography (FC 2003)

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

Included in the following conference series:

Abstract

Combinatorial auctions have recently attracted the interest of many researchers due to their promising applications such as the spectrum auctions recently held by the FCC. In a combinatorial auction, multiple items with interdependent values are sold simultaneously and bidders are allowed to bid on any combination of items. The Generalized Vickrey Auction (GVA) can handle combinatorial auctions and has several good theoretical characteristics. However, GVA has not yet widely used in practice due to its vulnerability to fraud by the auctioneers. In this paper, to prevent such fraud, we propose a secure Generalized Vickrey Auction scheme where the result of the auction can be computed while the actual evaluation values of each bidder are kept secret.

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 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

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)

    Chapter  Google Scholar 

  2. Baudron, O., Stern, J.: Non-interactive private auctions. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, pp. 364–377. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  3. Brandt, F.: Fully private auctions in a constant number of rounds. In: Proceedings of Financial Cryptography 2003 (2003)

    Google Scholar 

  4. Cachin, C.: Efficient private bidding and auctions with an oblivious third party. In: Proceedings of 6th ACM Conference on Computer and Communications Security, pp. 120–127 (1999)

    Google Scholar 

  5. Chida, K., Kobayashi, K., Morita, H.: Efficient sealed-bid auctions for massive numbers of bidders with lump comparison. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol. 2200, pp. 408–419. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  6. Clarke, E.H.: Multipart pricing of public goods. Public Choice 2, 19–33 (1971)

    Google Scholar 

  7. de Vries, S., Vohra, R.V.: Combinatorial auctions: A survey. INFORMS Journal on Computing (forthcoming)

    Google Scholar 

  8. Fujishima, Y., Leyton-Brown, K., Shoham, Y.: Taming the computation complexity of combinatorial auctions: Optimal and approximate approaches. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-1999), pp. 548–553 (1999)

    Google Scholar 

  9. Groves, T.: Incentives in teams. Econometrica 41, 617–631 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  10. Harkavy, M., Tygar, J.D., Kikuchi, H.: Electronic auctions with private bids. In: Proceedings of Third USENIX Workshop on Electronic Commerce, pp. 61–74 (1998)

    Google Scholar 

  11. 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)

    Chapter  Google Scholar 

  12. Kikuchi, H.: (m+1)st-price auction protocol. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, pp. 351–363. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  13. Kikuchi, H., Harkavy, M., Tygar, J.D.: Multi-round anonymous auction protocols. In: Proceedings of first IEEE Workshop on Dependable and Real-Time E-Commerce Systems, pp. 62–69 (1998)

    Google Scholar 

  14. Klemperer, P.: Auction theory: A guide to the literature. Journal of Economics Surveys 13(3), 227–286 (1999)

    Article  Google Scholar 

  15. Kobayashi, K., Morita, H., Suzuki, K., Hakuta, M.: Efficient sealed-bid auction by using one-way functions. IEICE Trans. Fundamentals E84-A(1), 289–294 (2001)

    Google Scholar 

  16. Krishna, V.: Auction Theory. Academic Press, London (2002)

    Google Scholar 

  17. Kudo, M.: Secure electronic sealed-bid auction protocol with public key cryptography. IEICE Trans. Fundamentals E81-A(1), 20–27 (1998)

    MathSciNet  Google Scholar 

  18. Lehmann, D., O’Callaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auction. In: Proceedings of the First ACM Conference on Electronic Commerce (EC-1999), pp. 96–102 (1999)

    Google Scholar 

  19. Leyton-Brown, K., Pearson, M., Shoham, Y.: Towards a universal test suite for combinatorial auction algorithms. In: Proceedings of the Second ACM Conference on Electronic Commerce (EC-2000), pp. 66–76 (2000)

    Google Scholar 

  20. 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)

    Chapter  Google Scholar 

  21. McMillan, J.: Selling spectrum rights. Journal of Economics Perspectives 8(3), 145–162 (1994)

    Article  Google Scholar 

  22. Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: Proceedings of ACM conference on E-commerce 1999, pp. 129–139 (1999)

    Google Scholar 

  23. Omote, K., Miyaji, A.: An anonymous auction protocol with a single nontrusted center using binary trees. In: Okamoto, E., Pieprzyk, J.P., Seberry, J. (eds.) ISW 2000. LNCS, vol. 1975, pp. 108–120. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  24. Omote, K., Miyaji, A.: A second-price sealed-bid auction with the discriminant of the p-th root. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 57–71. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  25. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  26. Rothkopf, M.H., Teisberg, T.J., Kahn, E.P.: Why are vickrey auctions are rare. Journal of Political Economy 98(1), 94–109 (1990)

    Article  Google Scholar 

  27. Sako, K.: Universally verifiable auction protocol which hides losing bids. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 422–432. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  28. Sakurai, K., Miyazaki, S.: A bulletin-board based digital auction scheme with bidding down strategy. In: Proceedings of 1999 International Workshop on Cryptographic Techniques and E-Commerce, pp. 180–187 (1999)

    Google Scholar 

  29. Sandholm, T.: An algorithm for optimal winner determination in combinatorial auction. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-1999), pp. 542–547 (1999)

    Google Scholar 

  30. Sandholm, T., Suri, S., Gilpin, A., Levine, D.: CABOB: A fast combinatorial algorithm for optimal combinatorial auctions. In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-2001), pp. 1102–1108 (2001)

    Google Scholar 

  31. Stubblebine, S.G., Syverson, P.F.: Fair on-line auctions without special trusted parties. In: Franklin, M.K. (ed.) FC 1999. LNCS, vol. 1648, pp. 230–240. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  32. Suzuki, K., Kobayashi, K., Morita, H.: Efficient sealed-bid auction using hash chain. In: Won, D. (ed.) ICISC 2000. LNCS, vol. 2015, pp. 183–191. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  33. Suzuki, K., Yokoo, M.: Secure combinatorial auctions by dynamic programming with polynomial secret sharing. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 44–56. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  34. Varian, H.R.: Economic mechanism design for computerized agents. In: Proceedings of the First Usenix Workshop on Electronic Commerce (1995)

    Google Scholar 

  35. Vickrey, W.: Counter speculation, auctions, and competitive sealed tenders. Journal of Finance 16, 8–37 (1961)

    Article  Google Scholar 

  36. Watanabe, Y., Imai, H.: Reducing the round complexity of a sealed-bid auction protocol with an off-line ttp. In: Proceedings of ACM Conference on Computer and Communications Security 2000, pp. 80–86 (2000)

    Google Scholar 

  37. Yao, A.C.: How to generate and exchange secrets. In: Proceedings of IEEE Symposium on Foundations of Computer Science, pp. 162–167 (1986)

    Google Scholar 

  38. Yokoo, M., Sakurai, Y., Matsubara, S.: Robust combinatorial auction protocol against false-name bids. Artificial Intelligence 130(2), 167–181 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  39. Yokoo, M., Skurai, Y., Matsubara, S.: The effect of false-name bids in combinatorial auctions: New fraud in internet auctions. Games and Economic Behavior (forthcoming)

    Google Scholar 

  40. Yokoo, M., Suzuki, K.: Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions. In: Proceedings of the First International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2002), pp. 112–119 (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. NTT Information Sharing Platform Laboratories, NTT Corporation, 1-1 Hikari-no-oka, Yokosuka, Kanagawa, 239-0847, Japan

    Koutarou Suzuki

  2. NTT Communication Science Laboratories, NTT Corporation, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto, 619-0237, Japan

    Makoto Yokoo

Authors
  1. Koutarou Suzuki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Makoto Yokoo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and DIMACS, Rutgers University, 08854, Piscataway, NJ, USA

    Rebecca N. Wright

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Suzuki, K., Yokoo, M. (2003). Secure Generalized Vickrey Auction Using Homomorphic Encryption. In: Wright, R.N. (eds) Financial Cryptography. FC 2003. Lecture Notes in Computer Science, vol 2742. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45126-6_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-45126-6_17

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40663-1

  • Online ISBN: 978-3-540-45126-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation