Secure two-party computation via cut-and-choose oblivious transfer. (English) Zbl 1278.94056

Summary: 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 [the authors, Lect. Notes Comput. Sci. 4515, 52–78 (2007; Zbl 1141.94362)] 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.


94A60 Cryptography
68M12 Network protocols
68P25 Data encryption (aspects in computer science)
94A62 Authentication, digital signatures and secret sharing


Zbl 1141.94362
Full Text: DOI


[1] Aumann, Y.; Lindell, Y., Security against covert adversaries: Efficient protocols for realistic adversaries, J. Cryptol., 23, 2, 281-343 (2010) · Zbl 1181.94091
[2] Beaver, D., Foundations of secure interactive computing, CRYPTO’91, 377-391 (1991), Berlin: Springer, Berlin · Zbl 0789.68044
[3] Canetti, R., Security and composition of multi-party cryptographic protocols, J. Cryptol., 13, 1, 143-202 (2000) · Zbl 0957.68040
[4] Canetti, R., Universally composable security: A new paradigm for cryptographic protocols, 42nd FOCS, 136-145 (2001)
[5] Canetti, R.; Fischlin, M., Universally composable commitments, CRYPTO 2001, 19-40 (2001), Berlin: Springer, Berlin · Zbl 1002.94528
[6] Carter, L.; Wegman, M. N., Universal classes of Hash functions, J. Comput. Syst. Sci., 18, 2, 143-154 (1979) · Zbl 0412.68090
[7] Cramer, R.; Damgård, I.; Schoenmakers, B., Proofs of partial knowledge and simplified design of Witness hiding protocols, CRYPTO’94, 174-187 (1994), Berlin: Springer, Berlin · Zbl 0939.94546
[8] I. Damgård, On Σ protocols. http://www.daimi.au.dk/ ivan/Sigma.pdf · Zbl 1295.94045
[9] Dodis, Y.; Gennaro, R.; Hastad, J.; Krawczyk, H.; Rabin, T., Randomness extraction and key derivation using the CBC, cascade and HMAC modes, CRYPTO 2004, 494-510 (2004), Berlin: Springer, Berlin · Zbl 1104.68470
[10] Dodis, Y.; Shoup, V.; Walfish, S., Efficient constructions of composable commitments and zero-knowledge proofs, CRYPTO 2008, 515-535 (2008), Berlin: Springer, Berlin · Zbl 1183.94030
[11] Even, S.; Goldreich, O.; Lempel, A., A randomized protocol for signing contracts, Commun. ACM, 28, 6, 637-647 (1985)
[12] Garay, J.; MacKenzie, P., K. Yang. Strengthening zero-knowledge protocols using signatures, EUROCRYPT 2003, 177-194 (2003), Berlin: Springer, Berlin · Zbl 1037.68741
[13] Goldreich, O., Foundations of Cryptography: Volume 2—Basic Applications (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1068.94011
[14] Goldreich, O.; Micali, S.; Wigderson, A., How to play any mental game—A completeness theorem for protocols with honest majority, 19th STOC, 218-229 (1987)
[15] Goldwasser, S.; Levin, L., Fair computation of general functions in presence of immoral majority, CRYPTO’90, 77-93 (1990), Berlin: Spring, Berlin · Zbl 0800.68459
[16] Goyal, V.; Mohassel, P., A. Smith. Efficient two party and multi party computation against covert adversaries, EUROCRYPT 2008, 289-306 (2008), Berlin: Springer, Berlin · Zbl 1149.94317
[17] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1998), Reading: Addison-Wesley, Reading
[18] Hastad, J.; Impagliazzo, R.; Levin, L.; Luby, M., Construction of a pseudo-random generator from any one-way function, SIAM J. Comput., 28, 4, 1364-1396 (1999) · Zbl 0940.68048
[19] Hazay, C.; Lindell, Y., Efficient Secure Two-Party Protocols: Techniques and Constructions (2010), Berlin: Springer, Berlin · Zbl 1208.68005
[20] Hazay, C.; Nissim, K., Efficient set operations in the presence of malicious adversaries, PKC 2010, 312-331 (2010), Berlin: Springer, Berlin · Zbl 1281.94029
[21] Ishai, Y.; Prabhakaran, M.; Sahai, A., Founding cryptography on oblivious transfer—Efficiently, CRYPTO 2008, 572-591 (2008), Berlin: Springer, Berlin · Zbl 1183.94037
[22] Ishai, Y.; Prabhakaran, M.; Sahai, A., Secure arithmetic computation with no honest majority, TCC 2009, 294-314 (2009), Berlin: Springer, Berlin · Zbl 1213.94111
[23] Jarecki, S.; Shmatikov, V., Efficient two-party secure computation on committed inputs, EUROCRYPT 2007, 97-114 (2007), Berlin: Springer, Berlin · Zbl 1141.94358
[24] Kiraz, M.; Schoenmakers, B., A protocol issue for the malicious case of Yao’s garbled circuit construction, Proceedings of the 27th Symposium on Information Theory in the Benelux, 283-290 (2006)
[25] Kolesnikov, V.; Schneider, T., Improved garbled circuit: Free XOR gates and applications, 35th ICALP, 486-498 (2008), Berlin: Springer, Berlin · Zbl 1155.94374
[26] Lindell, Y., Parallel coin-tossing and constant-round secure two-party computation, J. Cryptol., 16, 3, 143-184 (2003) · Zbl 1027.94011
[27] Lindell, Y., Highly-efficient universally-composable commitments, EUROCRYPT 2011, 446-466 (2011), Berlin: Springer, Berlin · Zbl 1291.68037
[28] Lindell, Y.; Pinkas, B., An efficient protocol for secure two-party computation in the presence of malicious adversaries, EUROCRYPT 2007, 52-78 (2007), Berlin: Springer, Berlin · Zbl 1141.94362
[29] Lindell, Y.; Pinkas, B., A proof of Yao’s protocol for secure two-party computation, J. Cryptol., 22, 2, 161-188 (2009) · Zbl 1159.94364
[30] MacKenzie, P.; Yang, K., On simulation-sound trapdoor commitments, EUROCRYPT 2004, 382-400 (2004), Berlin: Springer, Berlin · Zbl 1122.94386
[31] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A., Handbook of Applied Cryptography (2001), Boca Raton: CRC Press, Boca Raton · Zbl 0868.94001
[32] S. Micali, P. Rogaway, Secure computation. Unpublished manuscript, 1992. Preliminary version in CRYPTO’91, LNCS, vol. 576 (Springer, Berlin, 1991), pp. 392-404
[33] Mohassel, P.; Franklin, M. K., Efficiency tradeoffs for malicious two-party computation, 9th PKC Conference, 458-473 (2006), Berlin: Springer, Berlin · Zbl 1151.94551
[34] Naor, M.; Reingold, O., Synthesizers and their application to the parallel construction of pseudo-random functions, 36th FOCS, 170-181 (1995) · Zbl 0938.68637
[35] Nielsen, J. B.; Orlandi, C., LEGO for two-party secure computation, TCC 2009, 368-386 (2009), Berlin: Springer, Berlin · Zbl 1213.94124
[36] C. Orlandi, Personal communication, 2010
[37] Peikert, C.; Vaikuntanathan, V.; Waters, B., A framework for efficient and composable oblivious transfer, CRYPTO’08, 554-571 (2008), Berlin: Springer, Berlin · Zbl 1183.94046
[38] Pinkas, B.; Schneider, T.; Smart, N. P., S.C. Williams. Secure two-party computation is practical, ASIACRYPT 2009, 250-267 (2009), Berlin: Springer, Berlin · Zbl 1267.94091
[39] M. Rabin, How to exchange secrets by oblivious transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981
[40] Shamir, A., How to share a secret, Commun. ACM, 22, 11, 612-613 (1979) · Zbl 0414.94021
[41] Yao, A. C., How to generate and exchange secrets, 27th FOCS, 162-167 (1986)
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.