article

A complete problem for statistical zero knowledge

Authors:

Salil VadhanAuthors Info & Claims

Journal of the ACM (JACM), Volume 50, Issue 2

Pages 196 - 249

https://doi.org/10.1145/636865.636868

Published: 01 March 2003 Publication History

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]

Aiello, W., Bellare, M., and Venkatesan, R. 1995. Knowledge on the average---perfect, statistical and logarithmic. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29--June 1). ACM, New York, pp. 469--478.]]

Digital Library

[2]

Aiello, W., and Hastad, J. 1991. Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci. 42, 3 (June), 327--345.]]

Digital Library

[3]

Ajtai, M., and Ben-Or, M. 1984. A theorem on probabilistic constant depth computations. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C.). ACM, New York, pp. 471--474.]]

Digital Library

[4]

Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. 1998. Proof verification and the hardness of approximation problems. J. ACM 45, 3 (May), 501--555.]]

Digital Library

[5]

Arora, S., and Safra, S. 1998. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 1 (Jan.), 70--122.]]

Digital Library

[6]

Babai, L., and Moran, S. 1988. Arthur--Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 254--276.]]

Digital Library

[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/&sim;tcryptol).]]

[8]

Bellare, M., Micali, S., and Ostrovsky, R. 1990. The (true) complexity of statistical zero knowledge. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, Md. May 14--16) ACM, New York, pp. 494--502.]]

Digital Library

[9]

Bellare, M., and Petrank, E. 1992. Making zero-knowledge provers efficient. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (Victoria, B.C. Canada, May 4--6). ACM, New York, pp. 711--722.]]

Digital Library

[10]

Boppana, R. B., Hastad, J., and Zachos, S. 1987. Does co-NP have short interactive proofs? Inf. Proc. Lett. 25, 127--132.]]

Digital Library

[11]

Cook, S. A. 1971. The complexity of theorem-proving procedures. In Conference Record of the 3rd Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, 3--5). ACM, New York, pp. 151--158.]]

Digital Library

[12]

Cover, T. M., and Thomas, J. A. 1991. Elements of Information Theory, 2nd ed. Wiley Series in Telecommunications. Wiley, New York.]]

Digital Library

[13]

Damgå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/&sim;tcryptol.]]

[14]

Damgård, I., Goldreich, O., Okamoto, T., and Wigderson, A. 1995. Honest verifier vs. dishonest verifier in public coin zero-knowledge proofs. In Proceedings of Crypto '95. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York.]]

Digital Library

[15]

Damgård, I. B. 1993. Interactive hashing can simplify zero-knowledge protocol design without computational assumptions (extended abstract). In Advances in Cryptology---CRYPTO '93, Douglas R. Stinson, Ed. Lecture notes in Computer Science, vol. 773. Springer-Verlag, New York, pp. 100--109.]]

Digital Library

[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]

De Santis, A., Di Crescenzo, G., Persiano, G., and Yung, M. 1998. Image Density is complete for non-interactive-SZK. In Automata, Languages and Programming, 25th International Colloquium (Aalborg, Denmark, July 13--17). Lecture Notes in Computer Science, Springer-Verlag, New York, pp. 784--795. (See also preliminary draft of full version, May 1999.)]]

Digital Library

[18]

Di Crescenzo, G., Okamoto, T., and Yung, M. 1997. Keeping the SZK-verifier honest unconditionally. In Advances in Cryptology---CRYPTO '97, Burton S. Kaliski Jr., Ed. Lecture Notes in Computer Science, vol. 1294. Springer-Verlag, New York, 31--45.]]

Digital Library

[19]

Di Crescenzo, G., Sakurai, K., and Yung, M. 2000. On zero-knowledge proofs: "From membership to decision". In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (Portland, Ore., May). ACM, New York, pp. 255--264.]]

Digital Library

[20]

Even, S., Selman, A. L., and Yacobi, Y. 1984. The complexity of promise problems with applications to public-key cryptography. Inf. Cont. 61, 2 (May), 159--173.]]

Digital Library

[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]

Goldreich, O. 1990. A note on computational indistinguishability. Inf. Proc. Lett. 34, 6 (May), 277--281.]]

Digital Library

[23]

Goldreich, O. 2001. Foundations of Cryptography: Basic Tools. Cambridge University Press.]]

Digital Library

[24]

Goldreich, O., and Goldwasser, S. 2000. On the limits of nonapproximability of lattice problems. J. Comp. Syst. Sci. 60, 3, 540--563.]]

Digital Library

[25]

Goldreich, O., and Krawczyk, H. 1996. On the composition of zero-knowledge proof systems. SIAM J. Comput. 25, 1 (Feb.), 169--192.]]

Digital Library

[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.]]

Digital Library

[27]

Goldreich, O., Micali, S., and Wigderson, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 1, 691--729.]]

Digital Library

[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.]]

Digital Library

[30]

Goldreich, O., Ostrovsky, R., and Petrank, E. 1998. Computational complexity and knowledge complexity. SIAM J. Comput. 27, 4 (Aug.), 1116--1141.]]

Digital Library

[31]

Goldreich, O., and Petrank, E. 1999. Quantifying knowledge complexity. Comput. Complex. 8, 1, 50--98.]]

Digital Library

[32]

Goldreich, O., Sahai, A., and Vadhan, S. 1998. Honest verifier statistical zero-knowledge equals general statistical zero-knowledge. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (Dallas, Tex., May 23--26). ACM, New York, pp. 399--408.]]

Digital Library

[33]

Goldreich, O., Sahai, A., and Vadhan, S. 1999. Can statistical zero-knowledge be made non-interactive?, or On the relationship of SZK and NISZK. In Advances in Cryptology---CRYPTO '99 (Aug. 15--19. Lecture Notes in Computer Science, Springer-Verlag, New York.]]

Digital Library

[34]

Goldreich, O., and Vadhan, S. 1999. Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (Atlanta, Ga., May). IEEE Computer Society Press, Los Alamitos, Calif., pp. 54--73.]]

Digital Library

[35]

Goldreich, O., Vadhan, S., and Wigderson, A. 2001. On interactive proofs with a laconic prover. In Automata, Languages and Programming, 28th International Colloquium. (Crete, Greece, July 7--11). Lecture Notes in Computer Science, vol. 2076. Springer-Verlag, New York, pp. 334--345.]]

Digital Library

[36]

Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2 (Apr.), 270--299.]]

[37]

Goldwasser, S., Micali, S., and Rackoff, C. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1 (Feb.), 186--208.]]

Digital Library

[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]

Gutfreund, D., and Ben-Or, M. 2000. Increasing the power of the dealer in non-interactive zero-knowledge proof systems. In Advances in Cryptology---ASIACRYPT '00 (Kyoto, Japan). Springer-Verlag, Berlin, Germany. To appear.]]

Digital Library

[40]

Håstad, J., Impagliazzo, R., Levin, L. A., and Luby, M. 1999. A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 4, 1364--1396 (electronic).]]

Digital Library

[41]

Hofri, M. 1995. Analysis of Algorithms: Computational Methods & Mathematical Tools. Oxford University Press.]]

Digital Library

[42]

Kannan, S. 1989. Program Checkers for Algebraic Problems. Ph.D. dissertation. Univ. of California, Berkeley, Berkeley, Calif.]]

Digital Library

[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]

Lund, C., Fortnow, L., Karloff, H., and Nisan, N. 1992. Algebraic methods for interactive proof systems. J. ACM 39, 4 (Oct.), 859--868.]]

Digital Library

[47]

Okamoto, T. 2000. On relationships between statistical zero-knowledge proofs. J. Comput. Syst. Sci. 60, 1 (Feb.), 47--108.]]

Digital Library

[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]

Ostrovsky, R., Venkatesan, R., and Yung, M. 1993. Interactive hashing simplifies zero-knowledge protocol design. In Proceedings of Eurocrypt '93. Lecture Notes in Computer Science. Springer-Verlag, New York.]]

Digital Library

[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]

Petrank, E., and Tardos, G. 1996. On the knowledge complexity of NP. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (Burlington, Vt. Oct. 14--16). IEEE Computer Society Press, Los Alamitos, Calif., pp. 494--503.]]

Digital Library

[53]

Sahai, A. 2000. Frontiers in Zero Knowledge. Ph.D. dissertation. Massachusetts Institute of Technology, Cambridge, Mass.]]

Digital Library

[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]

Sahai, A., and Vadhan, S. P. 1997. A complete promise problem for statistical zero-knowledge. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (Miami Beach, Fla. Oct. 20--22). IEEE Computer Society Press, Los Alamitos, Calif., pp. 448--457.]]

Digital Library

[56]

Shamir, A. 1992. IP = PSPACE. J. ACM 39, 4 (Oct.), 869--877.]]

Digital Library

[57]

Vadhan, S. P. 1999. A Study of Statistical Zero-Knowledge Proofs. Ph.D. dissertation. Massachusetts Institute of Technology. Cambridge, Mass.]]

Digital Library

[58]

Vadhan, S. P. 2000. On transformations of interactive proofs that preserve the prover's complexity. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (Portland, Ore., May). ACM, New York, pp. 200--207.]]

Digital Library

[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.]]

Cited By

Savelov M(2024)Двусторонние оценки суммы вероятностей ошибок в задаче о различении конечного числа гипотез о неоднородной выборкеTwo-sided estimates for the sum of probabilities of errors in the multiple hypotheses testing problem with finite number of hypotheses about a nonhomogeneous sampleТеория вероятностей и ее примененияTeoriya Veroyatnostei i ee Primeneniya10.4213/tvp558669:2(405-416)Online publication date: 25-Apr-2024
https://doi.org/10.4213/tvp5586
Savelov M(2024)Two-sided Estimates for the Sum of Probabilities of Errors in the Multiple Hypothesis Testing Problem with Finite Number of Hypotheses on a Nonhomogeneous SampleTheory of Probability & Its Applications10.1137/S0040585X97T99194569:2(322-330)Online publication date: 14-Aug-2024
https://doi.org/10.1137/S0040585X97T991945
Gupte AVaikuntanathan V(2024)How to Construct Quantum FHE, GenericallyAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_8(246-279)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_8
Show More Cited By

Index Terms

A complete problem for statistical zero knowledge
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation
    1. Interactive computation

Recommendations

Computational Complexity and Knowledge Complexity

We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior to this work, for languages with greater-than-zero ...
Lower bounds for non-black-box zero knowledge
Special issue on FOCS 2003

We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:1.There does not exist a two-round zero-knowledge proof ...
One-Way Functions and Zero Knowledge
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge (CZK) proofs for all languages in NP. We prove its converse, thereby ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 50, Issue 2

March 2003

169 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/636865

Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2003

Published in JACM Volume 50, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

121
Total Citations
View Citations
1,517
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)7

Reflects downloads up to 23 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Savelov M(2024)Двусторонние оценки суммы вероятностей ошибок в задаче о различении конечного числа гипотез о неоднородной выборкеTwo-sided estimates for the sum of probabilities of errors in the multiple hypotheses testing problem with finite number of hypotheses about a nonhomogeneous sampleТеория вероятностей и ее примененияTeoriya Veroyatnostei i ee Primeneniya10.4213/tvp558669:2(405-416)Online publication date: 25-Apr-2024
https://doi.org/10.4213/tvp5586
Savelov M(2024)Two-sided Estimates for the Sum of Probabilities of Errors in the Multiple Hypothesis Testing Problem with Finite Number of Hypotheses on a Nonhomogeneous SampleTheory of Probability & Its Applications10.1137/S0040585X97T99194569:2(322-330)Online publication date: 14-Aug-2024
https://doi.org/10.1137/S0040585X97T991945
Gupte AVaikuntanathan V(2024)How to Construct Quantum FHE, GenericallyAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_8(246-279)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_8
Bhattacharyya AGayen SMeel KMyrisiotis DPavan AVinodchandran NElkind E(2023)On approximating total variation distanceProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/387(3479-3487)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/387
Herman TRothblum G(2023)Doubley-Efficient Interactive Proofs for Distribution Properties2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00049(743-751)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00049
Allender EGouwar JHirahara SRobelle C(2023)Cryptographic hardness under projections for time-bounded Kolmogorov complexityTheoretical Computer Science10.1016/j.tcs.2022.10.040940:PB(206-224)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.040
Volkovich I(2023)The final nail in the coffin of statistically-secure obfuscatorInformation Processing Letters10.1016/j.ipl.2023.106366182(106366)Online publication date: Aug-2023
https://doi.org/10.1016/j.ipl.2023.106366
Fischlin MRohrbach F(2023)Searching for ELFs in the Cryptographic ForestTheory of Cryptography10.1007/978-3-031-48621-0_8(207-236)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48621-0_8
Yin HChen EZhu YFeng RYau S(2022)An Efficient Zero-Knowledge Dual Membership Proof Supporting Pos-and-Neg Membership DecisionMathematics10.3390/math1017321710:17(3217)Online publication date: 5-Sep-2022
https://doi.org/10.3390/math10173217
Dixon PPavan AWoude JVinodchandran NLeonardi SGupta A(2022)Pseudodeterminism: promises and lowerboundsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520043(1552-1565)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520043
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents