The Function-Inversion Problem: Barriers and Opportunities

Henry Corrigan-Gibbs and Dmitry Kogan

Electronic Colloquium on Computational Complexity (ECCC Preprint)
October 31, 2018

  • Abstract page: ECCC
  • Preprint: PDF

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