One-way functions and pseudorandom generators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

One-way functions and pseudorandom generators

Full text

Pdf (315 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the seventeenth annual ACM symposium on Theory of computing table of contents

Providence, Rhode Island, United States

Pages: 363 - 365

Year of Publication: 1985

ISBN:0-89791-151-2

Author

L A Levin

Boston University, Massachusetts Institute of Technology

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 50, Citation Count: 14

Additional Information:

abstract 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/22145.22185 What is a DOI?

ABSTRACT

One-way are those functions which are easy to compute, but hard to invert on a non-negligible fraction of instances. The existence of such functions with some additional assumptions was shown to be sufficient for generating perfect pseudorandom strings |Blum, Micali 82|, |Yao 82|, |Goldreich, Goldwasser, Micali 84|. Below, among a few other observations, a weaker assumption about one-way functions is suggested, which is not only sufficient, but also necessary for the existence of pseudorandom generators. The main theorem can be understood without reading the sections 3-6.

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	L. Blum, M. Blum, M. Shub, A Siml)l~ Secure Pseudo-Random Number Generator, Advances in Cryptology ed. D. Chaum. R.I. Rivest and A.T. S}herman, Plem\num Pres, 1983. pp 61-78
	2	M. Blunl, S. Mieali, llow to generate ~;ryptographically Strong Sequences of Pseudo Random Bits, FOCS Symp. Proc. (1982); SIAM J. on Cornput, Jug. 13 ( 1984 ) pp.85()--8~~4.
	3	O. Goldreich, S. Goldwasser, S. Mirali, How toConstruct Random Functions, PRco. 25th Symp. on l~))undations' of Computer Science (1984).
	4	Shafrira Goldwasser, Probabilistic encryption: theory and applications (partial information, factoring, pseudo random bit generation), 1984
	5	L. kevin, Universal Sequential Search Problems, Probl. Inf. 7~ansm. 9/3, (1973)pp. 265-266.
	6	L, Levin, Average Case Complete Problems. 1984 ACM Syrup. on Theory of Computing, Proc.
	7	Leonid A. Levin, Randomness conservation inequalities; information and independence in mathematical theories, Information and Control, v.61 n.1, p.15-37, April 1984 [doi>10.1016/S0019-9958(84)80060-1]
	8	Adi Shamir, On the Generation of Cryptographically Strong Pseudo-Random Sequences, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.544-550, July 13-17, 1981
	9	A. D. Wyner, The wire-tap channel, Bell System 'l~:chnica!Journal 54, (1975), pp. 1355-1387.
	10	A. C. Yao, Theory and Applications of Trapdoor Functions, t>roc. 23rd IEEE Syrup. on l;bun. dations of Computer Science {1982) pp. 80-91.

CITED BY 14

	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States
	E. Allender, Some consequences of the existence of pseudorandom generators, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.151-159, January 1987, New York, New York, United States
	O. Goldreich, Towards a theory of software protection and simulation by oblivious RAMs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.182-194, January 1987, New York, New York, United States
	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States
	Ronald L. Rivest , Yiqun Lisa Yin, Being taught can be faster than asking questions, Proceedings of the eighth annual conference on Computational learning theory, p.144-151, July 05-08, 1995, Santa Cruz, California, United States
	Stuart Haber , W. Scott Stornetta, Secure names for bit-strings, Proceedings of the 4th ACM conference on Computer and communications security, p.28-35, April 01-04, 1997, Zurich, Switzerland
	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986
	M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States
	S. Ben-David , B. Chor , O. Goldreich, On the theory of average case complexity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.204-216, May 14-17, 1989, Seattle, Washington, United States
	Mihir Bellare , Silvio Micali, How to sign given any trapdoor function, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.32-42, May 02-04, 1988, Chicago, Illinois, United States
	Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994
	Huaxiong Wang , Josef Pieprzyk, Shared generation of pseudo-random functions, Journal of Complexity, v.20 n.2-3, p.458-472, April/June 2004
	J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States
	J. Håstad, Pseudo-random generators under uniform assumptions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.395-404, May 13-17, 1990, Baltimore, Maryland, United States