## The Function-Inversion Problem: Barriers and Opportunities

#### Henry Corrigan-Gibbs and Dmitry Kogan

##### Materials

##### Abstract

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.