Cách Đạt Được Mô Phỏng Hoàn Hảo và Một Vấn Đề Hoàn Chỉnh cho Chứng Minh Không Tương Tác Hoàn Hảo

W. Aiello, J. Håstad, Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci. 42(3), 327–345 (1991) M. Bellare, P. Rogaway, Noninteractive perfect zero-knowledge. Unpublished manuscript, June 1990 M. Blum, A. De Santis, S. Micali, G. Persiano, Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084–1118 (1991) G. Brassard, C. Crépeau, M. Yung, Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds (extended abstract), in EUROCRYPT ’89: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (Springer, New York, 1990), pp. 192–195 I. Damgård, O. Goldreich Avi Wigderson, Hashing functions can simplify zero-knowledge protocol design (too). Technical report RS-94-39, BRICS, November 1994 S. Even, A.L. Selman, Y. Yacobi, The complexity of promise problems with applications to public-key cryptography. Inf. Control 61(2), 159–173 (1984) L. Fortnow, The complexity of perfect zero-knowledge, in Advances in Computing Research, vol. 5, ed. by S. Micali (JAC Press, 1989), pp. 327–343 O. Goldreich, Foundations of Cryptography, vol. 1 (Cambridge University Press, Cambridge, 2001) O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991) O. Goldreich, A. Sahai, S.P. Vadhan, Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge, in STOC ’98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (ACM, New York, 1998), pp. 399–408 O. Goldreich, A. Sahai, S.P. Vadhan, Can statistical zero knowledge be made non-interactive? Or on the relationship of SZK and NISZK, in CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology (Springer, London, 1999), pp. 467–484 O. Goldreich, S.P. Vadhan, Comparing entropies in statistical zero-knowledge with applications to the structure of SZK, in IEEE Conference on Computational Complexity (1999), pp. 54–73 S. Goldwasser, M. Sipser, Private-coins versus public-coins in interactive proof systems, in Advances in Computing Research, vol. 5, ed. by S. Micali (JAC Press, 1989), pp. 73–90 S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989) J. Groth, R. Ostrovsky, A. Sahai, Perfect non-interactive zero knowledge for NP, in Proceedings of Eurocrypt 2006. LNCS, vol. 4004 (Springer, Berlin, 2006), pp. 339–358 I. Haitner, O. Reingold, S.P. Vadhan, H. Wee, Inaccessible entropy, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, ed. by M. Mitzenmacher, Bethesda, MD, USA, May 31—June 2, 2009 (ACM, New York, 2009), pp. 611–620 L. Babai, S. Moran, Arthur-merlin games: a randomized proof system and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 254–276 (1988) L. Malka, Instance-dependent commitment schemes and the round complexity of perfect zero-knowledge proofs. Electron. Colloq. Comput. Complex. 15, 068 (2008) S. Micali, R. Pass, Local zero knowledge, in STOC ’06: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (ACM, New York, 2006), pp. 306–315 M. Naor, R. Ostrovsky, R. Venkatesan, M. Yung, Perfect zero-knowledge arguments for p using any one-way permutation. J. Cryptol. 11(2), 87–108 (1998) M.-H. Nguyen, S. Vadhan, Zero knowledge with efficient provers, in STOC ’06: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (ACM Press, New York, 2006), pp. 287–295 T. Okamoto, On relationships between statistical zero-knowledge proofs. J. Comput. Syst. Sci. 60(1), 47–108 (2000) S.J. Ong, S.P. Vadhan, An equivalence between zero knowledge and commitments, in TCC, ed. by R. Canetti. Lecture Notes in Computer Science, vol. 4948 (Springer, Berlin, 2008) C.H. Papadimitriou, Computational Complexity, vol. 10 (Addison Wesley, Reading, 1993) E. Petrank, G. Tardos, On the knowledge complexity of NP, in FOCS (1996), pp. 494–503 A. Sahai, S.P. Vadhan, A complete problem for statistical zero-knowledge. J. ACM 50(2), 196–249 (2003) A. De Santis, G. Di Crescenzo, G. Persiano, The knowledge complexity of quadratic residuosity languages. Theor. Comput. Sci. 132(1–2), 291–317 (1994) A. De Santis, G. Di Crescenzo, G. Persiano, Randomness-efficient non-interactive zero-knowledge (extended abstract), in Automata, Languages and Programming, (1997), pp. 716–726 A. De Santis, G. Di Crescenzo, G. Persiano, On NC1 boolean circuit composition of non-interactive perfect zero-knowledge, in MFCS (2004), pp. 356–367 A. De Santis, G. Di Crescenzo, G. Persiano, M. Yung, Image density is complete for non-interactive-SZK (extended abstract), in Automata, Languages and Programming, 25th International Colloquium, ICALP’98, ed. by K.G. Larsen, S. Skyum, G. Winskel, Aalborg, Denmark, July 13–17, 1998. Lecture Notes in Computer Science, vol. 1443 (Springer, Berlin, 1998), pp. 784–795 M. Tompa, H. Woll, Random self-reducibility and zero-knowledge interactive proofs of possession of information, in FOCS ’87: 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 12–14 October 1987 (IEEE Press, New York, 1987), pp. 472–482 S.P. Vadhan, A study of statistical zero-knowledge proofs. PhD thesis, MIT (1999) J. Watrous, Zero-knowledge against quantum attacks, in STOC ’06: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (ACM, New York, 2006), pp. 296–305