The Taub Faculty of Computer Science Events and Talks

n the function-inversion problem, an algorithm gets black-box access to a function $f:[N] \to [N]$ and takes as input a point $y \in [N]$, along with $S$ bits of auxiliary information about $f$. 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 time-space tradeoff $S = T = \tilde{O}(N^{2/3})$ when $f$ is a random function, while the best known lower bound, due to Yao (1990) shows that $ST = \tilde{\Omega}(N)$, which admits the possibility of an $S = T = \tilde{O}(N^{1/2})$ algorithm. There remains a long-standing and vexing gap between these upper and lower bounds.

In this talk, I will present some new connections between function inversion and other areas of theoretical computer science. These connections suggest that making progress on either the lower-bound or upper-bound side of this problem might be challenging. Moreover, we will see how these connections—in concert with Hellman-style algorithms—improve the best upper bounds for well-studied

problems in communication complexity and data structures.

Joint work with Henry Corrigan-Gibbs.