Rigorous Time/Space Trade-offs for Inverting Functions
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 29 (3) , 790-803
- https://doi.org/10.1137/s0097539795280512
Abstract
We provide rigorous time/space trade-offs for inverting any function. Given a function f, we give a time/space trade-off of T S2 = N3 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, T S3 = N3, that can invert any function at any point.Keywords
This publication has 11 references indexed in Scilit:
- Dynamic Perfect Hashing: Upper and Lower BoundsSIAM Journal on Computing, 1994
- On the power of two-point based samplingJournal of Complexity, 1989
- Time-memory-processor trade-offsIEEE Transactions on Information Theory, 1988
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- A cryptanalytic time-memory trade-offIEEE Transactions on Information Theory, 1980
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Hiding information and signatures in trapdoor knapsacksIEEE Transactions on Information Theory, 1978
- An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)IEEE Transactions on Information Theory, 1978