{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:55:56Z","timestamp":1787324156780,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR0011-20-2-0025"],"award-info":[{"award-number":["HR0011-20-2-0025"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001409","name":"Department of Science and Technology, Ministry of Science and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001409","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1709\/14"],"award-info":[{"award-number":["1709\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018393"],"award-info":[{"award-number":["2018393"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015782"],"award-info":[{"award-number":["2015782"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["1619348"],"award-info":[{"award-number":["1619348"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2012366"],"award-info":[{"award-number":["2012366"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [Kushilevitz, Ostrovsky, and Ros\u00e9n, J. Comput. Syst. Sci., 58 (1999), pp. 129--136] and [G\u00e1l and Ros\u00e9n, SIAM J. Comput., 31 (2002), pp. 1424--1437]. More concretely, we consider the randomness complexity of the basic Boolean function \\tt and, that serves as a building block in the design of many private protocols. We show that \\tt and cannot be privately computed using a single random bit, thus giving the first nontrivial lower bound on the 1-private randomness complexity of an explicit Boolean function, $f: \\{0,1\\}^n \\rightarrow \\{0,1\\}$. We further show that and, on any number of inputs $n$ (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of $n=3$ players), improving the upper bound of 73 random bits implicit in [Kushilevitz, Ostrovsky, and Ros\u00e9n, J. Comput. Syst. Sci., 58 (1999), pp. 129--136]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of \\tt and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for \\tt xor, which is 1-random, and for several degenerate functions).<\/jats:p>","DOI":"10.1137\/20m1314197","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T11:16:36Z","timestamp":1616498196000},"page":"465-484","source":"Crossref","is-referenced-by-count":4,"title":["Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND"],"prefix":"10.1137","volume":"35","author":[{"given":"Eyal","family":"Kushilevitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emmanuel","family":"Prouff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adrian","family":"Thillard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Damien","family":"Vergnaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-015-9214-4"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"D. Beaver,\n                      Precomputing oblivious transfer\n                      , in Advances in Cryptology - CRYPTO '95, 15th Annual International Cryptology Conference, Santa Barbara, California, USA, August 27-31, 1995, Proceedings, 1995, pp. 97-109,https:\/\/doi.org\/10.1007\/3-540-44750-4_8.","DOI":"10.1007\/3-540-44750-4_8"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, and A. Wigderson,\n                      Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract)\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, 1988, pp. 1-10,https:\/\/doi.org\/10.1145\/62212.62213,http:\/\/doi.acm.org\/10.1145\/62212.62213.","DOI":"10.1145\/62212.62213"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"C. Blundo, C. Galdi, and P. Persiano,\n                      Randomness recycling in constant-round private computations (extended abstract)\n                      , in Distributed Computing, 13th International Symposium, Bratislava, Slovak Republic, September 27-29, 1999, Proceedings, P. Jayanti, ed., vol. 1693 of Lecture Notes in Computer Science, Springer, New York, 1999, pp. 138-150,https:\/\/doi.org\/10.1007\/3-540-48169-9_10.","DOI":"10.1007\/3-540-48169-9_10"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050025"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"P. Bogetoft, D. L. Christensen, I. Damg\\aard, M. Geisler, T. P. Jakobsen, M. Kr\u00f8igaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. I. Schwartzbach, and T. Toft,\n                      Secure multiparty computation goes live\n                      , in Financial Cryptography and Data Security, 13th International Conference, FC 2009, Accra Beach, Barbados, February 23-26, 2009. Revised Selected Papers, R. Dingledine and P. Golle, eds., vol. 5628 of Lecture Notes in Computer Science, Springer, New York, 2009, pp. 325-343,https:\/\/doi.org\/10.1007\/978-3-642-03549-4_20.","DOI":"10.1007\/978-3-642-03549-4_20"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Cr\u00e9peau, and I. Damg\\aard,\n                      Multiparty unconditionally secure protocols (extended abstract)\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, 1988, pp. 11-19,https:\/\/doi.org\/10.1145\/62212.62214.","DOI":"10.1145\/62212.62214"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/0404004"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90120-X"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"I. Damg\\aard, J. B. Nielsen, R. Ostrovsky, and A. Ros\u00e9n,\n                      Unconditionally secure computation with reduced interaction\n                      , in Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, M. Fischlin and J. Coron, eds., vol. 9666 of Lecture Notes in Computer Science, Springer, New York, 2016, pp. 420-447,https:\/\/doi.org\/10.1007\/978-3-662-49896-5_15.","DOI":"10.1007\/978-3-662-49896-5_15"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"I. Damg\\aard, J. B. Nielsen, A. Polychroniadou, and M. A. Raskin,\n                      On the communication required for unconditionally secure multiplication\n                      , in Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, M. Robshaw and J. Katz, eds., vol. 9815 of Lecture Notes in Computer Science, Springer, New York, 2016, pp. 459-488,https:\/\/doi.org\/10.1007\/978-3-662-53008-5_16.","DOI":"10.1007\/978-3-662-53008-5_16"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2568207"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701385296"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703432785"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"O. Goldreich,\n                      Modern Cryptography, Probabilistic Proofs and Pseudorandomness\n                      , Algorithms and Combinatorics 17, Springer, New York, 1998.","DOI":"10.1007\/978-3-662-12521-2"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"A. Jakoby, M. Li\u015bkiewicz, and R. Reischuk,\n                      Private computations in networks: Topology versus randomness\n                      , in STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, H. Alt and M. Habib, eds., vol. 2607 of Lecture Notes in Computer Science, Springer, New York, 2003, pp. 121-132,https:\/\/doi.org\/10.1007\/3-540-36494-3_12.","DOI":"10.1007\/3-540-36494-3_12"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196306130"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1544"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010135274X"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019427634X"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1546"},{"key":"atypb22","unstructured":"A. Ros\u00e9n and F. Urrutia,\n                      A new approach to multi-party peer-to-peer communication complexity\n                      , in 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, A. Blum, ed., vol. 124 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, pp. 64:1-64:19,https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2019.64."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1314197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:33Z","timestamp":1787321973000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1314197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1314197"],"URL":"https:\/\/doi.org\/10.1137\/20m1314197","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}