Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-193 | 3rd December 2023 02:27

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity



We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in the question of whether there exist efficient randomized algorithms that output a valid solution to $\Avoid$ with probability significantly greater than $1/2$. (Notice that achieving probability $1/2$ is trivial by random guessing.)

Our first main result shows that cryptographic one-way functions exist unless Avoid can be solved efficiently with probability $1-1/n^{C}$ (on efficiently sampleable input distributions). In other words, even a relatively weak notion of hardness of Avoid already implies the existence of all cryptographic primitives in Minicrypt.

In fact, we show something a bit stronger than this. In particular, we introduce two new natural problems, which we call CollisionAvoid and AffineAvoid. Like Avoid, these are total search problems in the polynomial hierarchy. They are provably at least as hard as Avoid, and seem to be notably harder. We show that one-way functions exist if either of these problems is weakly hard on average.

Our second main result shows that in certain settings Avoid can be solved with probability 1 in expected polynomial time, given access to either an oracle that approximates the Kolmogorov-Levin complexity of a bit string, or an oracle that approximates conditional time-bounded Kolmogorov complexity. This shows an interesting connection between Avoid and meta-complexity.

Finally, we discuss the possibility of proving hardness of Avoid. We show barriers preventing simple reductions from hard problems in FNP to Avoid.

ISSN 1433-8092 | Imprint