Paper 2023/528
NPHardness of Approximating MetaComplexity: A Cryptographic Approach
Abstract
It is a longstanding open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related metacomplexity problems are NPcomplete. Even for the rare cases where the NPhardness of metacomplexity problems are known, we only know very weak hardness of approximation. In this work, we prove NPhardness of approximating metacomplexity with nearlyoptimal approximation gaps. Our key idea is to use *cryptographic constructions* in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present both conditional and unconditional hardness of approximation results as follows. $\bullet$ Assuming subexponentiallysecure witness encryption exists, we prove essentially optimal NPhardness of approximating conditional timebounded Kolmogorov complexity ($\mathrm{K}^t(x \mid y)$) in the regime where $t \gg y$. Previously, the best hardness of approximation known was a $x^{1/ \mathrm{poly}(\log \log x)}$ factor and only in the sublinear regime ($t \ll y$). $\bullet$ Unconditionally, we show nearoptimal NPhardness of approximation for the Minimum Oracle Circuit Size Problem (MOCSP), where Yes instances have circuit complexity at most $2^{\varepsilon n}$, and No instances are essentially as hard as random truth tables. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC'13). Previously, it was unknown whether it is NPhard to distinguish between oracle circuit complexity $s$ versus $10s\log N$. $\bullet$ Finally, we define a "multivalued" version of $\mathrm{MCSP}$, called $\mathrm{mvMCSP}$, and show that w.p. $1$ over a random oracle $O$, $\mathrm{mvMCSP}^O$ is NPhard to approximate under quasipolynomialtime reductions with $O$ oracle access. Intriguingly, this result follows almost directly from the security of Micali's CS proofs (Micali, SICOMP'00). In conclusion, we give three results convincingly demonstrating the power of cryptographic techniques in proving NPhardness of approximating metacomplexity.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. STOC 2023
 Keywords
 witness encryptionSNARGCS proofsminimum circuit size problemKolmogorov complexityhardness of approximation
 Contact author(s)

huangyizhi01 @ gmail com
rilango @ mit edu
h4n1in r3n @ gmail com  History
 20230412: approved
 20230412: received
 See all versions
 Short URL
 https://ia.cr/2023/528
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/528, author = {Yizhi Huang and Rahul Ilango and Hanlin Ren}, title = {{NP}Hardness of Approximating MetaComplexity: A Cryptographic Approach}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/528}, year = {2023}, url = {https://eprint.iacr.org/2023/528} }