×

High-performance multi-party computation for binary circuits based on oblivious transfer. (English) Zbl 1470.94080

Summary: We present a unified view of the two-party and multi-party computation protocols based on oblivious transfer first outlined in [J. B. Nielsen et al., Lect. Notes Comput. Sci. 7417, 681–700 (2012; Zbl 1296.94134)] and E. Larraia et al. [ibid. 8617, 495–512 (2014; Zbl 1335.94064)]. We present a number of modifications and improvements to these earlier presentations, as well as full proofs of the entire protocol. Improvements include a unified pre-processing and online MAC methodology, mechanisms to pass between different MAC variants and fixing a minor bug in the protocol of Larraia et al. [loc. cit.] in relation to a selective failure attack. It also fixes a minor bug in Nielsen et al. [loc. cit.] resulting from using Jensen’s inequality in the wrong direction in an analysis.

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] B. Applebaum, D. Harnik, Y. Ishai, Semantic security under related-key attacks and applications, in Bernard Chazelle, editor, ICS (Tsinghua University Press, 2011), pp. 45-60
[2] A. Shelat, C.-H. Shen, Two-output secure computation with malicious adversaries, in Paterson [46], pp. 386-405 · Zbl 1282.68086
[3] A. Ben-David, N. Nisan, B. Pinkas, FairplayMP: a system for secure multi-party computation, in Peng Ning, Paul F. Syverson, and Somesh Jha, editors, CCS (ACM, 2008), pp. 257-266
[4] R. Bendlin, I. Damgård, C. Orlandi, S. Zakarias, Semi-homomorphic encryption and multiparty computation, in Paterson [46], pp. 169-188 · Zbl 1281.94015
[5] D. Beaver, Precomputing oblivious transfer, in Don Coppersmith, editor, Advances in Cryptology—CRYPTO ’95, 15th Annual International Cryptology Conference, Santa Barbara, California, USA, August 27-31, 1995, Proceedings. Lecture Notes in Computer Science, vol. 963 (Springer, 1995), pp. 97-109 · Zbl 0876.94021
[6] D. Beaver, Correlated pseudorandomness and the complexity of private computations, in Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 (ACM, 1996), pp. 479-488 · Zbl 0917.94012
[7] D. Bogdanov, S. Laur, W. Sharemind, A framework for fast privacy-preserving computations, in European Symposium on Research in Computer Security—ESORICS 2008. LNCS, vol. 5283 (Springer, 2008), pp. 192-206
[8] R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in FOCS (2001), pp. 136-145
[9] Canetti, R., Universally composable security, J. ACM, 67, 5, 28:1-28:94 (2020)
[10] R. Canetti, A. Cohen, Y. Lindell, A simpler variant of universally composable security for standard multiparty computation, in Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9216 (Springer, 2015), pp. 3-22. · Zbl 1351.94031
[11] R. Cramer, I. Damgård, D. Escudero, P. Scholl, C. Xing, Spd \(F_{2^{\text{k}}} \): efficient MPC mod \(2{}^{\text{ k }}\) for dishonest majority, in Hovav Shacham, Alexandra Boldyreva, editors, Advances in Cryptology—CRYPTO 2018—38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10992. (Springer, 2018), pp. 769-798 · Zbl 1436.94049
[12] S.G. Choi, K.-W. Hwang, J. Katz, T. Malkin, D. Rubenstein, Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces, in Orr Dunkelman, editor, CT-RSA. Lecture Notes in Computer Science, vol. 7178 (Springer, 2012), pp. 416-432 · Zbl 1292.94047
[13] S.G. Choi, J. Katz, R. Kumaresan, H.-S. Zhou, On the security of the “free-xor” technique, in Ronald Cramer, editor, TCC. Lecture Notes in Computer Science, vol. 7194 (Springer, 2012), pp. 39-53 · Zbl 1303.94075
[14] I. Damgård, M. Geisler, M. Krøigaard, J.B. Nielsen, Asynchronous multiparty computation: theory and implementation, in Stanislaw Jarecki and Gene Tsudik, editors, Public Key Cryptography - PKC 2009, 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5443 (Springer, 2009), pp. 160-179 · Zbl 1227.68014
[15] I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, N.P. Smart, Practical covertly secure mpc for dishonest majority - or: breaking the spdz limits, in Jason Crampton, Sushil Jajodia, and Keith Mayes, editors, ESORICS. Lecture Notes in Computer Science, vol. 8134 (Springer, 2013), pp. 1-18 · Zbl 1406.94041
[16] I. Damgård, C. Orlandi, Multiparty computation for dishonest majority: from passive to active security at low cost, in Tal Rabin, editor, CRYPTO. Lecture Notes in Computer Science, vol. 6223 (Springer, 2010), pp. 558-576 · Zbl 1284.68064
[17] I. Damgård, V. Pastro, N.P. Smart, S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in Safavi-Naini and Canetti [50], pp. 643-662 · Zbl 1296.94104
[18] I. Damgård, S. Zakarias, Constant-overhead secure computation of Boolean circuits using preprocessing, in TCC (2013), pp. 621-641. · Zbl 1315.94068
[19] T.K. Frederiksen, T.P. Jakobsen, J.B. Nielsen, P.S. Nordholt, C. Orlandi, Minilego: efficient secure two-party computation from general assumptions, in Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT. Lecture Notes in Computer Science, vol. 7881 (Springer, 2013), pp. 537-556 · Zbl 1312.94049
[20] T.K. Frederiksen, M. Keller, E. Orsini, P. Scholl, A unified approach to MPC with preprocessing using OT, in Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29-December 3, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9452 (Springer, 2015), pp. 711-735 · Zbl 1396.94077
[21] O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in STOC (ACM, 1987), pp. 218-229
[22] O. Goldreich, Foundations of Cryptography, vol. 2. Cambridge University Press (2004). http://www.wisdom.weizmann.ac.il/ oded/foc-vol2.html · Zbl 1068.94011
[23] Y. Huang, D. Evans, J. Katz, L. Malka, Faster secure two-party computation using garbled circuits, in USENIX Security Symposium (2011)
[24] D. Harnik, Y. Ishai, E. Kushilevitz, J.B. Nielsen, OT-combiners via secure computation, in Ran Canetti, editor, TCC. Lecture Notes in Computer Science, vol. 4948 (Springer, 2008), pp. 393-411 · Zbl 1162.94366
[25] D. Harnik, J. Kilian, M. Naor, O. Reingold, A. Rosen, On robust combiners for oblivious transfer and other primitives, in Ronald Cramer, editor, EUROCRYPT. Lecture Notes in Computer Science, vol. 3494 (Springer, 2005), pp. 96-113 · Zbl 1137.94346
[26] W. Henecka, S. Kögl, A.-R. Sadeghi, T. Schneider, I. Wehrenberg, Tasty: tool for automating secure two-party computations, in CCS (2010), pp. 451-462.
[27] C. Hazay, E. Orsini, P. Scholl, E. Soria-Vazquez, Concretely efficient large-scale MPC with active security (or, tinykeys for tinyot), in Thomas Peyrin and Steven D. Galbraith, editors, Advances in Cryptology—ASIACRYPT 2018—24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part III. Lecture Notes in Computer Science, vol. 11274 (Springer, 2018), pp. 86-117 · Zbl 1447.94042
[28] C. Hazay, E. Orsini, P. Scholl, E. Soria-Vazquez, Tinykeys: a new approach to efficient multi-party computation, in Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology—CRYPTO 2018—38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III. Lecture Notes in Computer Science, vol. 10993 (Springer, 2018), pp. 3-33 · Zbl 1446.94135
[29] C. Hazay, P. Scholl, E. Soria-Vazquez, Low cost constant round MPC combining BMR and oblivious transfer, in Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology—ASIACRYPT 2017—23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10624 (Springer, 2017), pp. 598-628 · Zbl 1420.94072
[30] Y. Ishai, J. Kilian, K. Nissim, E. Petrank, Extending oblivious transfers efficiently, in Dan Boneh, editor, CRYPTO. Lecture Notes in Computer Science, vol. 2729 (Springer, 2003), pp. 145-161. · Zbl 1122.94422
[31] Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Cryptography with constant computational overhead, in Cynthia Dwork, editor, STOC (ACM, 2008), pp. 433-442. · Zbl 1231.94050
[32] Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer—efficiently, in David Wagner, editor, CRYPTO. Lecture Notes in Computer Science, vol. 5157 (Springer, 2008), pp. 572-591 · Zbl 1183.94037
[33] Y. Ishai, M. Prabhakaran, A. Sahai, Secure arithmetic computation with no honest majority, in Reingold [48], pp. 294-314. · Zbl 1213.94111
[34] T.P. Jakobsen, M.X. Makkes, J.D. Nielsen, Efficient implementation of the orlandi protocol, in Jianying Zhou and Moti Yung, editors, ACNS. Lecture Notes in Computer Science, vol. 6123 (2010), pp. 255-272. · Zbl 1350.94038
[35] M. Keller, E. Orsini, P. Scholl, MASCOT: faster malicious arithmetic secure computation with oblivious transfer, in Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016 (ACM, 2016), pp. 830-842.
[36] V. Kolesnikov, T. Schneider, Improved garbled circuit: free xor gates and applications, in Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, ICALP (2). Lecture Notes in Computer Science, vol. 5126 (Springer, 2008), pp. 486-498. · Zbl 1155.94374
[37] Y. Lindell, E. Oxman, B. Pinkas, The ips compiler: optimizations, variants and concrete efficiency, in Phillip Rogaway, editor, CRYPTO. Lecture Notes in Computer Science, vol 6841 (Springer, 2011), pp. 259-276. · Zbl 1288.68023
[38] E. Larraia, E. Orsini, N.P. Smart, Dishonest majority multi-party computation for binary circuits, in Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II. Lecture Notes in Computer Science, vol. 8617 (Springer, 2014), pp. 495-512. · Zbl 1335.94064
[39] Y. Lindell, B. Pinkas, Secure two-party computation via cut-and-choose oblivious transfer, in Yuval Ishai, editor, Theory of Cryptography—8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6597 (Springer, 2011), pp. 329-346 · Zbl 1281.94037
[40] Y. Lindell, B. Pinkas, N.P. Smart, Implementing two-party computation efficiently with security against malicious adversaries, in Rafail Ostrovsky, Roberto De Prisco, and Ivan Visconti, editors, SCN. Lecture Notes in Computer Science, vol. 5229 (Springer, 2008), pp. 2-20. · Zbl 1180.68152
[41] L. Malka, J. Katz, VMCrypt—modular software architecture for scalable secure computation. Cryptology ePrint Archive, Report 2010/584 (2010). http://eprint.iacr.org/
[42] D. Malkhi, N. Nisan, B. Pinkas, Y. Sella, Fairplay—secure two-party computation system, in USENIX Security Symposium (USENIX, 2004), pp. 287-302
[43] J.B. Nielsen, Extending oblivious transfers efficiently—how to get robustness almost for free. Cryptology ePrint Archive, Report 2007/215 (2007). http://eprint.iacr.org/
[44] J.B. Nielsen, P.S. Nordholt, C. Orlandi, S.S. Burra. A new approach to practical active-secure two-party computation, in Safavi-Naini and Canetti [50]. Full version in IACR ePrint 2011/091, pp. 681-700. https://eprint.iacr.org/2011/091 · Zbl 1296.94134
[45] J.B. Nielsen, C. Orlandi, LEGO for two-party secure computation, in Reingold [48], pp. 368-386 · Zbl 1213.94124
[46] K.G. Paterson, editor, Advances in Cryptology—EUROCRYPT 2011—30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6632 (Springer, 2011)
[47] B. Pinkas, T. Schneider, N.P. Smart, S.C. Williams, Secure two-party computation is practical, in Mitsuru Matsui, editor, ASIACRYPT. Lecture Notes in Computer Science, vol. 5912 (Springer, 2009), pp. 250-267 · Zbl 1267.94091
[48] O. Reingold, editor. Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5444 (Springer, 2009). · Zbl 1156.94005
[49] SIMAP Project. SIMAP: secure information management and processing. http://alexandra.dk/uk/Projects/Pages/SIMAP.aspx
[50] Reihaneh Safavi-Naini and Ran Canetti, editors. Advances in Cryptology—CRYPTO 2012—32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7417 (Springer, 2012). · Zbl 1246.94010
[51] X. Wang, S. Ranellucci, J. Katz, Authenticated garbling and efficient maliciously secure two-party computation, in Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30-November 03, 2017 (ACM, 2017), pp. 21-37
[52] X. Wang, S. Ranellucci, J. Katz, Global-scale secure multiparty computation, in Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30-November 03, 2017 (ACM, 2017), pp. 39-56
[53] A.C.-C. Yao, Protocols for secure computations (extended abstract), in FOCS (IEEE, 1982), pp. 160-164
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.