ECCC-Report TR21-010https://eccc.weizmann.ac.il/report/2021/010Comments and Revisions published for TR21-010en-usSun, 06 Nov 2022 14:49:38 +0200
Revision 2
| Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity |
Eric Allender,
John Gouwar,
Shuichi Hirahara,
Caleb Robelle
https://eccc.weizmann.ac.il/report/2021/010#revision2A 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 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.
As an application, we provide several improved worst-case to average-case reductions to problems in NP.Sun, 06 Nov 2022 14:49:38 +0200https://eccc.weizmann.ac.il/report/2021/010#revision2
Revision 1
| Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity |
Eric Allender,
John Gouwar,
Shuichi Hirahara,
Caleb Robelle
https://eccc.weizmann.ac.il/report/2021/010#revision1A 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 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.
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).Mon, 27 Sep 2021 17:15:31 +0300https://eccc.weizmann.ac.il/report/2021/010#revision1
Paper TR21-010
| Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity |
Eric Allender,
John Gouwar,
Shuichi Hirahara,
Caleb Robelle
https://eccc.weizmann.ac.il/report/2021/010A 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 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.
As an application, we provide several improved worst-case to average-case reductions to problems in NP.Thu, 11 Feb 2021 02:24:56 +0200https://eccc.weizmann.ac.il/report/2021/010