Marcel Keller
ABSTRACT
We consider the task of secure multi-party computation of arithmetic circuits over a finite field. Unlike Boolean circuits, arithmetic circuits allow natural computations on integers to be expressed easily and efficiently. In the strongest setting of malicious security with a dishonest majority --- where any number of parties may deviate arbitrarily from the protocol --- most existing protocols require expensive public-key cryptography for each multiplication in the preprocessing stage of the protocol, which leads to a high total cost. We present a new protocol that overcomes this limitation by using oblivious transfer to perform secure multiplications in general finite fields with reduced communication and computation. Our protocol is based on an arithmetic view of oblivious transfer, with careful consistency checks and other techniques to obtain malicious security at a cost of less than 6 times that of semi-honest security. We describe a highly optimized implementation together with experimental results for up to five parties. By making extensive use of parallelism and SSE instructions, we improve upon previous runtimes for MPC over arithmetic circuits by more than 200 times.
- The Sharemind project. http://sharemind.cs.ut.ee, 2007.Google Scholar
- Asharov, G., Lindell, Y., Schneider, T., and Zohner, M. More efficient oblivious transfer and extensions for faster secure computation. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security (2013), ACM, pp. 535--548. Google ScholarDigital Library
- Baum, C., Damgård, I., Toft, T., and Zakarias, R. Better preprocessing for secure multiparty computation. IACR Cryptology ePrint Archive (2016).Google Scholar
- Beaver, D. Efficient multiparty protocols using circuit randomization. Advances in Cryptology - CRYPTO 1991 (1992). Google ScholarDigital Library
- Beaver, D. Correlated pseudorandomness and the complexity of private computations. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (1996), G. L. Miller, Ed., ACM, pp. 479--488. Google ScholarDigital Library
- Bendlin, R., Damgård, I., Orlandi, C., and Zakarias, S. Semi-homomorphic encryption and multiparty computation. In Advances in Cryptology - EUROCRYPT 2011 (2011), pp. 169--188. Google ScholarCross Ref
- Black, J., Rogaway, P., Shrimpton, T., and Stam, M. An analysis of the blockcipher-based hash functions from PGV. J. Cryptology 23, 4 (2010), 519--545. Google ScholarDigital Library
- Bogdanov, D., J\ oemets, M., Siim, S., and Vaht, M. How the Estonian tax and customs board evaluated a tax fraud detection system based on secure multi-party computation. In Financial Cryptography and Data Security - 19th International Conference, FC 2015, Revised Selected Papers (2015), pp. 227--234.Google Scholar
- Bogdanov, D., Kamm, L., Kubo, B., Rebane, R., Sokk, V., and Talviste, R. Students and taxes: a privacy-preserving social study using secure computation. IACR Cryptology ePrint Archive (2015).Google Scholar
- Burra, S. S., Larraia, E., Nielsen, J. B., Nordholt, P. S., Orlandi, C., Orsini, E., Scholl, P., and Smart, N. P. High performance multi-party computation for binary circuits based on oblivious transfer. Cryptology ePrint Archive, Report 2015/472, 2015. http://eprint.iacr.org/.Google Scholar
- Canetti, R. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS (2001), pp. 136--145. Google ScholarDigital Library
- Chou, T., and Orlandi, C. The simplest protocol for oblivious transfer. In Progress in Cryptology - LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America (2015), pp. 40--58. Google ScholarDigital Library
- Damgård, I., Damgård, K., Nielsen, K., Nordholt, P. S., and Toft, T. Confidential benchmarking based on multiparty computation. In Financial Cryptography (2016).Google Scholar
- Damgård, I., Keller, M., Larraia, E., Miles, C., and Smart, N. P. Implementing AES via an actively/covertly secure dishonest-majority MPC protocol. In SCN (2012), I. Visconti and R. D. Prisco, Eds., vol. 7485 of Lecture Notes in Computer Science, Springer, pp. 241--263. Google ScholarDigital Library
- Damgård, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., and Smart, N. P. Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits. In ESORICS (2013), J. Crampton, S. Jajodia, and K. Mayes, Eds., vol. 8134 of Lecture Notes in Computer Science, Springer, pp. 1--18.Google ScholarCross Ref
- Damgård, I., and Orlandi, C. Multiparty computation for dishonest majority: From passive to active security at low cost. In Advances in Cryptology - CRYPTO (2010), pp. 558--576. Google ScholarDigital Library
- Damgård, I., Pastro, V., Smart, N. P., and Zakarias, S. Multiparty computation from somewhat homomorphic encryption. In Advances in Cryptology -- CRYPTO 2012 (2012), R. Safavi-Naini and R. Canetti, Eds., vol. 7417 of Lecture Notes in Computer Science, Springer, pp. 643--662. Google ScholarDigital Library
- Demmler, D., Schneider, T., and Zohner, M. ABY - A framework for efficient mixed-protocol secure two-party computation. In 22nd Annual Network and Distributed System Security Symposium, NDSS (2015), The Internet Society.Google ScholarCross Ref
- Frederiksen, T. K., Keller, M., Orsini, E., and Scholl, P. A unified approach to MPC with preprocessing using OT. In Advances in Cryptology -- ASIACRYPT 2015, Part I (2015), T. Iwata and J. H. Cheon, Eds., vol. 9452 of Lecture Notes in Computer Science, Springer, pp. 711--735.Google ScholarDigital Library
- Gilboa, N. Two party RSA key generation. In Advances in Cryptology - CRYPTO (1999), pp. 116--129. Google ScholarDigital Library
- Goldreich, O., Micali, S., and Wigderson, A. How to play any mental game or A completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (1987), pp. 218--229. Google ScholarDigital Library
- Intel. Intel intrinsics guide. https://software.intel.com/sites/landingpage/IntrinsicsGuide, 2016. Online; accessed February 2016.Google Scholar
- Ishai, Y., Kilian, J., Nissim, K., and Petrank, E. Extending oblivious transfers efficiently. In Advances in Cryptology - CRYPTO (2003), pp. 145--161.Google ScholarCross Ref
- Ishai, Y., Prabhakaran, M., and Sahai, A. Secure arithmetic computation with no honest majority. In ReingoldciteDBLP:conf/tcc/2009, pp. 294--314. Google ScholarDigital Library
- Kamm, L., and Willemson, J. Secure floating point arithmetic and private satellite collision analysis. International Journal of Information Security 14, 6 (2015), 531--548. Google ScholarDigital Library
- Keller, M., Orsini, E., and Scholl, P. Actively secure OT extension with optimal overhead. In Advances in Cryptology - CRYPTO 2015, Part I (2015), pp. 724--741.Google Scholar
- Keller, M., Orsini, E., and Scholl, P. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer. Cryptology ePrint Archive, Report 2016/505, 2016. http://eprint.iacr.org/2014/505.Google Scholar
- Keller, M., Scholl, P., and Smart, N. P. An architecture for practical actively secure MPC with dishonest majority. In ACM Conference on Computer and Communications Security (2013), pp. 549--560. Google ScholarDigital Library
- Kreuter, B., Shelat, A., and Shen, C. Billion-gate secure computation with malicious adversaries. In Proceedings of the 21st USENIX conference on Security symposium (2012), USENIX Association, pp. 14--14. Google ScholarDigital Library
- Larraia, E., Orsini, E., and Smart, N. P. Dishonest majority multi-party computation for binary circuits. In Advances in Cryptology - CRYPTO 2014, Part II (2014), pp. 495--512.Google Scholar
- Lindell, Y., and Riva, B. Blazing fast 2pc in the offline/online setting with security for malicious adversaries. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (2015), pp. 579--590. Google ScholarDigital Library
- Matyas, S. M., Meyer, C. H., and Oseas, J. Generating strong one-way functions with cryptographic algorithm. IBM Technical Disclosure Bulletin 27, 10A (1985), 5658--5659.Google Scholar
- mischasan. What is sse !@# good for? transposing a bit matrix. https://mischasan.wordpress.com/2011/07/24/what-is-sse-good-for-transposing-a-bit-matrix, 2011. Online; accessed February 2016.Google Scholar
- Nielsen, J. B., Nordholt, P. S., Orlandi, C., and Burra, S. S. A new approach to practical active-secure two-party computation. In Advances in Cryptology--CRYPTO 2012. Springer, 2012, pp. 681--700. Google ScholarDigital Library
- Nielsen, J. B., and Orlandi, C. LEGO for two-party secure computation. In ReingoldciteDBLP:conf/tcc/2009, pp. 368--386. Google ScholarDigital Library
- Peikert, C., Vaikuntanathan, V., and Waters, B. A framework for efficient and composable oblivious transfer. In Advances in Cryptology - CRYPTO (2008), pp. 554--571. Google ScholarDigital Library
- Pinkas, B., Schneider, T., Segev, G., and Zohner, M. Phasing: Private set intersection using permutation-based hashing. In 24th USENIX Security Symposium, USENIX Security 15 (2015), pp. 515--530. Google ScholarDigital Library
- Pinkas, B., Schneider, T., and Zohner, M. Faster private set intersection based on OT extension. In Proceedings of the 23rd USENIX Security Symposium (2014), pp. 797--812. Google ScholarDigital Library
- Reingold, O., Ed. Theory of Cryptography, 6th Theory of Cryptography Conference, TCC (2009), vol. 5444 of Lecture Notes in Computer Science, Springer. Google ScholarDigital Library
- The MPIR team. Multiple precision integers and rationals. https://www.mpir.org, 2016. Online; accessed February 2016.Google Scholar
- Yao, A. C. How to generate and exchange secrets (extended abstract). In 27th Annual Symposium on Foundations of Computer Science (1986). Google ScholarDigital Library
Index Terms
- MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer
Recommendations
Formalising oblivious transfer in the semi-honest and malicious model in CryptHOL
CPP 2020: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and ProofsMulti-Party Computation (MPC) allows multiple parties to compute a function together while keeping their inputs private. Large scale implementations of MPC protocols are becoming practical thus it is important to have strong guarantees for the whole ...
Efficient Multi-Party Private Set Intersection Against Malicious Adversaries
CCSW'19: Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security WorkshopPrivate set intersection (PSI) enables parties to compute the intersection of their inputs without leaking any additional information. Recently, there have been significant advances in the two-party settings with malicious security, making two-party PSI ...
Two-round Multiparty Secure Computation from Minimal Assumptions
We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest ...
Comments