Rigorous time/space tradeoffs for inverting functions
关键词: Applied mathematics 、 Point (geometry) 、 Image (mathematics) 、 Function (mathematics) 、 Time space 、 Mathematical analysis 、 Mathematics
摘要: We provide rigorous time-space tradeoffs for inverting any function. Given a function f, we give time space tradeoff of TS2 = N3q(f), where q(f) is the probability that two random elements are mapped to same image under f. also more general tradeoff, TS3 N3, can invert at point.
acm.org
sci-hub.se 参考文章(14)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Noga Alon, László Babai, Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem Journal of Algorithms. ,vol. 7, pp. 567- 583 ,(1985) , 10.1016/0196-6774(86)90019-2
A. C.-C. Yao, Coherent functions and program checkers symposium on the theory of computing. pp. 84- 94 ,(1990) , 10.1145/100216.100226
S. Pohlig, M. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (Corresp.) IEEE Transactions on Information Theory. ,vol. 24, pp. 106- 110 ,(1978) , 10.1109/TIT.1978.1055817
Richard Schroeppel, Adi Shamir, A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems SIAM Journal on Computing. ,vol. 10, pp. 456- 464 ,(1981) , 10.1137/0210033
M. Hellman, A cryptanalytic time-memory trade-off IEEE Transactions on Information Theory. ,vol. 26, pp. 401- 406 ,(1980) , 10.1109/TIT.1980.1056220
Benny Chor, Oded Goldreich, On the power of two-point based sampling Journal of Complexity. ,vol. 5, pp. 96- 106 ,(1989) , 10.1016/0885-064X(89)90015-0
J.Lawrence Carter, Mark N. Wegman, Universal classes of hash functions Journal of Computer and System Sciences. ,vol. 18, pp. 143- 154 ,(1979) , 10.1016/0022-0000(79)90044-8
H.R. Amirazizi, M.E. Hellman, Time-memory-processor trade-offs IEEE Transactions on Information Theory. ,vol. 34, pp. 505- 512 ,(1988) , 10.1109/18.6030
A. Fiat, S. Moses, A. Shamir, I. Shimshoni, G. Tardos, Planning and learning in permutation groups foundations of computer science. pp. 274- 279 ,(1989) , 10.1109/SFCS.1989.63490