From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9563
• 期：1
• 页码：65-82
• 全文大小：312 KB
• 参考文献：[AIK04]Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in \(\text{ NC }^{0}\) . In: Proceedings of 45th Symposium on Foundations of Computer Science (FOCS 2004), pp. 166–175. IEEE Computer Society, Rome, Italy, 17–19 October 2004
  [AIK15]Applebaum, B., Ishai, Y., Kushilevitz, E.: Minimizing locality of one-way functions via semi-private randomized encodings. Electron. Colloq. Comput. Complex. (ECCC) 22, 45 (2015)
  [BFS86]Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory (preliminary version). In: 27th Annual Symposium on Foundations of Computer Science, pp. 337–347. IEEE Computer Society, Toronto, Canada, 27–29 October 1986
  [BIKK14] Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317–342. Springer, Heidelberg (2014) CrossRef
  [BM88]Babai, L., Moran, S.: Arthur-merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254–276 (1988)MathSciNet CrossRef MATH
  [FKN94]Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Leighton, F.T., Goodrich, M.T. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 554–563. ACM, Montréal, Québec, Canada, 23–25 May 1994
  [GIKM00]Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci. 60(3), 592–629 (2000)MathSciNet CrossRef MATH
  [GKW15] Gay, R., Kerenidis, I., Wee, H.: Communication complexity of conditional disclosure of secrets and attribute-based encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 485–502. Springer, Heidelberg (2015) CrossRef
  [GPW15]Göös, M., Pitassi, T., Watson, T.: Zero-information protocols and unambiguity in arthur-merlin communication. In: Roughgarden, T. (ed.) Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, pp. 113–122. ACM, Rehovot, Israel, 11–13 January 2015
  [IK97]Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, pp. 174–183, June 1997
  [IK00]Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pp. 294–304. IEEE Computer Society, Redondo Beach, California, USA, 12–14 November 2000
  [Ish13]Ishai, Y.: Randomization techniques for secure computation. In: Prabhakaran, M., Sahai, A., (eds.) Secure Multi-Party Computation, vol. 10 of Cryptology and Information Security Series, pp. 222–248. IOS Press (2013)
  [Kla03]Klauck, H.: Rectangle size bounds and threshold covers in communication complexity. In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), pp. 118–134. IEEE Computer Society, Aarhus, Denmark, 7–10 July 2003
  [Kla10]Klauck, H.: A strong direct product theorem for disjointness. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 77–86. ACM, Cambridge, Massachusetts, USA, 5–8 June 2010
  
• 作者单位：Benny Applebaum (15)
  Pavel Raykov (15)
  
  15. School of Electrical Engineering, Tel-Aviv University, Tel Aviv, Israel
  
• 丛书名：Theory of Cryptography
• ISBN：978-3-662-49099-0
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Göös, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols (\(\mathsf {ZAM}\)). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs x and y respectively, and Merlin, the prover, attempts to convince them that some public function f evaluates to 1 on (x, y). In addition to standard completeness and soundness, Göös et al., require a “zero-knowledge” property which asserts that on each yes-input, the distribution of Merlin’s proof leaks no information about the inputs (x, y) to an external observer.