Lower Bounds on the Time/Memory Tradeoff of Function Inversion
This work addresses a fundamental problem in cryptography and complexity theory, with implications for understanding computational limits, though it is incremental as it focuses on restricted cases rather than fully closing the gap.
The paper tackles the problem of function inversion, specifically studying time/memory tradeoffs for both adaptive and non-adaptive inverters, and proves new lower bounds on restricted families of inverters to address a long-standing open question in this area.
We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an s-bit advice on a randomly chosen function $f : [n] -> [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$, i.e., to find $x\in f^{-1}(y)$. Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman [IEEE transactions on Information Theory 80] presented an adaptive inverter that inverts with high probability a random $f$. Fiat and Naor [SICOMP 00] proved that for any $s$, $q$ with $s^3q = n$ (ignoring low-order terms), an $s$-advice, $q$-query variant of Hellmans algorithm inverts a constant fraction of the image points of any function. Yao [STOC 90] proved a lower bound of $sq \geq n$ for this problem. Closing the gap between the above lower and upper bounds is a long-standing open question. Very little is known for the non-adaptive variant of the question. The only known upper bounds, i.e., inverters, are the trivial ones (with $s+q = n$), and the only lower bound is the above bound of Yao. In a recent work, Corrigan-Gibbs and Kogan [TCC 19] partially justified the difficulty of finding lower bounds on non-adaptive inverters, showing that a lower bound on the time/memory tradeoff of non-adaptive inverters implies a lower bound on low-depth Boolean circuits. Bounds that, for a strong enough choice of parameters, are notoriously hard to prove. We make progress on the above intriguing question, both for the adaptive and the non-adaptive case, proving the following lower bounds on restricted families of inverters.