Cryptographic hardness under projections for time-bounded Kolmogorov complexity
Cryptographic hardness under projections for time-bounded Kolmogorov complexity
复制标题
时限柯尔莫哥洛夫复杂度预测下的密码硬度
DOI：
10.1016/j.tcs.2022.10.040
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Robelle, Caleb
中科院分区：
文献类型：
--
作者：
Allender, Eric;Gouwar, John;Hirahara, Shuichi;Robelle, Caleb
KT是一种时间受限的Kolmogorov复杂性，由于它与电路复杂性和最小电路尺寸问题MCSP密切相关，在过去的几年里受到了广泛的关注。基本上，所有关于MCSP复杂性的结果也适用于MKTP(计算字符串的KT复杂性的问题)。在BPP-Turing约简下，MKTP和MCSP都很难得到SZK(统计零知识)；两者都不是NP完全的。最近，MKTP的一些硬度结果被证明是不适用于MCSP的。特别地，在非均匀≤m NC0约化下，MKTP对DET(P的一个子类)是困难的。本文对此进行了改进，证明了‾不仅在≤m NC0约化下，而且在投影下，对于(明显较大的)类NISZK L来说，MKTP也是困难的。此外，‾在≤m P/Poly还原下对NISZK来说也是困难的。这里，NISZK是具有非交互零知识证明的问题类，NISZK L是Dvir等人研究的SZK L类的非交互版本。作为应用，我们对NP中的问题提供了几种改进的最坏情况到平均情况的归约，并得到了MKTP的一个新的下界(目前还不知道这个下界对MCSP是成立的)。
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≤ m NC 0 reductions. In this paper, we improve this, to show that MKTP‾ is hard for the (apparently larger) class NISZK L under not only≤ m NC 0 reductions but even under projections. Also MKTP‾ is hard for NISZK under≤ m P/poly 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).