{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T11:31:32Z","timestamp":1780572692603,"version":"3.54.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["4.47E+12"],"award-info":[{"award-number":["4.47E+12"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2004240"],"award-info":[{"award-number":["2004240"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>\n            In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is\n            <jats:italic>fairness<\/jats:italic>\n            which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved\n            <jats:italic>in general<\/jats:italic>\n            without an honest majority. Since then, the accepted folklore has been that\n            <jats:italic>nothing<\/jats:italic>\n            non-trivial can be computed with complete fairness in the two-party setting.\n          <\/jats:p>\n          <jats:p>\n            We demonstrate that this folklore belief is\n            <jats:italic>false<\/jats:italic>\n            by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an \u201cembedded XOR\u201d; this class of functions includes boolean AND\/OR as well as Yao\u2019s \u201cmillionaires\u2019 problem\u201d. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.\n          <\/jats:p>","DOI":"10.1145\/2049697.2049698","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T15:45:47Z","timestamp":1323791147000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["Complete Fairness in Secure Two-Party Computation"],"prefix":"10.1145","volume":"58","author":[{"given":"S. Dov","family":"Gordon","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carmit","family":"Hazay","sequence":"additional","affiliation":[{"name":"Aarhus University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Katz","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yehuda","family":"Lindell","sequence":"additional","affiliation":[{"name":"Bar-Ilan University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196771"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/646756.705508"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63520"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Conference on Advances in Cryptology (Crypto\u201910)","volume":"6223","author":"Beimel A.","unstructured":"Beimel , A. , Omri , E. , and Orlov , I . 2010. Protocols for multiparty coin toss with dishonest majority . In Proceedings of the Conference on Advances in Cryptology (Crypto\u201910) . Lecture Notes in Computer Science , vol. 6223 . Springer, 538--557. Beimel, A., Omri, E., and Orlov, I. 2010. Protocols for multiparty coin toss with dishonest majority. In Proceedings of the Conference on Advances in Cryptology (Crypto\u201910). Lecture Notes in Computer Science, vol. 6223. Springer, 538--557."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Conference on Advances in Cryptology (Crypto\u201911)","volume":"6841","author":"Beimel A.","unstructured":"Beimel , A. , Lindell , Y. , Omri , E. , and Orlov , I . 2011. 1\/p-secure multiparty computation without honest majority and the best of both worlds . In Proceedings of the Conference on Advances in Cryptology (Crypto\u201911) . Lecture Notes in Computer Science , vol. 6841 . Springer, 277--196. Beimel, A., Lindell, Y., Omri, E., and Orlov, I. 2011. 1\/p-secure multiparty computation without honest majority and the best of both worlds. In Proceedings of the Conference on Advances in Cryptology (Crypto\u201911). Lecture Notes in Computer Science, vol. 6841. Springer, 277--196."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.50372"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/357360.357368"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Conference on Advances in Cryptology (Crypto\u201900)","volume":"1880","author":"Boneh D.","unstructured":"Boneh , D. and Naor , M . 2000. Timed commitments . In Proceedings of the Conference on Advances in Cryptology (Crypto\u201900) . Lecture Notes in Computer Science , vol. 1880 . Springer, 236--254. Boneh, D. and Naor, M. 2000. Timed commitments. In Proceedings of the Conference on Advances in Cryptology (Crypto\u201900). Lecture Notes in Computer Science, vol. 1880. Springer, 236--254."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12168"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646754.705053"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00191356"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3812.3818"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Conference on Advances in Cryptology (Crypto\u201987)","volume":"293","author":"Galil Z.","unstructured":"Galil , Z. , Haber , S. , and Yung , M . 1988. Cryptographic computation: Secure fault-tolerant protocols and the public-key model . In Proceedings of the Conference on Advances in Cryptology (Crypto\u201987) . Lecture Notes in Computer Science , vol. 293 . Springer, 135--155. Galil, Z., Haber, S., and Yung, M. 1988. Cryptographic computation: Secure fault-tolerant protocols and the public-key model. In Proceedings of the Conference on Advances in Cryptology (Crypto\u201987). Lecture Notes in Computer Science, vol. 293. Springer, 135--155."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-010-9080-z"},{"key":"e_1_2_1_19_1","volume-title":"Basic Applications","author":"Goldreich O.","unstructured":"Goldreich , O. 2004. Foundations of Cryptography Vol. 2 : Basic Applications . Cambridge University Press , Cambridge, UK . Goldreich, O. 2004. Foundations of Cryptography Vol. 2: Basic Applications. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Advances in Cryptology (Crypto\u201990)","volume":"537","author":"Goldwasser S.","unstructured":"Goldwasser , S. and Levin , L. A . 1991. Fair computation of general functions in presence of immoral majority . In Proceedings of the Conference on Advances in Cryptology (Crypto\u201990) . Lecture Notes in Computer Science , vol. 537 . Springer, 77--93. Goldwasser, S. and Levin, L. A. 1991. Fair computation of general functions in presence of immoral majority. In Proceedings of the Conference on Advances in Cryptology (Crypto\u201990). Lecture Notes in Computer Science, vol. 537. Springer, 77--93."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_2"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Gordon S. D. Hazay C. Katz J. and Lindell Y. 2008. Complete fairness in secure two-party computation. http:\/\/eprint.iacr.org. Gordon S. D. Hazay C. Katz J. and Lindell Y. 2008. Complete fairness in secure two-party computation. http:\/\/eprint.iacr.org.","DOI":"10.1145\/1374376.1374436"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783224"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62215"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103475"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-002-0143-7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.25"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Conference on Advances in Cryptology (Crypto\u201991)","volume":"576","author":"Micali S.","unstructured":"Micali , S. and Rogaway , P . 1992. Secure computation . In Proceedings of the Conference on Advances in Cryptology (Crypto\u201991) . Lecture Notes in Computer Science , vol. 576 . Springer, 392--404. Micali, S. and Rogaway, P. 1992. Secure computation. In Proceedings of the Conference on Advances in Cryptology (Crypto\u201991). Lecture Notes in Computer Science, vol. 576. Springer, 392--404."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1766171.1766179"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73014"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049698","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2049697.2049698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:41Z","timestamp":1750278401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2049697.2049698"],"URL":"https:\/\/doi.org\/10.1145\/2049697.2049698","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2008-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}