Document Open Access Logo

On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs

Authors Benny Applebaum , Eyal Golombek

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.4.pdf
  • Filesize: 0.85 MB
  • 23 pages

Document Identifiers

Author Details

Benny Applebaum
  • Tel-Aviv University, Israel
Eyal Golombek
  • Tel-Aviv University, Israel

Funding

Supported by the European Union’s Horizon 2020 Programme (ERC-StG-2014-2020) under grant agreement no. 639813 ERC-CLC, and the Check Point Institute for Information Security.

Cite AsGet BibTex

Benny Applebaum and Eyal Golombek. On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.4

Abstract

We study the randomness complexity of interactive proofs and zero-knowledge proofs. In particular, we ask whether it is possible to reduce the randomness complexity, R, of the verifier to be comparable with the number of bits, C_V, that the verifier sends during the interaction. We show that such randomness sparsification is possible in several settings. Specifically, unconditional sparsification can be obtained in the non-uniform setting (where the verifier is modelled as a circuit), and in the uniform setting where the parties have access to a (reusable) common-random-string (CRS). We further show that constant-round uniform protocols can be sparsified without a CRS under a plausible worst-case complexity-theoretic assumption that was used previously in the context of derandomization. All the above sparsification results preserve statistical-zero knowledge provided that this property holds against a cheating verifier. We further show that randomness sparsification can be applied to honest-verifier statistical zero-knowledge (HVSZK) proofs at the expense of increasing the communication from the prover by R-F bits, or, in the case of honest-verifier perfect zero-knowledge (HVPZK) by slowing down the simulation by a factor of 2^{R-F}. Here F is a new measure of accessible bit complexity of an HVZK proof system that ranges from 0 to R, where a maximal grade of R is achieved when zero-knowledge holds against a "semi-malicious" verifier that maliciously selects its random tape and then plays honestly. Consequently, we show that some classical HVSZK proof systems, like the one for the complete Statistical-Distance problem (Sahai and Vadhan, JACM 2003) admit randomness sparsification with no penalty. Along the way we introduce new notions of pseudorandomness against interactive proof systems, and study their relations to existing notions of pseudorandomness.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Interactive proofs
  • Zero-knowledge proofs
  • Pseudorandomness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, and Guang Yang. Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. computational complexity, 25(2):349-418, 2016. Google Scholar
  2. Benny Applebaum and Prashant Nalini Vasudevan. Placing conditional disclosure of secrets in the communication complexity universe. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019,, pages 4:1-4:14, 2019. Google Scholar
  3. Sergei Artemenko and Ronen Shaltiel. Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. ACM Transactions on Computation Theory (TOCT), 9(2):1-26, 2017. Google Scholar
  4. László Babai and Shlomo Moran. Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci., 36(2):254-276, 1988. URL: https://doi.org/10.1016/0022-0000(88)90028-1.
  5. Boaz Barak, Shien Jin Ong, and Salil Vadhan. Derandomization in cryptography. In Annual International Cryptology Conference, pages 299-315. Springer, 2003. Google Scholar
  6. Mihir Bellare, Oded Goldreich, and Shafi Goldwasser. Randomness in interactive proofs. Computational Complexity, 3(4):319-354, 1993. Google Scholar
  7. Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 276-287. IEEE Computer Society, 1994. URL: https://doi.org/10.1109/SFCS.1994.365687.
  8. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo random bits. In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 112-117. IEEE Computer Society, 1982. URL: https://doi.org/10.1109/SFCS.1982.72.
  9. David G Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, pages 587-592, 1981. Google Scholar
  10. J Lawrence Carter and Mark N Wegman. Universal classes of hash functions. Journal of computer and system sciences, 18(2):143-154, 1979. Google Scholar
  11. Andrew Drucker. Nondeterministic direct product reductions and the success probability of sat solvers. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 736-745. IEEE, 2013. Google Scholar
  12. Bella Dubrov and Yuval Ishai. On the randomness complexity of efficient sampling. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 711-720, 2006. Google Scholar
  13. Shimon Even, Alan L. Selman, and Yacov Yacobi. The complexity of promise problems with applications to public-key cryptography. Inf. Control., 61(2):159-173, 1984. URL: https://doi.org/10.1016/S0019-9958(84)80056-X.
  14. Uriel Feige and Carsten Lund. On the hardness of computing the permanent of random matrices. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 643-654, 1992. Google Scholar
  15. Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 416-426. ACM, 1990. URL: https://doi.org/10.1145/100216.100272.
  16. Oded Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness, volume 17 of Algorithms and Combinatorics. Springer, 1998. URL: http://link.springer.com/book/10.1007/978-3-662-12521-2/page/1.
  17. Oded Goldreich. On promise problems: A survey. In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman, editors, Theoretical Computer Science, Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254-290. Springer, 2006. URL: https://doi.org/10.1007/11685654_12.
  18. Oded Goldreich and Johan Håstad. On the complexity of interactive proofs with bounded communication. Inf. Process. Lett., 67(4):205-214, 1998. Google Scholar
  19. Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. Journal of the ACM (JACM), 38(3):690-728, 1991. Google Scholar
  20. Oded Goldreich, Amit Sahai, and Salil Vadhan. Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 399-408, 1998. Google Scholar
  21. Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Computational Complexity, 11(1-2):1-53, 2002. Google Scholar
  22. Oded Goldreich and Avi Wigderson. Derandomization that is rarely wrong from short advice that is typically good. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 209-223. Springer, 2002. Google Scholar
  23. Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270-299, 1984. URL: https://doi.org/10.1016/0022-0000(84)90070-9.
  24. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on computing, 18(1):186-208, 1989. Google Scholar
  25. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 59-68, 1986. Google Scholar
  26. Pavel Hubáček, Alon Rosen, and Margarita Vald. An efficiency-preserving transformation from honest-verifier statistical zero-knowledge to statistical zero-knowledge. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 66-87. Springer, 2018. Google Scholar
  27. Russell Impagliazzo and Avi Wigderson. P= bpp if e requires exponential circuits: Derandomizing the xor lemma. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 220-229, 1997. Google Scholar
  28. Adam R Klivans and Dieter Van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501-1526, 2002. Google Scholar
  29. Alex Lombardi, Willy Quach, Ron D. Rothblum, Daniel Wichs, and David J. Wu. New constructions of reusable designated-verifier nizks. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III, volume 11694 of Lecture Notes in Computer Science, pages 670-700. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_22.
  30. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, 1992. URL: https://doi.org/10.1145/146585.146605.
  31. Ilan Newman. Private vs. common random bits in communication complexity. Information processing letters, 39(2):67-71, 1991. Google Scholar
  32. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  33. Koji Nuida and Goichiro Hanaoka. On the security of pseudorandomized information-theoretically secure schemes. IEEE transactions on information theory, 59(1):635-652, 2012. Google Scholar
  34. Yair Oren. On the cunning power of cheating verifiers: Some observations about zero knowledge proofs. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 462-471. IEEE, 1987. Google Scholar
  35. Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM (JACM), 50(2):196-249, 2003. Google Scholar
  36. Ronen Shaltiel and Christopher Umans. Pseudorandomness for approximate counting and sampling. computational complexity, 15(4):298-341, 2006. Google Scholar
  37. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. URL: https://doi.org/10.1145/146585.146609.
  38. Joseph H Silverman. Fast multiplication in finite fields gf (2 n). In International Workshop on Cryptographic Hardware and Embedded Systems, pages 122-134. Springer, 1999. Google Scholar
  39. Luca Trevisan and Salil Vadhan. Extracting randomness from samplable distributions. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 32-42. IEEE, 2000. Google Scholar
  40. Salil Pravin Vadhan. A study of statistical zero-knowledge proofs. PhD thesis, Massachusetts Institute of Technology, 1999. Google Scholar
  41. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80-91. IEEE Computer Society, 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact