## The Function-Inversion Problem: Barriers and Opportunities

#### Henry Corrigan-Gibbs and Dmitry Kogan

##### Materials

##### Abstract

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).