Abstract
This article proposes efficient solutions for the construction of sealed-bid second-price and combinatorial auction protocols in an active adversary setting. The main reason for constructing secure auction protocols is that the losing bids can be used in the future auctions as well as negotiations if they are not kept private. Our motivation is to apply verifiable secret sharing in order to construct various kinds of sealed-bid auctions. We initially propose two secure second-price auction protocols with different masking methods. Subsequently, we provide two secure combinatorial auction protocols based on our second masking approach. In the first scheme, we apply an existing dynamic programming method. In the second protocol, we use inter-agent negotiation as an approximate solution in the multiple traveling salesman problem to determine auction outcomes. It is worth mentioning that our protocols are independent of the secret sharing scheme that is being used.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
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)
Baudron, O., Stern, J.: Non-interactive private auctions. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, pp. 354–377. Springer, Heidelberg (2002)
Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3), 209–219 (2006)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: 20th Annual ACM Symposium on Theory of Computing, STOC, pp. 1–10 (1988)
Blakley, G.R.: Safeguarding cryptographic keys. In: National Computer Conference, vol. 48, pp. 313–317. AFIPS Press (1979)
Brandt, F.: A verifiable, bidder-resolved auction protocol. In: 5th Int. Workshop on Deception, Fraud and Trust in Agent Societies, Special Track on Privacy and Protection with Multi-Agent Systems, pp. 18–25 (2002)
Cachin, C.: Efficient private bidding and auctions with an oblivious third party. In: ACM Conference on Computer and Communications Security, pp. 120–127 (1999)
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults. In: 26th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 383–395 (1985)
Damgård, I.B., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 285–304. Springer, Heidelberg (2006)
Franklin, M.K., Reiter, M.K.: The design and implementation of a secure auction service. IEEE Transactions on Software Eng. 22(5), 302–312 (1996)
Garay, J.A., Schoenmakers, B., Villegas, J.: Practical and secure solutions for integer comparison. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 330–342. Springer, Heidelberg (2007)
Harkavy, M., Tygar, J.D., Kikuchi, H.: Electronic auctions with private bids. In: 3rd Workshop on E-Commerce, pp. 61–74. USENIX Association (1998)
Kikuchi, H.: (M+1)st-price auction protocol. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, pp. 341–363. Springer, Heidelberg (2002)
Kikuchi, H., Harkavy, M., Tygar, J.D.: Multi-round anonymous auction protocols. IEICE Transaction on Information and Systems 82, 769–777 (1999)
Kikuchi, H., Hotta, S., Abe, K., Nakanishi, S.: Distributed auction servers resolving winner and winning bid without revealing privacy of bids. In: 7th Int. Conference on Parallel and Distributed Systems, pp. 307–312. IEEE (2000)
Kim, I.C.: Task reallocation in multiagent systems based on vickrey auctioning. In: International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, pp. 40–44. IOS Press (2002)
Krishnamachari, S., Nojoumian, M., Akkaya, K.: Implementation and analysis of dutch-style sealed-bid auctions: Computational vs unconditional security (2014) (Under Review Manuscript)
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)
MacWilliams, F., Sloane, N.: The theory of error-correcting codes. North-Holland Amsterdam (1978)
Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: ACM Conference on Electronic Commerce, pp. 129–139 (1999)
Nguyen, K.Q., Traoré, J.: An online public auction protocol protecting bidder privacy. In: Clark, A., Boyd, C., Dawson, E.P. (eds.) ACISP 2000. LNCS, vol. 1841, pp. 427–442. Springer, Heidelberg (2000)
Nishide, T., Ohta, K.: Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 343–360. Springer, Heidelberg (2007)
Nojoumian, M., Stinson, D.R.: Unconditionally secure first-price auction protocols using a multicomponent commitment scheme. In: Soriano, M., Qing, S., López, J. (eds.) ICICS 2010. LNCS, vol. 6476, pp. 266–280. Springer, Heidelberg (2010)
Nojoumian, M., Stinson, D.R.: On dealer-free dynamic threshold schemes. Advances in Mathematics of Communications, AMC 7(1), 39–56 (2013)
Parkes, D.C., Rabin, M.O., Shieber, S.M., Thorpe, C.: Practical secrecy-preserving, verifiably correct and trustworthy auctions. Electronic Commerce Research and Applications 7(3), 294–312 (2008)
Peng, K., Boyd, C., Dawson, E.: Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 84–98. Springer, Heidelberg (2005)
Peng, K., Boyd, C., Dawson, E., Viswanathan, K.: Robust, privacy protecting and publicly verifiable sealed-bid auction. In: Deng, R.H., Qing, S., Bao, F., Zhou, J. (eds.) ICICS 2002. LNCS, vol. 2513, pp. 147–159. Springer, Heidelberg (2002)
Peng, K., Boyd, C., Dawson, E., Viswanathan, K.: Five sealed-bid auction models. In: Australasian Information Security Workshop Conference, pp. 77–86. Australian Computer Society (2003)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: 21th Annual ACM Symposium on Theory of Computing, STOC, pp. 73–85 (1989)
Sako, K.: An auction protocol which hides bids of losers. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 422–432. Springer, Heidelberg (2000)
Shamir, A.: How to share a secret. Comm. of the ACM 22(11), 612–613 (1979)
Stinson, D.R., Wei, R.: Unconditionally secure proactive secret sharing scheme with combinatorial structures. In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 200–214. Springer, Heidelberg (2000)
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)
Suzuki, K., Yokoo, M.: Secure multi-attribute procurement auction. In: Song, J.-S., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS, vol. 3786, pp. 306–317. Springer, Heidelberg (2006)
Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance 16(1), 8–37 (1961)
Viswanathan, K., Boyd, C., Dawson, E.: A three phased schema for sealed bid auction system design. In: Clark, A., Boyd, C., Dawson, E.P. (eds.) ACISP 2000. LNCS, vol. 1841, pp. 412–426. Springer, Heidelberg (2000)
Watanabe, Y., Imai, H.: Reducing the round complexity of a sealed-bid auction protocol with an off-line ttp. In: ACM Conference on Computer and Communications Security, CCS, pp. 80–86 (2000)
Yao, A.C.-C.: Protocols for secure computations. In: 23rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 160–164 (1982)
Yokoo, M., Suzuki, K.: Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions. In: 1st International Joint Conference on AAMAS, pp. 112–119. ACM (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Nojoumian, M., Stinson, D.R. (2014). Efficient Sealed-Bid Auction Protocols Using Verifiable Secret Sharing. In: Huang, X., Zhou, J. (eds) Information Security Practice and Experience. ISPEC 2014. Lecture Notes in Computer Science, vol 8434. Springer, Cham. https://doi.org/10.1007/978-3-319-06320-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-06320-1_23
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06319-5
Online ISBN: 978-3-319-06320-1
eBook Packages: Computer ScienceComputer Science (R0)