Abstract
Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao’s protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Y. Aumann, Y. Lindell, Security against covert adversaries: Efficient protocols for realistic adversaries. J. Cryptol. 23(2), 281–343 (2010)
D. Beaver, Foundations of secure interactive computing, in CRYPTO’91. LNCS, vol. 576 (Springer, Berlin, 1991), pp. 377–391
R. Canetti, Security and composition of multi-party cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)
R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, in 42nd FOCS (2001), pp. 136–145. Full version available at http://eprint.iacr.org/2000/067
R. Canetti, M. Fischlin, Universally composable commitments, in CRYPTO 2001. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 19–40
L. Carter, M.N. Wegman, Universal classes of Hash functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979)
R. Cramer, I. Damgård, B. Schoenmakers, Proofs of partial knowledge and simplified design of Witness hiding protocols, in CRYPTO’94. LNCS, vol. 839 (Springer, Berlin, 1994), pp. 174–187
I. Damgård, On Σ protocols. http://www.daimi.au.dk/~ivan/Sigma.pdf
Y. Dodis, R. Gennaro, J. Hastad, H. Krawczyk, T. Rabin, Randomness extraction and key derivation using the CBC, cascade and HMAC modes, in CRYPTO 2004. LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 494–510
Y. Dodis, V. Shoup, S. Walfish, Efficient constructions of composable commitments and zero-knowledge proofs, in CRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 515–535
S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)
J. Garay, P. MacKenzie, K. Yang. Strengthening zero-knowledge protocols using signatures, in EUROCRYPT 2003. LNCS, vol. 2656 (Springer, Berlin, 2003), pp. 177–194
O. Goldreich, Foundations of Cryptography: Volume 2—Basic Applications (Cambridge University Press, Cambridge, 2004)
O. Goldreich, S. Micali, A. Wigderson, How to play any mental game—A completeness theorem for protocols with honest majority, in 19th STOC (1987), pp. 218–229. For details see [13, Chap. 7]
S. Goldwasser, L. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO’90. LNCS, vol. 537 (Spring, Berlin, 1990), pp. 77–93
V. Goyal, P. Mohassel, A. Smith. Efficient two party and multi party computation against covert adversaries, in EUROCRYPT 2008. LNCS, vol. 4965 (Springer, Berlin, 2008), pp. 289–306
R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edn. (Addison-Wesley, Reading, 1998)
J. Hastad, R. Impagliazzo, L. Levin, M. Luby, Construction of a pseudo-random generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)
C. Hazay, Y. Lindell, Efficient Secure Two-Party Protocols: Techniques and Constructions (Springer, Berlin, 2010)
C. Hazay, K. Nissim, Efficient set operations in the presence of malicious adversaries, in PKC 2010. LNCS, vol. 6056 (Springer, Berlin, 2010), pp. 312–331
Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer—Efficiently, in CRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 572–591
Y. Ishai, M. Prabhakaran, A. Sahai, Secure arithmetic computation with no honest majority, in TCC 2009. LNCS, vol. 5444 (Springer, Berlin, 2009), pp. 294–314
S. Jarecki, V. Shmatikov, Efficient two-party secure computation on committed inputs, in EUROCRYPT 2007. LNCS, vol. 4515 (Springer, Berlin, 2007), pp. 97–114
M. Kiraz, B. Schoenmakers, A protocol issue for the malicious case of Yao’s garbled circuit construction, in Proceedings of the 27th Symposium on Information Theory in the Benelux (2006), pp. 283–290
V. Kolesnikov, T. Schneider, Improved garbled circuit: Free XOR gates and applications, in 35th ICALP. LNCS, vol. 5126 (Springer, Berlin, 2008), pp. 486–498
Y. Lindell, Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol. 16(3), 143–184 (2003)
Y. Lindell, Highly-efficient universally-composable commitments, in EUROCRYPT 2011. LNCS, vol. 6632 (Springer, Berlin, 2011), pp. 446–466
Y. Lindell, B. Pinkas, An efficient protocol for secure two-party computation in the presence of malicious adversaries, in EUROCRYPT 2007. LNCS, vol. 4515 (Springer, Berlin, 2007), pp. 52–78
Y. Lindell, B. Pinkas, A proof of Yao’s protocol for secure two-party computation. J. Cryptol. 22(2), 161–188 (2009)
P. MacKenzie, K. Yang, On simulation-sound trapdoor commitments, in EUROCRYPT 2004. LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 382–400
A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 2001)
S. Micali, P. Rogaway, Secure computation. Unpublished manuscript, 1992. Preliminary version in CRYPTO’91, LNCS, vol. 576 (Springer, Berlin, 1991), pp. 392–404
P. Mohassel, M.K. Franklin, Efficiency tradeoffs for malicious two-party computation, in 9th PKC Conference. LNCS, vol. 3958 (Springer, Berlin, 2006), pp. 458–473
M. Naor, O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions, in 36th FOCS (1995), pp. 170–181
J.B. Nielsen, C. Orlandi, LEGO for two-party secure computation, in TCC 2009. LNCS, vol. 5444 (Springer, Berlin, 2009), pp. 368–386
C. Orlandi, Personal communication, 2010
C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, in CRYPTO’08. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 554–571
B. Pinkas, T. Schneider, N.P. Smart, S.C. Williams. Secure two-party computation is practical, in ASIACRYPT 2009. LNCS, vol. 5912 (Springer, Berlin, 2009), pp. 250–267
M. Rabin, How to exchange secrets by oblivious transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981
A. Shamir, How to share a secret. Commun. ACM 22(11), 612–613 (1979)
A.C. Yao, How to generate and exchange secrets, in 27th FOCS (1986), pp. 162–167
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Hugo Krawczyk
An extended abstract of this work appeared at TCC 2011.
Rights and permissions
About this article
Cite this article
Lindell, Y., Pinkas, B. Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer. J Cryptol 25, 680–722 (2012). https://doi.org/10.1007/s00145-011-9107-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-011-9107-0