Rigorous time/space tradeoffs for inverting functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rigorous time/space tradeoffs for inverting functions

Full text

Pdf (621 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 534 - 541

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Amos Fiat	Tel-Aviv Univ., Tel-Aviv Univ., Israel
Moni Naor	IBM, Almaden Research Center

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 25, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103473 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	3	H. P#. Amirazizi and M. E. Hellman, Timememory-processor trade-off, IEEE Trans. infor. Theory 34, 1988, pp. 505-512.
	4	J. L. Carter #nd M. N. Wegman, Universal classes of hash functions, Journal of Computer and Systems Sciences, 18 (1979), pp. 143-154.
	5	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	6	B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. P#udich and P#. Smolensky, The bit extraction problem or t-resilient .functions, Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, (1985) pp. 396-407.
	7	A. Fiat, S. Moses, A. Shamir, I. Shimshoni, and G. Tardos, Planning and learning in permutation groups, Proc. of 30th Symposium on Foundations of Computer Science, 1989, pp. 274 - 279.
	8	M. E. ttellm#n, A cryptanalytic time memory trade-off, IEEE Trans. Infor. Theory 26, 1980, pp. 401-406.
	9	M. E. Hellman, and J. M. l#eyneri, Drainage and the DES, Summary, Advances in Cryptology, Proceedings of Crypto '82, pp. 129- 131, Plenum press.
	10	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	11	It. C. Merkle #nd M. E. Hellman, Hiding information and signatures in trapdoor functions, IEEE Trans. Infor. Theory 24, 1978, pp. 525-530.
	12	S. C. Pohlig #nd M. E. Hellm#n, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Tr#Lns. Infor. Theory 24, 1978, pp. 106-110.
	13	P#. Schroepel and A. Shamir, A T = O(T'/2), S = 0(2'#/4) algorithm for certain NP-complete problems. SIAM J. Computing, 10 (19Sl), pp. 456-464.
	14	A. Siegel, On universal classes of fast high performance hash functions, their time-space tradeoff and their applications Proc. of 30th Symposium on Foundations of Computer Science, 1989, pp. 20-25.
	15	A. C.-C. Yao, Coherent functions and program checkers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.84-94, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100226]

CITED BY 2

	Arvind Narayanan , Vitaly Shmatikov, Fast dictionary attacks on passwords using time-space tradeoff, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
	Gildas Avoine , Pascal Junod , Philippe Oechslin, Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables, ACM Transactions on Information and System Security (TISSEC), v.11 n.4, p.1-22, July 2008