Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR21-010 | 6th November 2022 14:49

Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

RSS-Feed




Revision #2
Authors: Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
Accepted on: 6th November 2022 14:49
Downloads: 149
Keywords: 


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 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.



Changes to previous version:

Some minor errors corrected, thanks to sharp-eyed referees.


Revision #1 to TR21-010 | 27th September 2021 17:15

Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity





Revision #1
Authors: Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
Accepted on: 27th September 2021 17:15
Downloads: 271
Keywords: 


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 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).



Changes to previous version:

Added a new circuit lower bound for MKTP, and some other minor changes.


Paper:

TR21-010 | 11th February 2021 02:24

Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity


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 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.



ISSN 1433-8092 | Imprint