Lower Bounds on the Time/Memory Tradeoff of Function Inversion

Dror Chawin, Iftach Haitner, Noam Mazor

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$ or…