Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-193 | 18th September 2024 09:27

The hardness of range avoidance for randomized algorithms implies Minicrypt

RSS-Feed




Revision #1
Authors: Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz
Accepted on: 18th September 2024 09:27
Downloads: 24
Keywords: 


Abstract:


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 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 (for randomized algorithms) already implies the existence of all cryptographic primitives in Minicrypt.

In fact, we show something 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 auxiliary-input one-way functions exist if either of these problems is weakly hard in the worst case, and standard one-way functions exist if either of these problems is weakly hard on average.

We also show that (1) Avoid can be solved by an efficient zero-error randomized algorithm given access to a suitable oracle that approximates the Kolmogorov-Levin complexity of a bit string; and that (2) simple reductions from hard problems in FNP to Avoid are unlikely. These latter results can be viewed as variants of known results from Ren, Santhanam, and Wang (FOCS 2022), and Ilango, Li, and Williams (STOC 2023).



Changes to previous version:

Updated the focus of the paper; Updated title.


Paper:

TR23-193 | 3rd December 2023 02:27

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


Abstract:

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