Document Open Access Logo

Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Authors Eric Allender , Shuichi Hirahara , Harsha Tirumala

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.3.pdf
  • Filesize: 0.82 MB
  • 19 pages

Document Identifiers

Author Details

Eric Allender
  • Rutgers University, Piscataway, NJ, USA
Shuichi Hirahara
  • National Institute of Informatics, Tokyo, Japan
Harsha Tirumala
  • Rutgers University, Piscataway, NJ, USA

Funding

  • Allender, Eric: Supported in part by NSF Grants CCF-1909216 and CCF-1909683.
  • Hirahara, Shuichi: Supported in part by JST, PRESTO Grant Number JPMJPR2024, Japan.
  • Tirumala, Harsha: Supported in part by NSF Grants CCF-1909216 and CCF-1909683.

Acknowledgements

We thank Sam Buss, Johannes Köbler, and Uwe Schöning for discussions concerning Boolean formula reducibility.

Cite As Get BibTex

Eric Allender, Shuichi Hirahara, and Harsha Tirumala. Kolmogorov Complexity Characterizes Statistical Zero Knowledge. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.3

Abstract

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge SZK, as well as the related classes NISZK_L and SZK_L.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Circuit complexity
Keywords
  • Kolmogorov Complexity
  • Interactive Proofs

Metrics

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

Related Versions

References

  1. Leonard M. Adleman and Kenneth L. Manders. Reducibility, randomness, and intractability (abstract). In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), pages 151-163. ACM, 1977. URL: https://doi.org/10.1145/800105.803405.
  2. Eric Allender. Curiouser and curiouser: The link between incompressibility and complexity. In Proc. Computability in Europe (CiE), volume 7318 of Lecture Notes in Computer Science, pages 11-16. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-30870-3_2.
  3. Eric Allender. The complexity of complexity. In Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of his 60th Birthday, volume 10010 of Lecture Notes in Computer Science, pages 79-94. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-50062-1_6.
  4. Eric Allender. Vaughan Jones, Kolmogorov complexity, and the new complexity landscape around circuit minimization. New Zealand journal of mathematics, 52, 2021. URL: https://doi.org/10.53733/148.
  5. Eric Allender, José L. Balcázar, and Neil Immerman. A first-order isomorphism theorem. SIAM J. Comput., 26(2):557-567, 1997. URL: https://doi.org/10.1137/S0097539794270236.
  6. Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy. Planar and grid graph reachability problems. Theory of Computing Systems, 45(4):675-723, 2009. URL: https://doi.org/10.1007/s00224-009-9172-z.
  7. Eric Allender, Harry Buhrman, Luke Friedman, and Bruno Loff. Reductions to the set of random strings: The resource-bounded case. Logical Methods in Computer Science, 10(3), 2014. URL: https://doi.org/10.2168/LMCS-10(3:5)2014.
  8. Eric Allender, Harry Buhrman, and Michal Koucký. What can be efficiently reduced to the Kolmogorov-random strings? Annals of Pure and Applied Logic, 138:2-19, 2006. Google Scholar
  9. Eric Allender, Harry Buhrman, Michal Kouckỳ, Dieter Van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM Journal on Computing, 35(6):1467-1493, 2006. URL: https://doi.org/10.1137/050628994.
  10. Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-way functions and a conditional variant of MKTP. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 213 of LIPIcs, pages 7:1-7:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2021.7.
  11. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. Information and Computation, 256:2-8, 2017. Special issue for MFCS '14. URL: https://doi.org/10.1016/j.ic.2017.04.004.
  12. Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret. Kolmogorov complexity, circuits, and the strength of formal theories of arithmetic. Chicago Journal of Theoretical Computer Science, 2013(5), April 2013. URL: https://doi.org/10.4086/cjtcs.2013.005.
  13. Eric Allender, Luke Friedman, and William Gasarch. Limits on the computational power of random strings. Information and Computation, 222:80-92, 2013. ICALP 2011 Special Issue. URL: https://doi.org/10.1016/j.ic.2011.09.008.
  14. Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic hardness under projections for time-bounded Kolmogorov complexity. Theoretical Computer Science, 2022. To appear. URL: https://doi.org/10.1016/j.tcs.2022.10.040.
  15. Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, and Pengxiang Wang. Robustness for space-bounded statistical zero knowledge. Technical Report TR22-138, Electronic Colloquium on Computational Complexity (ECCC), 2022. Google Scholar
  16. Eric Allender, Joshua A Grochow, Dieter Van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum circuit size, graph isomorphism, and related problems. SIAM Journal on Computing, 47(4):1339-1372, 2018. URL: https://doi.org/10.1137/17M1157970.
  17. Eric Allender, Shuichi Hirahara, and Harsha Tirumala. Kolmogorov complexity characterizes statistical zero knowledge. Technical Report TR22-127, Electronic Colloquium on Computational Complexity (ECCC), 2022. Google Scholar
  18. Eric Allender, Rahul Ilango, and Neekon Vafa. The non-hardness of approximating circuit size. Theory of Computing Systems, 65(3):559-578, 2021. URL: https://doi.org/10.1007/s00224-020-10004-x.
  19. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. SIAM Journal on Computing, 36(4):845-888, 2006. URL: https://doi.org/10.1137/S0097539705446950.
  20. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC¹. Journal of Computer and System Sciences, 41(3):274-306, 1990. URL: https://doi.org/10.1016/0022-0000(90)90022-D.
  21. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119-1159, 2006. URL: https://doi.org/10.1137/S0097539705446974.
  22. Harry Buhrman, Lance Fortnow, Michal Koucký, and Bruno Loff. Derandomizing from random strings. In 25th IEEE Conference on Computational Complexity (CCC), pages 58-63. IEEE, 2010. URL: https://doi.org/10.1109/CCC.2010.15.
  23. Harry Buhrman, Edith Spaan, and Leen Torenvliet. The relative power of logspace and polynomial time reductions. Computational Complexity, 3:231-244, 1993. URL: https://doi.org/10.1007/BF01271369.
  24. Samuel R. Buss and Louise Hay. On truth-table reducibility to SAT. Information and Computation, 91(1):86-102, 1991. URL: https://doi.org/10.1016/0890-5401(91)90075-D.
  25. Mingzhong Cai, Rodney Downey, Rachel Epstein, Steffen Lempp, and Joseph Miller. Random strings and tt-degrees of Turing complete c.e. sets. Logical Methods in Computer Science, 10(3):1-24, 2014. URL: https://doi.org/10.2168/LMCS-10(3:15)2014.
  26. Richard Chang, Jim Kadin, and Pankaj Rohatgi. On unique satisfiability and the threshold behavior of randomized reductions. Journal of Computer and System Sciences, 50(3):359-373, 1995. URL: https://doi.org/10.1006/jcss.1995.1028.
  27. R. Downey and D. Hirschfeldt. Algorithmic Randomness and Complexity. Springer, 2010. Google Scholar
  28. Zeev Dvir, Dan Gutfreund, Guy N Rothblum, and Salil P Vadhan. On approximating the entropy of polynomial mappings. In Second Symposium on Innovations in Computer Science, 2011. Google Scholar
  29. Oded Goldreich, Amit Sahai, and Salil Vadhan. Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK. In Annual International Cryptology Conference, pages 467-484. Springer, 1999. URL: https://doi.org/10.1007/3-540-48405-1_30.
  30. Joachim Grollmann and Alan L. Selman. Complexity measures for public-key cryptosystems. SIAM J. Comput., 17(2):309-335, 1988. URL: https://doi.org/10.1137/0217018.
  31. Shuichi Hirahara. Unexpected hardness results for Kolmogorov complexity under uniform reductions. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1038-1051. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384251.
  32. Shuichi Hirahara. Unexpected power of random strings. In 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPIcs, pages 41:1-41:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.41.
  33. Shuichi Hirahara. NP-hardness of learning programs and partial MCSP. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 968-979. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00095.
  34. Shuichi Hirahara and Akitoshi Kawamura. On characterizations of randomized computation using plain Kolmogorov complexity. Computability, 7(1):45-56, 2018. URL: https://doi.org/10.3233/COM-170075.
  35. Shuichi Hirahara and Osamu Watanabe. On nonadaptive reductions to the set of random strings and its dense subsets. In Ding-Zhu Du and Jie Wang, editors, Complexity and Approximation - In Memory of Ker-I Ko, volume 12000 of Lecture Notes in Computer Science, pages 67-79. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-41672-0_6.
  36. Rahul Ilango. Approaching MCSP from above and below: Hardness for a conditional variant and AC⁰[p]. In 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151 of LIPIcs, pages 34:1-34:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.34.
  37. Rahul Ilango. Constant depth formula and partial function versions of MCSP are hard. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 424-433. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00047.
  38. Rahul Ilango, Bruno Loff, and Igor Carboni Oliveira. NP-hardness of circuit minimization for multi-output functions. In 35th Computational Complexity Conference (CCC), volume 169 of LIPIcs, pages 22:1-22:36. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.22.
  39. Rahul Ilango, Hanlin Ren, and Rahul Santhanam. Robustness of average-case meta-complexity via pseudorandomness. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1575-1583. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520051.
  40. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0539-5.
  41. Johannes Köbler, Uwe Schöning, and Klaus W. Wagner. The difference and truth-table hierarchies for NP. RAIRO Theor. Informatics Appl., 21(4):419-435, 1987. URL: https://doi.org/10.1051/ita/1987210404191.
  42. Richard E. Ladner, Nancy A. Lynch, and Alan L. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103-123, 1975. URL: https://doi.org/10.1016/0304-3975(75)90016-X.
  43. Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition. Texts in Computer Science. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11298-1.
  44. Yanyi Liu and Rafael Pass. On one-way functions from NP-complete problems. In 37th Computational Complexity Conference (CCC), volume 234 of LIPIcs, pages 36:1-36:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.36.
  45. Kenneth W. Regan. A uniform reduction theorem - extending a result of J. Grollmann and A. Selman. In Proc. International Conference on Automata, Languages, and Programming (ICALP), volume 226 of Lecture Notes in Computer Science, pages 324-333. Springer, 1986. URL: https://doi.org/10.1007/3-540-16761-7_82.
  46. Hanlin Ren and Rahul Santhanam. Hardness of KT characterizes parallel cryptography. In 36th Computational Complexity Conference (CCC), volume 200 of LIPIcs, pages 35:1-35:58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.35.
  47. Amit Sahai and Salil P. Vadhan. A complete problem for statistical zero knowledge. J. ACM, 50(2):196-249, 2003. URL: https://doi.org/10.1145/636865.636868.
  48. Michael Saks and Rahul Santhanam. On randomized reductions to the random strings. In 37th Computational Complexity Conference (CCC), volume 234 of LIPIcs, pages 29:1-29:30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.29.
  49. Rahul Santhanam. Personal communication, 2022. Google Scholar
  50. Salil Vadhan. A Study of Statistical Zero-Knowledge Proofs. Springer, 2023. To appear. Google Scholar
  51. Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47(3):85-93, 1986. URL: https://doi.org/10.1016/0304-3975(86)90135-0.
  52. Heribert Vollmer. Introduction to circuit complexity: a uniform approach. Springer Science & Business Media, 1999. URL: https://doi.org/10.1007/978-3-662-03927-4.
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 About DROPS Imprint Privacy Contact