The task of function inversion is central to cryptanalysis: breaking block ciphers, forging signatures, and cracking password hashes are all special cases of the function-inversion problem. In 1980, Hellman showed that it is possible to invert a random function $f\colon [N] \to [N]$ in time $T = \widetilde{O}(N^{2/3})$ given only $S = \widetilde{O}(N^{2/3})$ bits of precomputed advice about $f$. Hellman’s algorithm is the basis for the popular “Rainbow Tables” technique (Oechslin, 2003), which achieves the same asymptotic cost and is widely used in practical cryptanalysis.

Is Hellman’s method the best possible algorithm for inverting functions with preprocessed advice? The best known lower bound, due to Yao (1990), shows that $ST = \widetilde{\Omega}(N)$, which still admits the possibility of an $S = T = \widetilde{O}(N^{1/2})$ attack. There remains a long-standing and vexing gap between Hellman’s $N^{2/3}$ upper bound and Yao’s $N^{1/2}$ lower bound. Understanding the feasibility of an $S = T = N^{1/2}$ algorithm is cryptanalytically relevant since such an algorithm could perform a key-recovery attack on AES-128 in time $2^{64}$ using a precomputed table of size $2^{64}$.

For the past 29 years, there has been no progress either in improving Hellman’s algorithm or in strengthening Yao’s lower bound. In this work, we connect function inversion to problems in other areas of theory to (1) explain why progress may be difficult and (2) explore possible ways forward.

Our results are as follows:

- We show that *any* improvement on Yao’s lower bound on function-inversion algorithms will imply new lower bounds on depth-two circuits with arbitrary gates. Further, we show that proving strong lower bounds on *non-adaptive* function-inversion algorithms would imply breakthrough circuit lower bounds on linear-size log-depth circuits.

- We take first steps towards the study of the *injective* function-inversion problem, which has manifold cryptographic applications. In particular, we show that improved algorithms for breaking PRGs with preprocessing would give improved algorithms for inverting injective functions with preprocessing.

- Finally, we show that function inversion is closely related to well-studied problems in communication complexity and data structures. Through these connections we immediately obtain the best known algorithms for problems in these domains.

We study preprocessing algorithms for the function-inversion problem. In this problem, an algorithm gets oracle access to a function $f\colon[N] \to [N]$ and takes as input $S$ bits of auxiliary information about $f$, along with a point $y \in [N]$. After running for time $T$, the algorithm must output an $x \in [N]$ such that $f(x) = y$, if one exists. This problem, first studied by Hellman (1980), has manifold applications to cryptanalysis.

Hellman’s algorithm for this problem achieves the upper bound $S = T = \widetilde{O}(N^{2/3})$ when $f$ is a random function, while the best known lower bound, due to Yao (1990) shows that $ST = \widetilde{\Omega}(N)$, which admits the possibility of an $S = T = \widetilde{O}(N^{1/2})$ algorithm. There remains a long-standing and vexing gap between these upper and lower bounds.

By uncovering connections between function inversion and other areas of theoretical computer science, we explain why making progress on either the lower-bound or upper-bound side of this problem will be difficult. Along the way, we use these connections—in concert with Hellman-style algorithms—to improve the best upper bounds for well-studied problems in communication complexity and data structures.

In particular, we obtain the following results:

- We show that any improvement on Yao’s lower bound for function inversion will imply new lower bounds on depth-two circuits with arbitrary gates.

- We show that proving strong lower bounds for function inversion would imply breakthrough lower bounds against linear-size log-depth circuits.

- We use a cryptanalytic algorithm to obtain an $O\big((N/k + \sqrt{N})\log N\big)$-bit protocol for the permutation variant of the $k$-party pointer jumping problem in the number-on-the-forehead model of communication complexity. For any $k=\omega\big(\frac{\log N}{\log\log N}\big)$, we improve the previous best bound of $O\big(N \cdot\frac{\log \log N}{\log N}\big)$, due to Pudlák, Rödl, and Sgall (1997).

- We give the first data structure for the systematic substring-search problem achieving index size and query time $\widetilde{O}(N^{\delta})$, for some $\delta < 1$. In fact, we achieve $\delta = 3/4$. In doing so, we answer an open question of Gál and Miltersen (2003).