Paper 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.
- Contact author(s)
-
noammaz @ gmail com
rafaelp @ tau ac il - History
- 2024-06-25: revised
- 2024-03-10: received
- See all versions
- Short URL
- https://ia.cr/2024/420
- License
-
CC BY
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}
}
