Abstract
Secure multiparty computation (MPC) permits a collection of parties to compute a collaborative result without any of the parties or compute servers gaining any knowledge about the inputs provided by other parties, except what can be determined from the output of the computation. In the form of MPC known as linear (or additive) sharing, computation proceeds on data that appears entirely random. Operations such as addition or logical-XOR can be performed purely locally, but operations such as multiplication or logical-AND require a network communication between the parties. Consequently, the computational overhead of MPC is large, and the cost is still measured in orders of magnitude slowdown with respect to computing in the clear. However, efficiency improvements over the last few years have shifted the potential applicability of MPC from just micro benchmarks to user-level applications.
To assess how close MPC is to real world use we implement and assess two very different MPC-based applications—secure email filtering and secure teleconference VoIP. Because the computation cost model is very different from traditional machines, the implementations required a significantly different set of algorithmic and compiler techniques. We describe a collection of the techniques we found to be important, including SAT-based circuit optimization and an optimized table lookup primitive.
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
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)
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)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: Proc. of IEEE Conference on the Foundations of Computer Science (FOCS) (1995)
Damgaard, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.: Practical Covertly Secure MPC for Dishonest Majority or: Breaking the SPDZ Limits. In: Crampton, J., Jajodia, S., Mayes, K. (eds.) ESORICS 2013. LNCS, vol. 8134, pp. 1–18. Springer, Heidelberg (2013)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: ACM Symposium on Theory of Computing (STOC 2009) (2009)
Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press (2004)
Launchbury, J., Adams-Moran, A., Diatchki, I.: Efficient Lookup-Table Protocol in Secure Multiparty Computation. In: Proc. International Conference on Functional Programming (ICFP) (2012)
Lonsing, F., Biere, A.: DepQBF: A Dependency-Aware QBF Solver. JSAT 7, 2–3 (2010)
Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations (2011) Manuscript at, http://eprint.iacr.org/2011/133
Yao, A.C.: How to generate and exchange secrets. In: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (1986)
Fischer, S., Huch, F., Wilke, T.: A Play on Regular Expressions: Functional Pearl. In: Proceedings of the International Conference on Functional Programming, ICFP 2010 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Launchbury, J., Archer, D., DuBuisson, T., Mertens, E. (2014). Application-Scale Secure Multiparty Computation. In: Shao, Z. (eds) Programming Languages and Systems. ESOP 2014. Lecture Notes in Computer Science, vol 8410. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54833-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-54833-8_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54832-1
Online ISBN: 978-3-642-54833-8
eBook Packages: Computer ScienceComputer Science (R0)