nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Practically Efficient Secure Single-Commodity Multi-market Auctions

verfasst von : Abdelrahaman Aly, Mathieu Van Vyve

Erschienen in: Financial Cryptography and Data Security

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the problem of securely building single-commodity multi-markets auction mechanisms. We introduce a novel greedy algorithm and its corresponding privacy preserving implementation using secure multi-party computation. More specifically, we determine the quantity of supply and demand bids maximizing welfare. Each bid is attached to a specific market, but exchanges between different markets are allowed up to some upper limit. The general goal is for the players to bid their intended valuations without concerns about what the other players can learn. This problem is inspired by day-ahead electricity markets where there are substantial transmission capacity between the different markets, but applies to other commodity markets like gas. Furthermore, we provide computational results with a specific C++ implementation of our algorithm and the necessary MPC primitives. We can solve problems of 1945 bids and 4 markets in 1280 s when online/offline phases are considered. Finally, we report on possible set-ups, workload distributions and possible trade-offs for real-life applications of our results based on this experimentation and prototyping.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Private eCash in Practice (Short Paper)

Nächstes Kapitel How to Challenge and Cast Your e-Vote

Klemperer, P.: What really matters in auction design, from auctions: theory and practice. In: Auctions: Theory and Practice. Introductory Chapters. Princeton University Press (2004)

Yao, A.C.C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, pp. 160–164. IEEE (1982)

Shoup, V.: NTL: a library for doing number theory. http://www.shoup.net/ntl/

Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03549-4_20 CrossRef

Geisler, M.: Cryptographic protocols: theory and implementation. Ph.D. thesis, Aarhus University Denmark, Department of Computer Science (2010)

Aly, A., Van Vyve, M.: Securely solving classical network flow problems. In: Lee, J., Kim, J. (eds.) ICISC 2014. LNCS, vol. 8949, pp. 205–221. Springer, Cham (2015). doi:10.1007/978-3-319-15943-0_13

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

Harkavy, M., Tygar, J.D., Kikuchi, H.: Electronic auctions with private bids. In: Proceedings of the 3rd Conference on USENIX Workshop on Electronic Commerce, WOEC 1998, vol. 3, p. 6. USENIX Association, Berkeley (1998)

Kikuchi, H., Hotta, S., Abe, K., Nakanishi, S.: Distributed auction servers resolving winner and winning bid without revealing privacy of bids. In: Seventh International Conference on Parallel and Distributed Systems: Workshops, pp. 307–312 (2000)

10.

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). doi:10.1007/11554868_7 CrossRef

11.

Nojoumian, M., Stinson, D.R.: Efficient sealed-bid auction protocols using verifiable secret sharing. In: Huang, X., Zhou, J. (eds.) ISPEC 2014. LNCS, vol. 8434, pp. 302–317. Springer, Cham (2014). doi:10.1007/978-3-319-06320-1_23 CrossRef

12.

Shamir, A.: How to share a secret. Commun. ACM 22, 612–613 (1979). ACM, New YorkMathSciNetCrossRefMATH

13.

Catane, B., Herzberg, A.: Secure second price auctions with a rational auctioneer. In: The 10-th SECRYPT International Conference on Security and Cryptography (2013)

14.

Madani, M., Van Vyve, M.: A new formulation of the European day-ahead electricity market problem and its algorithmic consequences. CORE Discussion Papers 2013074, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) (2013)

15.

Madani, M., Van Vyve, M.: Computationally efficient MIP formulation and algorithms for European day-ahead electricity market auctions. Eur. J. Oper. Res. 242, 580–593 (2015)MathSciNetCrossRefMATH

16.

Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57, 509–533 (1935)MathSciNetCrossRefMATH

17.

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 1–10. ACM, New York (1988)

18.

Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults. In: 26th Annual Symposium on Foundations of Computer Science, pp. 383–395, October 1985

19.

Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC 1998, pp. 101–111. ACM, New York (1998)

20.

Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20901-7_2 CrossRef

21.

Damgård, I., 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). doi:10.1007/11681878_15 CrossRef

22.

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). doi:10.1007/978-3-540-71677-8_23 CrossRef

23.

Catrina, O., de Hoogh, S.: Improved primitives for secure multiparty integer computation. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 182–199. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15317-4_13 CrossRef

24.

Lipmaa, H., Toft, T.: Secure equality and greater-than tests with sublinear online complexity. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 645–656. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39212-2_56

25.

Laur, S., Willemson, J., Zhang, B.: Round-efficient oblivious database manipulation. In: Lai, X., Zhou, J., Li, H. (eds.) ISC 2011. LNCS, vol. 7001, pp. 262–277. Springer, Heidelberg (2011). doi:10.1007/978-3-642-24861-0_18 CrossRef

26.

Keller, M., Scholl, P.: Efficient, oblivious data structures for MPC. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 506–525. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45608-8_27

27.

Czumaj, A., Kanarek, P., Kutylowski, M., Lorys, K.: Delayed path coupling and generating random permutations via distributed stochastic processes. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999, pp. 271–280. Society for Industrial and Applied Mathematics, Philadelphia (1999)

28.

Goodrich, M.T.: Randomized shellsort: a simple data-oblivious sorting algorithm. J. ACM (JACM) 58, 27:1–27:26 (2011). ACM, New YorkMathSciNetCrossRefMATH

29.

Jónsson, K.V., Kreitz, G., Uddin, M.: Secure multi-party sorting and applications. In: IACR Cryptology ePrint Archive, vol. 2011, p. 122 (2011)

30.

Goodrich, M.T.: Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in o(n log n) time. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 684–693. ACM, New York (2014)

31.

Hamada, K., Ikarashi, D., Chida, K., Takahashi, K.: Oblivious radix sort: an efficient sorting algorithm for practical secure multi-party computation. In: IACR Cryptology ePrint Archive, vol. 2014, p. 121 (2014)

32.

Aly, A., Cuvelier, E., Mawet, S., Pereira, O., Van Vyve, M.: Securely solving simple combinatorial graph problems. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 239–257. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39884-1_21 CrossRef

33.

Blanton, M., Steele, A., Alisagari, M.: Data-oblivious graph algorithms for secure computation and outsourcing. In: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, ASIA CCS 2013, pp. 207–218. ACM, New York (2013)

34.

Catrina, O., de Hoogh, S.: Secure multiparty linear programming using fixed-point arithmetic. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 134–150. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15497-3_9 CrossRef

35.

Hamada, K., Kikuchi, R., Ikarashi, D., Chida, K., Takahashi, K.: Practically efficient multi-party sorting protocols from comparison sort algorithms. In: Kwon, T., Lee, M.-K., Kwon, D. (eds.) ICISC 2012. LNCS, vol. 7839, pp. 202–216. Springer, Heidelberg (2013). doi:10.1007/978-3-642-37682-5_15 CrossRef

36.

Aly, A.: Network flow problems with secure multiparty computation. Ph.D. thesis, Universté catholique de Louvain, IMMAQ (2015)

37.

Cramer, R., Damgård, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005). doi:10.1007/978-3-540-30576-7_19 CrossRef

Titel: Practically Efficient Secure Single-Commodity Multi-market Auctions
verfasst von: Abdelrahaman Aly
Mathieu Van Vyve
Verlag: Springer Berlin Heidelberg
Buch: Financial Cryptography and Data Security
Print ISBN: 978-3-662-54969-8

Electronic ISBN: 978-3-662-54970-4

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-662-54970-4_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"