The Function-Inversion Problem: Barriers and Opportunities.

The task of function inversion is central to cryptanalysis: breaking block ciphers, forging signatures, and cracking password hashes are all special cases of the function-inversion problem. In 1980, Hellman showed that it is possible to invert a random function \(f{:}\,[N] \rightarrow [N]\) in time \(T = \widetilde{O}(N^{2/3})\) given only \(S = \widetilde{O}(N^{2/3})\) bits of precomputed advice about f. Hellman’s algorithm is the basis for the popular “Rainbow Tables” technique (Oechslin 2003), which achieves the same asymptotic cost and is widely used in practical cryptanalysis.