Revisiting Time-Space Tradeoffs for Function Inversion

Alexander Golovnev; Siyao Guo; Spencer Peters; Noah Stephens-Davidowitz

doi:10.1007/978-3-031-38545-2_15

CRYPTO2023顶会

Revisiting Time-Space Tradeoffs for Function Inversion

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

DOI 出版方

2023年份

5被引次数

2顶会引用

摘要

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.