Welcome to the resource topic for 2020/687
Title:
Lower Bounds on the Time/Memory Tradeoff of Function Inversion
Authors: Dror Chawin, Iftach Haitner, Noam Mazor
Abstract: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\colon [n] \mapsto [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^3 q = n^3 (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\times f, for some matrix A, viewing f as a vector in [n]^n), then s+q \in \Omega(n). The bound generalizes to the case where the advice string of f_1 + f_2, i.e., the coordinate-wise addition of the truth tables of f_1 and f_2, can be computed from the description of f_1 and f_2 by a low communication protocol. - 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 \in \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\in \Omega(n/d \log n).
ePrint: https://eprint.iacr.org/2020/687
Talk: https://www.youtube.com/watch?v=ukdDrsGKiEg
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .