{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:42Z","timestamp":1787340222256,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide \u201cfull security\u201d (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the \u201cbest of both worlds\u201d: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.<\/jats:p>","DOI":"10.1137\/100783224","type":"journal-article","created":{"date-parts":[[2011,2,10]],"date-time":"2011-02-10T19:24:36Z","timestamp":1297365876000},"page":"122-141","source":"Crossref","is-referenced-by-count":26,"title":["On Achieving the \u201cBest of Both Worlds\u201d in Secure Multiparty Computation"],"prefix":"10.1137","volume":"40","author":[{"given":"Yuval","family":"Ishai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yehuda","family":"Lindell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erez","family":"Petrank","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,2,10]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Y. Aumann and Y. Lindell,\n                      Security against covert adversaries: Efficient protocols for realistic adversaries\n                      , in Proceedings of the 4th Annual Theory of Cryptography Conference (TCC 2007), Lecture Notes in Comput. Sci. 4392, Springer, Berlin, 2007, pp. 137\u2013156.","DOI":"10.1007\/978-3-540-70936-7_8"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"D. Beaver,\n                      Multiparty protocols tolerating half faulty processors\n                      , in Advances in Cryptology (Crypto'89), Lecture Notes in Comput. Sci. 435, Springer-Verlag, New York, 1990, pp. 560\u2013572.","DOI":"10.1007\/0-387-34805-0_49"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"D. Beaver and S. Goldwasser,\n                      Multiparty computation with faulty majority\n                      , in Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Piscataway, NJ, 1989, pp. 468\u2013473.","DOI":"10.1109\/SFCS.1989.63520"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, and A. Wigderson,\n                      Completeness theorems for noncryptographic fault-tolerant distributed computation\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1988, pp. 1\u201310.","DOI":"10.1145\/62212.62213"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"R. Canetti,\n                      Universally composable security: A new paradigm for cryptographic protocols\n                      , in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Piscataway, NJ, 2001, pp. 136\u2013145.","DOI":"10.1109\/SFCS.2001.959888"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/1165555.1165570"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Cr\u00e9peau, and I. Damg\u00e5rd,\n                      Multiparty unconditionally secure protocols\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1988, pp. 11\u201319.","DOI":"10.1145\/62212.62214"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. Cleve,\n                      Limits on the security of coin flips when half the processors are faulty\n                      , in Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1986, pp. 364\u2013369.","DOI":"10.1145\/12130.12168"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. Cramer, I. Damg\u00e5rd, S. Dziembowski, M. Hirt, and T. Rabin,\n                      Efficient multiparty computations secure against an adaptive adversary\n                      , in Advances in Cryptology (Eurocrypt'99), Lecture Notes in Comput. Sci. 1592, Springer-Verlag, Berlin, 1999, pp. 311\u2013326.","DOI":"10.1007\/3-540-48910-X_22"},{"key":"R11","unstructured":"O. Goldreich,\n                      Foundations of Cryptography, Vol.\n                      2:\n                      Basic Applications\n                      , Cambridge University Press, Cambridge, UK, 2004."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson,\n                      How to play any mental game, or a completeness theorem for protocols with honest majority\n                      , in Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1987, pp. 218\u2013229.","DOI":"10.1145\/28395.28420"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"S. Goldwasser and L. A. Levin,\n                      Fair computation of general functions in presence of immoral majority\n                      , in Advances in Cryptology (Crypto'90), Lecture Notes in Comput. Sci. 537, Springer-Verlag, Berlin, 1991, pp. 77\u201393.","DOI":"10.1007\/3-540-38424-3_6"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-005-0319-z"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"S. D. Gordon, C. Hazay, J. Katz, and Y. Lindell,\n                      Complete fairness in secure two-party computation\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 2008, pp. 413\u2013422.","DOI":"10.1145\/1374376.1374436"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. D. Gordon and J. Katz,\n                      Complete fairness in multiparty computation without an honest majority\n                      , in Proceedings of the 6th Annual Theory of Cryptography Conference (TCC 2009), Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 19\u201335.","DOI":"10.1007\/978-3-642-00457-5_2"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"S. D. Gordon and J. Katz,\n                      Partial fairness in secure two-party computation\n                      , in Advances in Cryptology (Eurocrypt 2010), Lecture Notes in Comput. Sci. 6110, Springer, Berlin, 2010, pp. 157\u2013176.","DOI":"10.1007\/978-3-642-13190-5_8"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Y. Ishai, E. Kushilevitz, Y. Lindell, and E. Petrank,\n                      On combining privacy with guaranteed output delivery in secure multiparty computation\n                      , in Advances in Cryptology (Crypto 2006), Lecture Notes in Comput. Sci. 4117, Springer-Verlag, Berlin, 2006, pp. 483\u2013500.","DOI":"10.1007\/11818175_29"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Katz,\n                      On achieving the \u201cbest of both worlds\u201d in secure multiparty computation\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 2007, pp. 11\u201320.","DOI":"10.1145\/1250790.1250793"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"T. Rabin and M. Ben-Or,\n                      Verifiable secret sharing and multiparty protocols with honest majority\n                      , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), ACM Press, New York, 1989, pp 73\u201385.","DOI":"10.1145\/73007.73014"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao,\n                      How to generate and exchange secrets\n                      , in Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Piscataway, NJ, 1986, pp. 162\u2013167.","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100783224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:40Z","timestamp":1787336740000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100783224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100783224"],"URL":"https:\/\/doi.org\/10.1137\/100783224","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}