Rafael Pass, Tel Aviv University & Cornell Tech
We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions. In more detail: - Assuming the existence of indistinguishability obfuscation, and subexponentially-secure one-way functions, an appropriate Gap version of MCSP is not NP-complete under randomized Levin-reductions. - Assuming the existence of subexponentially-secure indistinguishability obfuscation, subexponentially-secure one-way functions and injective PRGs, an appropriate Gap version of MKTP is not NP-complete under randomized Levin-reductions.
BibTeX
@misc{cryptoeprint:2024/420,
author = {Noam Mazor and Rafael Pass},
title = {Gap {MCSP} is not (Levin) {NP}-complete in Obfustopia},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/420},
year = {2024},
url = {https://eprint.iacr.org/2024/420}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。