Article

Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces

Authors:

Seung Geol Choi,

Kyung-Wook Hwang,

Dan RubensteinAuthors Info & Claims

CT-RSA'12: Proceedings of the 12th conference on Topics in Cryptology

Pages 416 - 432

https://doi.org/10.1007/978-3-642-27954-6_26

Published: 27 February 2012 Publication History

Abstract

Protocols for generic secure multi-party computation (MPC) generally come in two forms: they either represent the function being computed as a boolean circuit, or as an arithmetic circuit over a large field. Either type of protocol can be used for any function, but the choice of which protocol to use can have a significant impact on efficiency. The magnitude of the effect, however, has never been quantified.

With this in mind, we implement the MPC protocol of Goldreich, Micali, and Wigderson [13], which uses a boolean representation and is secure against a semi-honest adversary corrupting any number of parties. We then consider applications of secure MPC in on-line marketplaces, where customers select resources advertised by providers and it is desired to ensure privacy to the extent possible. Problems here are more naturally formulated in terms of boolean circuits, and we study the performance of our MPC implementation relative to existing ones that use an arithmetic-circuit representation. Our protocol easily handles tens of customers/providers and thousands of resources, and outperforms existing implementations including FairplayMP [3], VIFF [11], and SEPIA [7].

References

[1]

Armbrust, M., Fox, A., Griffith, R., Joseph, A. D., Katz, R., Konwinski, A., Lee, G., Patterson, D. A., Rabkin, A., Stoica, I., Zaharia, M.: Above the clouds: A Berkeley view of cloud computing. Technical Report UCB/EECS-2009-28, EECS Department, UC Berkeley (2009)

[2]

Beaver, D.: Precomputing Oblivious Transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97-109. Springer, Heidelberg (1995)

[3]

Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: A system for secure multiparty computation. In: 15th ACM Conf. on Computer and Communications Security, pp. 257-266. ACM Press (2008)

[4]

Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A Framework for Fast Privacy-Preserving Computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192-206. Springer, Heidelberg (2008)

[5]

Bogetoft, P., Christensen, D. L., Damgård, I., Geisler, M., Jakobsen, T., Krøigaard, M., Nielsen, J. D., Nielsen, J. B., Nielsen, K., Pagter, J., Schwartzbach, M., Toft, T.: Secure Multiparty Computation Goes Live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325-343. Springer, Heidelberg (2009)

[6]

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)

[7]

Burkhart, M., Strasser, M., Many, D., Dimitropoulos, X.: SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics. In: 19th USENIX Security Symposium, pp. 223-240. USENIX Association (2010)

[8]

Buyya, R., Abramson, D., Venugopal, S.: The grid economy. Proc. IEEE 93(3), 698-714 (2005)

[9]

Chen, Y., Katz, R. H., Katz, Y. H., Kubiatowicz, J. D.: Dynamic Replica Placement for Scalable Content Delivery. In: Druschel, P., Kaashoek, M. F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 306-318. Springer, Heidelberg (2002)

[10]

Choi, S. G., Hwang, K., Katz, J., Malkin, T., Rubenstein, D.: Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces. Cryptology ePrint Archive, Report 2011/257 (2011), http://eprint.iacr.org/2011/257

[11]

Damgård, I., Geisler, M., Krøigaard, M., Nielsen, J. B.: Asynchronous Multiparty Computation: Theory and Implementation. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 160-179. Springer, Heidelberg (2009)

[12]

Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)

[13]

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game, or a completeness theorem for protocols with honest majority. In: 19th ACM STOC Annual ACM Symposium on Theory of Computing (STOC), pp. 218-229. ACM Press (1987)

[14]

Henecka, W., Kögl, S., Sadeghi, A.-R., Schneider, T., Wehrenberg, I.: TASTY: Tool for automating secure two-party computations. In: 17th ACM Conf. on Computer and Communications Security (CCCS), pp. 451-462. ACM Press (2010)

[15]

Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: 20th USENIX Security Symposium. USENIX Association (2011)

[16]

Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending Oblivious Transfers Efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145-161. Springer, Heidelberg (2003)

[17]

Jakobsen, T. P., Makkes, M.X., Nielsen, J. D.: Efficient Implementation of the Orlandi Protocol. In: Zhou, J., Yung, M. (eds.) ACNS 2010. LNCS, vol. 6123, pp. 255-272. Springer, Heidelberg (2010)

[18]

Kangasharju, J., Roberts, J., Ross, K. W.: Object replication strategies in content distribution networks. Computer Communications 25(4), 376-383 (2002)

[19]

Kolesnikov, V., Sadeghi, A.-R., Schneider, T.: Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima. In: Garay, J. A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 1-20. Springer, Heidelberg (2009)

[20]

Lewis, P. R., Marrow, P., Yao, X.: Evolutionary Market Agents for Resource Allocation in Decentralised Systems. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 1071-1080. Springer, Heidelberg (2008)

[21]

Li, B., Li, H., Xu, G., Xu, H.: Efficient reduction of 1-out-of-n oblivious transfers in random oracle model. Cryptology ePrint Archive, Report 2005/279 (2005)

[22]

Lindell, Y., Pinkas, B., Smart, N. P.: Implementing Two-Party Computation Efficiently with Security against Malicious Adversaries. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 2-20. Springer, Heidelberg (2008)

[23]

Malka, L., Katz, J.: VMCrypt -- modular software architecture for scalable secure computation, http://eprint.iacr.org/2010/584

[24]

Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay -- a secure two-party computation system. In: 13th USENIX Security Symposium, pp. 287-302. USENIX Association (2004)

[25]

Naor, M., Pinkas, B.: Computationally secure oblivious transfer. J. Cryptology 18(1), 1-35 (2005)

[26]

Pinkas, B., Schneider, T., Smart, N. P., Williams, S.C.: Secure Two-Party Computation is Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250-267. Springer, Heidelberg (2009)

[27]

Schnizler, B., Neumann, D., Veit, D., Weinhardt, C.: Trading grid services -- a multi-attribute combinatorial approach. European J. Operational Research 187(3), 943-961 (2008)

[28]

Tan, Z., Gurd, J. R.: Market-based grid resource allocation using a stable continuous double auction. In: Proc. 8th IEEE/ACM Intl. Conf. on Grid Computing, pp. 283- 290. IEEE (2007)

[29]

Wolski, R., Plank, J. S., Brevik, J., Bryan, T.: Analyzing market-based resource allocation strategies for the computational grid. International Journal of High Performance Computing Applications 15(3), 258-281 (2006)

[30]

Yao, A.C.-C.: How to generate and exchange secrets. In: 27th Annual Symp. on Foundations of Computer Science (FOCS), pp. 162-167. IEEE (1986)

Cited By

Heath DKolesnikov VPeceny S(2020): (Almost) Free Branching in GMWAdvances in Cryptology – ASIACRYPT 202010.1007/978-3-030-64840-4_1(3-30)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64840-4_1
Ben-Efraim ANielsen MOmri E(2019)Turbospeedz: Double Your Online SPDZ! Improving SPDZ Using Function Dependent PreprocessingApplied Cryptography and Network Security10.1007/978-3-030-21568-2_26(530-549)Online publication date: 5-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-21568-2_26
Büscher NDemmler DKatzenbeisser SKretzmer DSchneider TLie DMannan MBackes MWang X(2018)HyCCProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243786(847-861)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243786
Show More Cited By

Recommendations

Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
Secure Multi-Party Computation without Agreement

It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of ...
On adaptive security and round efficiency in secure multi-party computation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CT-RSA'12: Proceedings of the 12th conference on Topics in Cryptology

February 2012

432 pages

ISBN:9783642279539

Editor:
Orr Dunkelman
Computer Science Department, University of Haifa, Haifa, Israel

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 February 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Heath DKolesnikov VPeceny S(2020): (Almost) Free Branching in GMWAdvances in Cryptology – ASIACRYPT 202010.1007/978-3-030-64840-4_1(3-30)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64840-4_1
Ben-Efraim ANielsen MOmri E(2019)Turbospeedz: Double Your Online SPDZ! Improving SPDZ Using Function Dependent PreprocessingApplied Cryptography and Network Security10.1007/978-3-030-21568-2_26(530-549)Online publication date: 5-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-21568-2_26
Büscher NDemmler DKatzenbeisser SKretzmer DSchneider TLie DMannan MBackes MWang X(2018)HyCCProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243786(847-861)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243786
Chandran NGaray JMohassel PVusirikala SThuraisingham BEvans DMalkin TXu D(2017)Efficient, Constant-Round and Actively Secure MPCProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security10.1145/3133956.3134100(277-294)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.1145/3133956.3134100
Wang XRanellucci SKatz JThuraisingham BEvans DMalkin TXu D(2017)Global-Scale Secure Multiparty ComputationProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security10.1145/3133956.3133979(39-56)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.1145/3133956.3133979
Papadimitriou ANarayan AHaeberlen A(2017)DStressProceedings of the Twelfth European Conference on Computer Systems10.1145/3064176.3064218(560-574)Online publication date: 23-Apr-2017
https://dl.acm.org/doi/10.1145/3064176.3064218
Asharov GLindell YSchneider TZohner M(2017)More Efficient Oblivious Transfer ExtensionsJournal of Cryptology10.1007/s00145-016-9236-630:3(805-858)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00145-016-9236-6
Ben-Efraim ALindell YOmri EWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)Optimizing Semi-Honest Secure Multiparty Computation for the InternetProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2978347(578-590)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2978347
Lindell YSmart NSoria-Vazquez E(2016)More Efficient Constant-Round Multi-party Computation from BMR and SHEProceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 998510.1007/978-3-662-53641-4_21(554-581)Online publication date: 31-Oct-2016
https://dl.acm.org/doi/10.1007/978-3-662-53641-4_21
Demmler DDessouky GKoushanfar FSadeghi ASchneider TZeitouni SRay ILi NKruegel C(2015)Automated Synthesis of Optimized Circuits for Secure ComputationProceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security10.1145/2810103.2813678(1504-1517)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2810103.2813678
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents