Abstract
We revisit the problem of general-purpose private function evaluation (PFE) wherein a single party P 1 holds a circuit \(\mathcal{C}\), while each P i for 1 ≤ i ≤ n holds a private input x i , and the goal is for a subset (or all) of the parties to learn \(\mathcal{C}(x_1, \ldots, x_n)\) but nothing else. We put forth a general framework for designing PFE where the task of hiding the circuit and securely evaluating its gates are addressed independently: First, we reduce the task of hiding the circuit topology to oblivious evaluation of a mapping that encodes the topology of the circuit, which we refer to as oblivious extended permutation (OEP) since the mapping is a generalization of the permutation mapping. Second, we design a subprotocol for private evaluation of a single gate (PFE for one gate), which we refer to as private gate evaluation (PGE). Finally, we show how to naturally combine the two components to obtain efficient and secure PFE.
We apply our framework to several well-known general-purpose MPC constructions, in each case, obtaining the most efficient PFE construction to date, for the considered setting. Similar to the previous work we only consider semi-honest adversaries in this paper.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abadi, M., Feigenbaum, J.: Secure circuit evaluation. Journal of Cryptology 2, 1–12 (1990)
Kolesnikov, V., Schneider, T.: A practical universal circuit construction and secure evaluation of private functions. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 83–97. Springer, Heidelberg (2008)
Sadeghi, A.R., Schneider, T.: Generalized universal circuits for secure evaluation of private functions with application to data classification. In: Lee, P.J., Cheon, J.H. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 336–353. Springer, Heidelberg (2009)
Katz, J., Malka, L.: Constant-round private function evaluation with linear complexity. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 556–571. Springer, Heidelberg (2011)
Schneider, T.: Practical secure function evaluation (2008)
Valiant, L.: Universal circuits (preliminary report). In: Proceedings of the Eighth Annual ACM STOC, pp. 196–203 (1976)
Shpilka, A., Yehudayoff, A.: Arithmetic circuits: A survey of recent results and open questions (2010)
Raz, R.: Elusive functions and lower bounds for arithmetic circuits. In: Proceedings of the 40th Annual ACM STOC (2008)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM, STOC 2009, pp. 169–178. ACM (2009)
Huang, Y., Evans, D., Katz, J.: Private set intersection: Are garbled circuits better than custom protocols? In: Proceedings of 19th NDSS Conference (2012)
Wang, G., Luo, T., Goodrich, M.T., Du, W., Zhu, Z.: Bureaucratic protocols for secure two-party sorting, selection, and permuting. In: Proceedings of the 5th ACM ASIACCS, pp. 226–237 (2010)
Du, W.: A Study of Several Specific Secure Two-party Computation Problems. PhD thesis, Department of Computer Sciences, Purdue University (2001)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM, STOC 1987, pp. 218–229. ACM (1987)
Yao, A.C.C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science, pp. 162–167 (October 1986)
Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–299. Springer, Heidelberg (2001)
Franklin, M., Gondree, M., Mohassel, P.: Multi-party indirect indexing and applications. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 283–297. Springer, Heidelberg (2007)
Choi, S.G., Hwang, K.-W., Katz, J., Malkin, T., Rubenstein, D.: Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces. In: Dunkelman, O. (ed.) CT-RSA 2012. LNCS, vol. 7178, pp. 416–432. Springer, Heidelberg (2012)
Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681–700. Springer, Heidelberg (2012)
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)
Beaver, D.: Precomputing oblivious transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995)
Mohassel, P., Sadeghian, S.: How to hide circuits in mpc: An efficient framework for private function evaluation (2013), http://eprint.iacr.org/
Waksman, A.: A permutation network. J. ACM 15, 159–163 (1968)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
Mohassel, P., Sadeghian, S. (2013). How to Hide Circuits in MPC an Efficient Framework for Private Function Evaluation. In: Johansson, T., Nguyen, P.Q. (eds) Advances in Cryptology – EUROCRYPT 2013. EUROCRYPT 2013. Lecture Notes in Computer Science, vol 7881. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38348-9_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-38348-9_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38347-2
Online ISBN: 978-3-642-38348-9
eBook Packages: Computer ScienceComputer Science (R0)