{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:21Z","timestamp":1787340321500,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"Frankel Center for Computer Science"},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["FP\/2007-2013"],"award-info":[{"award-number":["FP\/2007-2013"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["239868"],"award-info":[{"award-number":["239868"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["189\/11"],"award-info":[{"award-number":["189\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["544\/13"],"award-info":[{"award-number":["544\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["152\/17"],"award-info":[{"award-number":["152\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["152\/17"],"award-info":[{"award-number":["152\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Fairness is a desirable property in secure computation; informally it means that if one party gets the output of the function, then all parties get the output. Alas, an implication of Cleve\u2019s result [18th ACM Symposium on the Theory of Computing, 1986] is that when there is no honest majority, in particular in the important case of the two-party setting, there exist functions that cannot be computed with fairness. In a surprising result, Gordon et\u00a0al.\u00a0[18th ACM Symposium on the Theory of Computing, 2008; J. ACM, 58 (2011), 24] showed that some interesting functions can be computed with fairness in the two-party setting and reopened the question of understanding which Boolean functions can be computed with fairness, and which cannot. Our main result in this work is a complete characterization of the (symmetric) Boolean functions that can be computed with fairness in the two-party setting; this settles an open problem of Gordon et\u00a0al. The statement of the characterization is quite simple: A function can be computed with fairness if and only if the all-one vector or the all-zero vector are in the affine span of either the rows or the columns of the matrix describing the function. This is true for both deterministic and randomized functions. To prove the possibility result, we modify the protocol of Gordon et\u00a0al.; the resulting protocol computes with full security (and in particular with fairness) all functions that are computable with fairness. Complementing this result, we also show that any function that does not satisfy the aforementioned condition can be reduced to a fair sampling protocol, which, by Agrawal and Prabhakaran [ Advances in Cryptology \u2013 CRYPTO 2013, 2013], cannot be computed with fairness.<\/jats:p>","DOI":"10.1137\/18m1232656","type":"journal-article","created":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T04:14:07Z","timestamp":1727064847000},"page":"1381-1408","source":"Crossref","is-referenced-by-count":0,"title":["Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions"],"prefix":"10.1137","volume":"53","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[{"name":"Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amos","family":"Beimel","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben Gurion University, Be\u2019er Sheva, 84104, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9818-456X","authenticated-orcid":true,"given":"Nikolaos","family":"Makriyannis","sequence":"additional","affiliation":[{"name":"Fireblocks, Tel Aviv, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Omri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ariel University, Ariel, 40700, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,9,23]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_15"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"M. Andrychowicz, S. Dziembowski, D. Malinowski, and L. Mazurek, Secure multiparty computations on bitcoin, in Proceedings of the 2014 IEEE Symposium on Security and Privacy, SP 2014, IEEE Computer Society, Berkeley, CA, 2014, pp. 443\u2013458.","DOI":"10.1109\/SP.2014.35"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"G. Asharov, Towards characterizing complete fairness in secure two-party computation, in Proceedings of the Eleventh Theory of Cryptography Conference \u2013 TCC 2014, Vol. 8349, Springer-Verlag, Berlin, 2014, pp. 291\u2013316.","DOI":"10.1007\/978-3-642-54242-8_13"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"G. Asharov, Y. Lindell, and T. Rabin, A full characterization of functions that imply fair coin tossing and ramifications to fairness, in Proceedings of the Tenth Theory of Cryptography Conference \u2013 TCC 2013, Lecture Notes in Computer Science 7785, Springer-Verlag, Berlin, 2013, pp. 243\u2013262.","DOI":"10.1007\/978-3-642-36594-2_14"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"G. Asharov, A. Beimel, N. Makriyannis, and E. Omri, Complete characterization of fairness in secure two-party computation of Boolean functions, in Proceedings of the Eleventh Theory of Cryptography Conference \u2013 TCC 2014, Lect. Notes Comput. Sci. 9014, Springer-Verlag, Berlink 2015, pp. 199\u2013228.","DOI":"10.1007\/978-3-662-46494-6_10"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14623-7_29"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_16"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, O. Goldreich, S. Micali, and R. Rivest, A fair protocol for signing contracts, in Proceedings of the 12th Colloquium on Automata, Languages and Programming, Springer-Verlag, Berlin, 1985, pp. 43\u201352.","DOI":"10.1007\/BFb0015729"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"M. Blum, How to exchange (secret) keys (extended abstract), in Proceedings of the 15th Annual ACM Symposium on Theory of Computing, ACM, Boston, MA, 1983, pp. 440\u2013447.","DOI":"10.1145\/800061.808775"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44598-6_15"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"R. Cleve, Limits on the security of coin flips when half the processors are faulty, in Proceedings of the 18th ACM Symposium on the Theory of Computing, 1986, pp. 364\u2013369.","DOI":"10.1145\/12130.12168"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-34805-0_50"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-016-9245-5"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"V. Daza and N. Makriyannis, Designing fully secure protocols for secure two-party computation of constant-domain functions, in Proceedings of the Fifteenth Theory of Cryptography Conference \u2013 TCC 2015, Lect. Notes Comput. Sci. 10677, Springer-Verlag, Berlin, 2017, pp. 581\u2013611.","DOI":"10.1007\/978-3-319-70500-2_20"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"J. A. Garay, P. D. MacKenzie, M. Prabhakaran, and K. Yang, Resource fairness and composability of cryptographic protocols, in Proceedings of the Third Theory of Cryptography Conference \u2013 TCC 2006, Lect. Notes Comput. Sci. 3876, S. Halevi and T. Rabin, eds. Springer-Verlag, Berlin, 2006, pp. 404\u2013428.","DOI":"10.1007\/11681878_21"},{"key":"ref17","volume-title":"Foundations of Cryptography, Voume II Basic Applications","author":"Goldreich O.","year":"2004"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game, in Proceedings of the 19th ACM Symposium on the Theory of Computing, 1987, pp. 218\u2013229.","DOI":"10.1145\/28395.28420"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"S. D. Gordon and J. Katz, Complete fairness in multi-party computation without an honest majority, in Proceedings of the Sixth Theory of Cryptography Conference \u2013 TCC 2009, Lect. Notes Comput. Sci. 5444, Springer-Verlag, Berlin, 2009, pp. 19\u201335.","DOI":"10.1007\/978-3-642-00457-5_2"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_8"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"S. D. Gordon, C. Hazay, J. Katz, and Y. Lindell, Complete fairness in secure two-party computation, in Proceedings of the 40th ACM Symposium on the Theory of Computing, 2008, pp. 413\u2013422.","DOI":"10.1145\/1374376.1374436"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049698"},{"key":"ref23","first-page":"223","volume":"8","author":"Kahn J. K. J.","year":"1995","journal-title":"J. Amer. Math. Soc."},{"key":"ref24","first-page":"7","volume":"2","author":"Koml\u00f2s J.","year":"1967","journal-title":"Studia Sci. Math. Hungar."},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"Y. Lindell and T. Rabin, Secure two-party computation with fairness - A necessary design principle, in Proceedings of the Fifteenth Theory of Cryptography Conference \u2013 TCC 2017, Lect. Notes Comput. Sci. 10677, Springer-Verlag, Berlin, 2017, pp. 565\u2013580.","DOI":"10.1007\/978-3-319-70500-2_19"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"M. Luby, S. Micali, and C. Rackoff, How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin, in Proceedings of the 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 11\u201321.","DOI":"10.1109\/SFCS.1983.25"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"N. Makriyannis, On the classification of finite Boolean functions up to fairness, in Security and Cryptography for Networks \u2013 9th International Conference, SCN 2014, Lect. Notes Comput. Sci. 8642, Springer-Verlag, Berlin, 2014, pp. 135\u2013154.","DOI":"10.1007\/978-3-319-10879-7_9"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"S. Micali, Simple and fast optimistic protocols for fair electronic exchange, in Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, PODC 2003, ACM, Boston, Massachusetts, 2003, pp. 12\u201319.","DOI":"10.1145\/872035.872038"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-39200-9_6"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2020.191.2.6"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007339"},{"key":"ref32","unstructured":"P. J. Wood, On the Probability that a Discrete Complex Random Matrix is Singular, Ph.D. thesis, Rutgers University, 2009."},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"A. C. Yao, How to generate and exchange secrets, in Proceedings of the 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 162\u2013167.","DOI":"10.1109\/SFCS.1986.25"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8438-9_1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1232656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:54Z","timestamp":1787336994000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1232656"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,23]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1137\/18M1232656"],"URL":"https:\/\/doi.org\/10.1137\/18m1232656","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,23]]}}}