Back to Search
Start Over
Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- Publication Year :
- 2025
- Publisher :
- Elsevier, 2025.
-
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.<br />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 MKTP is hard for the (apparently larger) class NISZK_L under not only NC^0 m-reductions but even under projections. Also 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.<br />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).
- Subjects :
- Theory of computation ��� Circuit complexity
General Computer Science
Minimum Circuit Size Problem
Kolmogorov Complexity
Computer Science
Theory of computation ��� Problems, reductions and completeness
Interactive Proofs
Theory of computation ��� Complexity classes
Worst-Case to Average-Case Reductions
Theoretical Computer Science
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....811370386e56ef5b730787d6b31caafb
- Full Text :
- https://doi.org/10.7282/00000279