Paper 2024/420

Gap MCSP is not (Levin) NP-complete in Obfustopia

Noam Mazor, Tel Aviv University
Rafael Pass, Tel Aviv University & Cornell Tech
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-03-11: approved
2024-03-10: received
See all versions
Short URL
https://ia.cr/2024/420
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2024/420}},
      url = {https://eprint.iacr.org/2024/420}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.