Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces. (English) Zbl 1292.94047

Dunkelman, Orr (ed.), Topics in cryptology – CT-RSA 2012. The cryptographers’ track at the RSA conference 2012, San Francisco, CA, USA, February 27–March 2, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-27953-9/pbk). Lecture Notes in Computer Science 7178, 416-432 (2012).
Summary: 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, 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, VIFF, and SEPIA.
For the entire collection see [Zbl 1235.94010].


94A60 Cryptography
Full Text: DOI Link


[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) · Zbl 0876.94021
[3] Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: A system for secure multi-party 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) · Zbl 05357655
[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) · Zbl 1417.94045
[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) · Zbl 1152.94405
[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) · Zbl 1014.68654
[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 · Zbl 1292.94047
[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) · Zbl 1227.68014
[12] Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011
[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) · Zbl 1122.94422
[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) · Zbl 1350.94038
[18] Kangasharju, J., Roberts, J., Ross, K.W.: Object replication strategies in content distribution networks. Computer Communications 25(4), 376–383 (2002) · Zbl 05396658
[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) · Zbl 1287.94078
[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) · Zbl 05489546
[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) · Zbl 1180.68152
[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) · Zbl 1075.68026
[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) · Zbl 1267.94091
[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) · Zbl 1137.91416
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.