A complete problem for statistical zero knowledge

ABSTRACT

We present the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called Statistical Difference, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge.We propose the use of complete problems to unify and extend the study of statistical zero knowledge. To this end, we examine several consequences of our Completeness Theorem and its proof, such as:---A way to make every (honest-verifier) statistical zero-knowledge proof very communication efficient, with the prover sending only one bit to the verifier (to achieve soundness error 1/2).---Simpler proofs of many of the previously known results about statistical zero knowledge, such as the Fortnow and Aiello--Hεstad upper bounds on the complexity of SZK and Okamoto's result that SZK is closed under complement.---Strong closure properties of SZK that amount to constructing statistical zero-knowledge proofs for complex assertions built out of simpler assertions already shown to be in SZK.---New results about the various measures of "knowledge complexity," including a collapse in the hierarchy corresponding to knowledge complexity in the "hint" sense.---Algorithms for manipulating the statistical difference between efficiently samplable distributions, including transformations that "polarize" and "reverse" the statistical relationship between a pair of distributions.

REFERENCES

• 1: William Aiello , Mihir Bellare , Ramarathnam Venkatesan, Knowledge on the average—perfect, statistical and logarithmic, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.469-478, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225186]
• 2: William Aiello , Johan Hastad, Statistical zero-knowledge languages can be recognized in two rounds, Journal of Computer and System Sciences, v.42 n.3, p.327-345, June 1991 [doi>10.1016/0022-0000(91)90006-Q]
• 3: Miklos Ajtai , Michael Ben-Or, A theorem on probabilistic constant depth Computations, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.471-474, December 1984 [doi>10.1145/800057.808715]
• 4: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 5: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 6: László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
• 7: Bellare, M. 1997. A note on negligible functions. Tech. Rep. CS97-529, Dept. Computer Science and Engineering, Univ. California at San Diego, San Diego, Calif., March. Also available from the Theory of Cryptography Library (http://theory.lcs.mit.edu/∼tcryptol).
• 8: M. Bellare , S. Micali , R. Ostrovsky, The (true) complexity of statistical zero knowledge, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.494-502, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100285]
• 9: Mihir Bellare , Erez Petrank, Making zero-knowledge provers efficient, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.711-722, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129781]
• 10: R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
• 11: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 12: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 13: Damg&##949;rd, I., and Cramer, R. 1996. On monotone function closure of perfect and statistical zero-knowledge. Theory of Cryptography Library: Record 96-03. http://theory.lcs.mit.edu/∼tcryptol.
• 14: Ivan Damgård , Oded Goldreich , Tatsuaki Okamoto , Avi Wigderson, Honest Verifier vs Dishonest Verifier in Public Cain Zero-Knowledge Proofs, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.325-338, August 27-31, 1995
• 15: Ivan B. Damgård, Interactive hashing can simplify zero-knowledge protocol design without computational assumptions, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.100-109, January 1994, Santa Barbara, California, United States
• 16: De Santis, A., Di Crescenzo, G., Persiano, G., and Yung, M. 1994. On monotone formula closure of SZK. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (Santa Fe, N.M., Nov. 20--22). IEEE Computer Society Press, Los Alamitos, Calif., pp. 454--465.
• 17: Alfredo De Santis , Giovanni Di Crescenzo , Giuseppe Persiano , Moti Yung, Image Density is Complete for Non-Interactive-SZK (Extended Abstract), Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.784-795, July 13-17, 1998
• 18: Giovanni Di Crescenzo , Tatsuaki Okamoto , Moti Yung, Keeping the SZK-Verifier Honest Unconditionally, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.31-45, August 17-21, 1997
• 19: Giovanni Di Crescenzo , Kouichi Sakurai , Moti Yung, On zero-knowledge proofs (extended abstract): “from membership to decision”, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.255-264, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335336]
• 20: Shimon Even , Alan L. Selman , Yacov Yacobi, The complexity of promise problems with applications to public-key cryptography, Information and Control, v.61 n.2, p.159-173, May 1984 [doi>10.1016/S0019-9958(84)80056-X]
• 21: Fortnow, L. 1989. The complexity of perfect zero-knowledge. In Advances in Computing Research, vol. 5, Silvio Micali, Ed. JAC Press, Inc., pp. 327--343.
• 22: O. Goldreich, A note on computational indistinguishability, Information Processing Letters, v.34 n.6, p.277-281, May 1990 [doi>10.1016/0020-0190(90)90010-U]
• 23: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 24: Oded Goldreich , Shafi Goldwasser, On the limits of nonapproximability of lattice problems, Journal of Computer and System Sciences, v.60 n.3, p.540-563, June 2000 [doi>10.1006/jcss.1999.1686]
• 25: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 26: Goldreich, O., and Kushilevitz, E. 1993. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. J. Cryptology 6, 97--116.
• 27: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 28: Goldreich, O., Nisan, N., and Wigderson, A. 1995. On Yao's XOR lemma. Tech. Rep. TR95--050. Electronic Colloquium on Computational Complexity. Mar. http://www.eccc.uni-trier.de/eccc.
• 29: Goldreich, O., and Oren, Y. 1994. Definitions and properties of zero-knowledge proof systems. J. Cryptology 7, 1 (Winter), 1--32.
• 30: Oded Goldreich , Rafail Ostrovsky , Erez Petrank, Computational Complexity and Knowledge Complexity, SIAM Journal on Computing, v.27 n.4, p.1116-1141, Aug. 1998 [doi>10.1137/S0097539795280524]
• 31: Oded Goldreich , Erez Petrank, Quantifying knowledge complexity, Computational Complexity, v.8 n.1, p.50-98, June 1999 [doi>10.1007/s000370050019]
• 32: Oded Goldreich , Amit Sahai , Salil Vadhan, Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.399-408, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276852]
• 33: Oded Goldreich , Amit Sahai , Salil P. Vadhan, Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.467-484, August 15-19, 1999
• 34: Oded Goldreich , Salil Vadhan, Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.54, May 04-06, 1999
• 35: Oded Goldreich , Salil P. Vadhan , Avi Wigderson, On Interactive Proofs with a Laconic Prover, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.334-345, July 08-12, 2001
• 36: Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2 (Apr.), 270--299.
• 37: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 38: Goldwasser, S., and Sipser, M. 1989. Private coins versus public coins in interactive proof systems. In Advances in Computing Research, vol. 5. Silvio Micali, Ed. JAC Press, Inc., pp. 73--90.
• 39: Danny Gutfreund , Michael Ben-Or, Increasing the Power of the Dealer in Non-interactive Zero-Knowledge Proof Systems, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.429-442, December 03-07, 2000
• 40: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 41: Micha Hofri, Analysis of algorithms: computational methods and mathematical tools, Oxford University Press, Oxford, 1995
• 42: Sampath Kumar Kannan , Manuel Blum, Program checkers for algebraic problems*, 1990
• 43: Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, J. W. Thatcher and R. E. Miller, Eds. Plenum Press, New York, pp. 85--103.
• 44: Ladner, R. E., Lynch, N. A., and Selman, A. L. 1975. A comparison of polynomial time reducibilities. Theoret. Comput. Sci. 1, 2 (Dec.), 103--123.
• 45: Levin, L. A. 1973. Universal'nyĭe perebornyĭe zadachi (Universal search problems : in Russian). Problemy Peredachi Informatsii 9, 3, 265--266.
• 46: Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
• 47: Tatsuaki Okamoto, On relationships between statistical zero-knowledge proofs, Journal of Computer and System Sciences, v.60 n.1, p.47-108, Feb. 2000 [doi>10.1006/jcss.1999.1664]
• 48: Ostrovsky, R. 1991. One-way functions, hard on average problems, and statistical zero-knowledge proofs. In Proceedings of the 6th Annual Structure in Complexity Theory Conference (Chicago, Ill. June 30--July 3). IEEE Computer Society Press, Los Alamitos, Calif., pp. 133--138.
• 49: Rafail Ostrovsky , Ramarathnam Venkatesan , Moti Yung, Interactive hashing simplifies zero-knowledge protocol design, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.267-273, January 1994, Lofthus, Norway
• 50: Ostrovsky, R., and Wigderson, A. 1993. One-way functions are essential for non-trivial zero-knowledge. In Proceedings of the 2nd Israel Symposium on Theory of Computing and Systems.
• 51: Papadimitriou, C. H. 1994. Computational Complexity. Addison--Wesley, Reading, Mass.
• 52: E. Petrank , G. Tardos, On the knowledge complexity of N P, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.494, October 14-16, 1996
• 53: Amit Sahai , Shafi Goldwasser, Frontiers in zero knowledge, 2000
• 54: Sahai, A., and Vadhan, S. 1999. Manipulating statistical difference. In Randomization Methods in Algorithm Design (DIMACS Workshop, December 1997), Panos Pardalos, Sanguthevar Rajasekaran, and José Rolim, Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 43. American Mathematical Society, Providence, R.I., pp. 251--270.
• 55: Amit Sahai , Salil Vadhan, A Complete Promise Problem for Statistical Zero-Knowledge, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.448, October 19-22, 1997
• 56: Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
• 57: Salil Pravin Vadhan , Shafi Goldwasser, A study of statistical zero-knowledge proofs, 1999
• 58: Salil Vadhan, On transformation of interactive proofs that preserve the prover's complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.200-207, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335330]
• 59: Yao, A. C. 1982. Theory and applications of trapdoor functions (extended abstract). In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (Chicago, Ill., Nov. 3--5). IEEE Computer Society Press, Los Alamitos, Calif., pp. 80--91.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Security, Theory

Keywords:
Knowledge complexity, proof systems, statistical difference, zero knowledge