Paper 2024/420 Original: eprint.iacr.org/2024/420 ↗
Gap MCSP is not (Levin) NP-complete in Obfustopia
Abstract
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2026-05-03: last updated
- 2024-03-10: published
- Short URL
- https://ia.cr/2024/420
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}