Lower bounds on the time/memory tradeoff of function inversion

DOI10.1007/978-3-030-64381-2_11zbMATH Open1485.94070arXiv2105.00761OpenAlexW3115830630MaRDI QIDQ2119084FDOQ2119084

Authors: Dror Chawin, Iftach Haitner, Noam Mazor 

Publication date: 23 March 2022

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:[n]->[n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$, i.e., to find $xin{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$ (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 $sqgeqn$ 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.

Full work available at URL: https://arxiv.org/abs/2105.00761

Recommendations

• The function-inversion problem: barriers and opportunities
• Time hierarchies for cryptographic function inversion with advice
• Rigorous Time/Space Trade-offs for Inverting Functions
• Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs
• Time space tradeoffs for attacks against one-way functions and PRGs

zbMATH Keywords

random functionsfunction inverterstime/memory tradeoff

Mathematics Subject Classification ID

Cryptography (94A60)

Cited In (10)

• Revisiting time-space tradeoffs for function inversion
• Time hierarchies for cryptographic function inversion with advice
• On time-space lower bounds for finding short collisions in sponge hash functions
• Complexity of inverting the Euler function
• Time-space lower bounds for finding collisions in Merkle-Damgård hash functions
• Rigorous Time/Space Trade-offs for Inverting Functions
• Time-space lower bounds for finding collisions in Merkle-Damgård Hash functions
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• Time space tradeoffs for attacks against one-way functions and PRGs

This page was built for publication: Lower bounds on the time/memory tradeoff of function inversion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2119084)