文章基本信息

标题：Lower Bounds on the Time/Memory Tradeoff of Function Inversion
本地全文：下载
作者：Dror Chawin ; Iftach Haitner ; Noam Mazor 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-29
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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] 7→ [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. 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 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 ≥ 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, CorriganGibbs and Kogan [TCC ’19] partially justified the difficulty of finding lower bounds on nonadaptive 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 nonadaptive 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×f, viewing f as a vector in [n] n), then s q ∈ Ω(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 ∈ Ω(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 0, then s ∈ Ω(n/d log n).