Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

연구 분야: Analysis

학회: STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit C:{0,1}n→{0,1}m, where m>n. Although at least half of the strings of length m are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS’21) and Ren, Wang, and Santhanam (FOCS’ 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e.g., Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist? In this work, we prove under the existence of subexponentially secure indistinguishability obfuscation (iO) that polynomial-time deterministic algorithms for Avoid imply NP=coNP. Combining this with Jain, Lin, and Sahai’s recent breakthrough construction of iO from well-founded assumptions (STOC’21, EUROCRYPT’22), we provide the first plausible evidence that Avoid has no efficient deterministic algorithm. Moreover, we also prove the hardness of Avoid based on polynomially-secure iO and a weaker variant of the Nondeterministic Exponential Time Hypothesis (NETH). Extending our techniques, we prove a surprising separation in bounded arithmetic, conditioned on similar assumptions. Assuming subexponentially secure iO and coNP is not infinitely often in, we show that Avoid has no deterministic polynomial-time algorithm even when we are allowed O(1) queries to an oracle that can invert the given input circuit on an arbitrarily chosen m-bit string. It follows that the dual Weak Pigeonhole Principle, the combinatorial principle underlying Avoid, is not provable in Cook’s theory PV1. This gives (under plausible assumptions) the first separation of Cook’s theory PV1 for polynomial-time reasoning and Jeřábek’s theory APV1 for probabilistic polynomial-time reasoning.