{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T23:12:41Z","timestamp":1775085161983,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,7,18]],"date-time":"2016-07-18T00:00:00Z","timestamp":1468800000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00145-016-9239-3","type":"journal-article","created":{"date-parts":[[2016,7,18]],"date-time":"2016-07-18T15:55:14Z","timestamp":1468857314000},"page":"961-988","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["From Private Simultaneous Messages to Zero-Information Arthur\u2013Merlin Protocols and Back"],"prefix":"10.1007","volume":"30","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Raykov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,18]]},"reference":[{"key":"9239_CR1","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, E.\u00a0Kushilevitz, Cryptography in $$\\text{NC}{}^{0}$$ NC 0 . SIAM J. Comput. 36(4), 845\u2013888 (2006)","DOI":"10.1137\/S0097539705446950"},{"key":"9239_CR2","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, E.\u00a0Kushilevitz, How to garble arithmetic circuits. SIAM J. Comput. 43(2), 905\u2013929 (2014)","DOI":"10.1137\/120875193"},{"key":"9239_CR3","doi-asserted-by":"crossref","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, E.\u00a0Kushilevitz, Minimizing locality of one-way functions via semi-private randomized encodings. Electron. Colloq. Comput. Complex. (ECCC), 22, 45 (2015)","DOI":"10.1007\/s00145-016-9244-6"},{"key":"9239_CR4","unstructured":"B.\u00a0Applebaum, P.\u00a0Raykov, From private simultaneous messages to zero-information arthur-merlin protocols and back, in E.\u00a0Kushilevitz, T.\u00a0Malkin, editors, Theory of Cryptography\u201413th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10\u201313, 2016, Proceedings, Part II. LNCS, vol. 9563 (Springer, 2016), pp. 65\u201382. Available as eprint report 2015\/1046 at http:\/\/eprint.iacr.org\/2015\/1046 ."},{"key":"9239_CR5","doi-asserted-by":"crossref","unstructured":"L.\u00a0Babai, P.\u00a0Frankl, J.\u00a0Simon, Complexity classes in communication complexity theory (preliminary version), in 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27\u201329 October 1986 (IEEE Computer Society, 1986), pp. 337\u2013347","DOI":"10.1109\/SFCS.1986.15"},{"key":"9239_CR6","doi-asserted-by":"crossref","unstructured":"A.\u00a0Beimel, A.\u00a0G\u00e1l, On arithmetic branching programs. J. Comput. Syst. Sci. 59(2), 195\u2013220 (1999)","DOI":"10.1006\/jcss.1999.1648"},{"key":"9239_CR7","doi-asserted-by":"crossref","unstructured":"A.\u00a0Beimel, Y.\u00a0Ishai, R.\u00a0Kumaresan, E.\u00a0Kushilevitz, On the cryptographic complexity of the worst functions, in Y.\u00a0Lindell, editor, Theory of Cryptography\u201411th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24\u201326, 2014. Proceedings. LNCS, vol. 8349 (Springer, 2014), pp. 317\u2013342","DOI":"10.1007\/978-3-642-54242-8_14"},{"key":"9239_CR8","unstructured":"L.\u00a0Babai, S.\u00a0Moran, Arthur\u2013Merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254\u2013276 (1988)"},{"key":"9239_CR9","doi-asserted-by":"crossref","unstructured":"B.\u00a0Chor, E.\u00a0Kushilevitz, O.\u00a0Goldreich, M.\u00a0Sudan, Private information retrieval. J. ACM 45(6), 965\u2013981 (1998)","DOI":"10.1145\/293347.293350"},{"key":"9239_CR10","doi-asserted-by":"crossref","unstructured":"U.\u00a0Feige, J.\u00a0Kilian, M.\u00a0Naor, A minimal model for secure computation (extended abstract), in F.\u00a0T. Leighton, M.\u00a0T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23\u201325 May 1994, Montr\u00e9al, Qu\u00e9bec, Canada (ACM, 1994), pp 554\u2013563","DOI":"10.1145\/195058.195408"},{"key":"9239_CR11","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Gertner, Y.\u00a0Ishai, E.\u00a0Kushilevitz, T.\u00a0Malkin, Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci. 60(3), 592\u2013629 (2000)","DOI":"10.1006\/jcss.1999.1689"},{"key":"9239_CR12","doi-asserted-by":"crossref","unstructured":"R.\u00a0Gay, I.\u00a0Kerenidis, H.\u00a0Wee. Communication complexity of conditional disclosure of secrets and attribute-based encryption, in R.\u00a0Gennaro, M.\u00a0Robshaw, editors, Advances in Cryptology - CRYPTO 2015\u201435th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16\u201320, 2015, Proceedings, Part II. LNCS, vol. 9216 (Springer, 2015), pp. 485\u2013502","DOI":"10.1007\/978-3-662-48000-7_24"},{"key":"9239_CR13","doi-asserted-by":"crossref","unstructured":"M.\u00a0G\u00f6\u00f6s, T.\u00a0Pitassi, T.\u00a0Watson, Zero-information protocols and unambiguity in arthur-merlin communication, in T.\u00a0Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11\u201313, 2015 (ACM, 2015), pp. 113\u2013122","DOI":"10.1145\/2688073.2688074"},{"key":"9239_CR14","unstructured":"Y.\u00a0Ishai, E.\u00a0Kushilevitz, Private simultaneous messages protocols with applications, in Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, June (1997), pp. 174\u2013183"},{"key":"9239_CR15","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Ishai, E.\u00a0Kushilevitz, Randomizing polynomials: a new representation with applications to round-efficient secure computation, in 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12\u201314 November 2000, Redondo Beach, California, USA (IEEE Computer Society, 2000), pp. 294\u2013304","DOI":"10.1109\/SFCS.2000.892118"},{"key":"9239_CR16","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Ishai, E.\u00a0Kushilevitz, Perfect constant-round secure computation via perfect randomizing polynomials, in P.\u00a0Widmayer, F.\u00a0T. Ruiz, R.\u00a0M. Bueno, M.\u00a0Hennessy, S.\u00a0Eidenbenz, R.\u00a0Conejo, editors, Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8\u201313, 2002, Proceedings. LNCS, vol. 2380 (Springer, 2002), pp. 244\u2013256","DOI":"10.1007\/3-540-45465-9_22"},{"key":"9239_CR17","unstructured":"Y.\u00a0Ishai, Randomization techniques for secure computation, in M.\u00a0Prabhakaran, A.\u00a0Sahai, editors, Secure Multi-Party Computation, volume\u00a010 of Cryptology and Information Security Series (IOS Press, 2013), pp 222\u2013248."},{"key":"9239_CR18","unstructured":"Y.\u00a0Ishai, H.\u00a0Wee, Partial garbling schemes and their applications, in J.\u00a0Esparza, P.\u00a0Fraigniaud, T.\u00a0Husfeldt, E.\u00a0Koutsoupias, editors, Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8\u201311, 2014, Proceedings, Part I. LNCS, vol. 8572 (Springer, 2014), pp 650\u2013662"},{"key":"9239_CR19","doi-asserted-by":"crossref","unstructured":"H.\u00a0Klauck, Rectangle size bounds and threshold covers in communication complexity, in 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7\u201310 July 2003, Aarhus, Denmark (IEEE Computer Society, 2003), pp. 118\u2013134","DOI":"10.1109\/CCC.2003.1214415"},{"key":"9239_CR20","doi-asserted-by":"crossref","unstructured":"H.\u00a0Klauck, A strong direct product theorem for disjointness, in L.\u00a0J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010 (ACM, 2010), pp. 77\u201386","DOI":"10.1145\/1806689.1806702"},{"key":"9239_CR21","doi-asserted-by":"crossref","unstructured":"M.\u00a0Karchmer, A.\u00a0Wigderson, On span programs, in Proceedings of the Eighth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18\u201321, 1993 (IEEE Computer Society, 1993), pp. 102\u2013111","DOI":"10.1109\/SCT.1993.336536"},{"key":"9239_CR22","doi-asserted-by":"crossref","unstructured":"P.\u00a0Pudl\u00e1k, J.\u00a0Sgall, Algebraic models of computation and interpolation for algebraic proof systems, in Proof Complexity and Feasible Arithmetic. DIMACS Series in Discrete Mathematics and Theor. Comput. Sci., vol.\u00a039 (Am. Math. Soc., Providence, RI, 1998), pp. 279\u2013296","DOI":"10.1090\/dimacs\/039\/15"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-016-9239-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9239-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9239-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9239-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T02:01:44Z","timestamp":1749002504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-016-9239-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,18]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9239"],"URL":"https:\/\/doi.org\/10.1007\/s00145-016-9239-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,18]]},"assertion":[{"value":"15 December 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}