Revisiting Time-Space Tradeoffs for Function Inversion

We study the black-box function inversion problem, which is the problem of finding x ∈ [N ] such that f (x) = y, given as input some challenge point y in the image of a function f : [N ] → [N ], using T oracle queries to f and preprocessed advice σ ∈ 0, 1 S depending on f . We prove a number of new results about this problem, as follows.