Document Open Access Logo

Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity

Authors Eric Allender , John Gouwar, Shuichi Hirahara, Caleb Robelle

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.54.pdf
  • Filesize: 0.89 MB
  • 17 pages

Document Identifiers

Author Details

Eric Allender
  • Rutgers University, Piscataway, NJ, USA
John Gouwar
  • Northeastern University, Boston, USA
Shuichi Hirahara
  • National Institute of Informatics, Japan
Caleb Robelle
  • MIT, Boston, USA

Funding

JG and CR were supported in part by the DIMACS 2020 REU program under NSF grants CCF-1852215 and CCF-1836666.
  • Allender, Eric: Supported in part by NSF Grants CCF-1909216 and CCF-1909683.

Acknowledgements

We thank Rahul Santhanam, Oded Goldreich, Salil Vadhan, Harsha Tirumala, Dieter van Melkebeek and Andrew Morgan for helpful discussions. We also thank the anonymous reviewers who provided helpful comments.

Cite As Get BibTex

Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.54

Abstract

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT complexity of a string). Both MKTP and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP-Turing reductions; neither is known to be NP-complete.
Recently, some hardness results for MKTP were proved that are not (yet) known to hold for MCSP. In particular, MKTP is hard for DET (a subclass of P) under nonuniform ≤^{NC^0}_m reductions. In this paper, we improve this, to show that the complement of MKTP is hard for the (apparently larger) class NISZK_L under not only ≤^{NC^0}_m reductions but even under projections. Also, the complement of MKTP is hard for NISZK under ≤^{P/poly}_m reductions. Here, NISZK is the class of problems with non-interactive zero-knowledge proofs, and NISZK_L is the non-interactive version of the class SZK_L that was studied by Dvir et al.
As an application, we provide several improved worst-case to average-case reductions to problems in NP, and we obtain a new lower bound on MKTP (which is currently not known to hold for MCSP).

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Circuit complexity
Keywords
  • Kolmogorov Complexity
  • Interactive Proofs
  • Minimum Circuit Size Problem
  • Worst-case to Average-case Reductions

Metrics

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

Related Versions

References

  1. Manindra Agrawal, Eric Allender, and Steven Rudich. Reductions in circuit complexity: An isomorphism theorem and a gap theorem. Journal of Computer and System Sciences, 57(2):127-143, 1998. Google Scholar
  2. Eric Allender, V Arvind, Rahul Santhanam, and Fengming Wang. Uniform derandomization from pathetic lower bounds. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 370(1971):3512-3535, 2012. URL: https://doi.org/10.1098/rsta.2011.0318.
  3. Eric Allender, Azucena Garvia Bosshard, and Amulya Musipatla. A note on hardness under projections for graph isomorphism and time-bounded Kolmogorov complexity. Technical Report TR20-158, Electronic Colloquium on Computational Complexity (ECCC), 2020. Google Scholar
  4. 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.1007/978-3-662-03927-4.
  5. 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.
  6. Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic hardness under projections for time-bounded Kolmogorov complexity. Technical Report TR21-010, Electronic Colloquium on Computational Complexity (ECCC), 2021. Google Scholar
  7. 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.
  8. Eric Allender and Shuichi Hirahara. New insights on the (non-) hardness of circuit minimization and related problems. ACM Transactions on Computation Theory, 11(4):1-27, 2019. URL: https://doi.org/10.1145/3349616.
  9. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. Computational Complexity, 26(2):469-496, 2017. URL: https://doi.org/10.1007/s00037-016-0124-0.
  10. 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.
  11. Kazuyuki Amano. On the size of depth-two threshold circuits for the inner product mod 2 function. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications - 14th International Conference (LATA), volume 12038 of Lecture Notes in Computer Science, pages 235-247. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-40608-0_16.
  12. 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.
  13. Manuel Blum, Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Noninteractive zero-knowledge. SIAM Journal on Computing, 20(6):1084-1118, 1991. URL: https://doi.org/10.1137/0220068.
  14. 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.
  15. 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
  16. Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon. Relations between communication complexity, linear arrangements, and computational complexity. In Proc. 21st Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 2245 of Lecture Notes in Computer Science, pages 171-182. Springer, 2001. URL: https://doi.org/10.1007/3-540-45294-X_15.
  17. Bin Fu. Hardness of sparse sets and minimal circuit size problem. In Proc. Computing and Combinatorics - 26th International Conference (COCOON), volume 12273 of Lecture Notes in Computer Science, pages 484-495. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-58150-3_39.
  18. 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.
  19. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. A (de)constructive approach to program checking. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 143-152. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374399.
  20. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 247-258. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00032.
  21. Shuichi Hirahara. Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. In 35th Computational Complexity Conference (CCC), volume 169 of LIPIcs, pages 20:1-20:47. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.20.
  22. Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of MCSP and its variants. In 32nd Conference on Computational Complexity (CCC), volume 79 of LIPIcs, pages 7:1-7:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.7.
  23. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In 31st Conference on Computational Complexity (CCC), volume 50 of LIPIcs, pages 18:1-18:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.18.
  24. John M. Hitchcock and Aduri Pavan. On the NP-completeness of the minimum circuit size problem. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), volume 45 of LIPIcs, pages 236-245. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2015.236.
  25. 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.
  26. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Proceedings of the Thirty-Second Symposium on Theory of Computing (STOC), pages 73-79, 2000. URL: https://doi.org/10.1145/335305.335314.
  27. Valentine Kabanets, Daniel M. Kane, and Zhenjian Lu. A polynomial restriction lemma with applications. In Proceedings of the 49th Annual Symposium on Theory of Computing (STOC), pages 615-628. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055470.
  28. Leonid A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61(1):15-37, 1984. URL: https://doi.org/10.1016/S0019-9958(84)80060-1.
  29. Shachar Lovett and Jiapeng Zhang. On the impossibility of entropy reversal, and its application to zero-knowledge proofs. In Theory of Cryptography - 15th International Conference (TCC), volume 10677 of Lecture Notes in Computer Science, pages 31-55. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-70500-2_2.
  30. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In Proceedings of the 51st Annual Symposium on Theory of Computing (STOC), pages 1215-1225, 2019. URL: https://doi.org/10.1145/3313276.3316396.
  31. Cody Murray and Ryan Williams. On the (non) NP-hardness of computing circuit complexity. Theory of Computing, 13(4):1-22, 2017. URL: https://doi.org/10.4086/toc.2017.v013a004.
  32. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In 34th Computational Complexity Conference (CCC), volume 137 of LIPIcs, pages 27:1-27:29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.27.
  33. Michael Rudow. Discrete logarithm and minimum circuit size. Information Processing Letters, 128:1-4, 2017. URL: https://doi.org/10.1016/j.ipl.2017.07.005.
  34. Michael Saks and Rahul Santhanam. Circuit lower bounds from NP-hardness of MCSP under Turing reductions. In 35th Computational Complexity Conference (CCC), volume 169 of LIPIcs, pages 26:1-26:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.26.
  35. Heribert Vollmer. Introduction to circuit complexity: a uniform approach. Springer Science & Business Media, 1999. Google Scholar
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