Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

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 ( i O ) that polynomial-time deterministic algorithms for Avoid imply NP = coNP . Combining this with Jain, Lin, and Sahai’s recent breakthrough construction of i O 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 i O 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 i O 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 PV 1 . This gives (under plausible assumptions) the first separation of Cook’s theory PV 1 for polynomial-time reasoning and Jeřábek’s theory APV 1 for probabilistic polynomial-time reasoning.

Authors

• Rahul Ilango
• Jiatu Li
• R. Ryan Williams

Keywords

• bounded arithmetic
• circuit range avoidance
• dual weak pigeonhole principle
• indistinguishability obfuscation