**The Function-Inversion Problem: Barriers and Opportunities**

*Henry Corrigan-Gibbs and Dmitry Kogan*

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

**Category / Keywords: **foundations /

**Original Publication**** (with major differences): **IACR-TCC-2019

**Date: **received 13 Sep 2019

**Contact author: **dkogan at cs stanford edu, henrycg at cs stanford edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20190918:123331 (All versions of this report)

**Short URL: **ia.cr/2019/1046

[ Cryptology ePrint archive ]