Cryptology ePrint Archive: Report 2020/687

Lower Bounds on the Time/Memory Tradeoff of Function Inversion

Dror Chawin and Iftach Haitner and Noam Mazor

Abstract: We study time/memory tradeoffs of function inversion: an algorithm, i.e. an inverter, equipped with an $s$-bit advice for a randomly chosen function $f:[n]\to [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e. to find $x$ such that $f(x)=y$). Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman80 [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^2 q = n^2$ (ignoring low-order  terms), an $s$-advice, $q$-query variant of Hellman's algorithm inverts a constant fraction of the image points of any function. Yao [STOC '90] proved a lower bound of $sq \ge 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 inverter chooses its queries in advance. 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:

- Linear-advice (adaptive inverter). If the advice string is a linear function of f (e.g. $A\cdot f$, viewing $f$ as a vector in $[n]^n$), then $s+q = \Omega(n)$. - Affine non-adaptive decoders. If the non-adaptive inverter has an affine decoder - it  outputs a linear function, determined by the advice string and the element to invert, of the query answers - then $s = \Omega(n)$ (regardless of $q$). - Affine non-adaptive decision trees. If the non-adaptive inversion algorithm is a $d$-depth affine decision tree - it outputs the evaluation of a decision tree whose nodes compute a linear function of the answers to the queries - and $q < cn$ for some universal $c>0$, then $s = \Omega(n/d log n)$.

Category / Keywords: foundations / function inverters; random functions; time/memory tradeoff

Original Publication (in the same form): ECCC

Date: received 9 Jun 2020

Contact author: quefumas at gmail com,iftachh@gmail com,noammaz@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200609:234554 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]