Rigorous time/space trade-offs for inverting functions
We provide rigorous time/space trade-offs for inverting any function. Given a function f, we give a time/space trade-off of TS2 = N(3)q(f), where q(f) is the probability that two random elements (taken with replacement) are mapped to the same image under f. We also give a more general trade-off, TS3 = N-3, that can invert any function at any point.
cryptography cryptanalysis one-way functions randomized algorithms random graphs hashing data encryption standard