Pseudo-random generators under uniform assumptions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pseudo-random generators under uniform assumptions

Full text

Pdf (815 KB)

Source

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

Baltimore, Maryland, United States

Pages: 395 - 404

Year of Publication: 1990

ISBN:0-89791-361-2

Author

J. Håstad

Royal Institute of Technology, Stockholm, Sweden

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): 31, Citation Count: 14

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/100216.100270 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	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	2	[G] Goldreich, O. "A Note on Computational Indistiguishability", technical report 89-051, International Computer Science Institute.
	3	[GKL] Goldreich, O., Krawczyk, H. and Luby, M. "On the existence of pseudo-random generators", Proc. 29th Annual Conf. on Foundations of Computer Science, (1988), pp. 12-24.
	4	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	5	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	6	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	7	L A Levin, One-way functions and pseudorandom generators, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.363-365, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22185]
	8	[Y] Yao A. "Theory and application of trapdoor functions", Proc. 23rd Annual Conf. on Foundations of Computer Science, (1982), pp. 80-91.

CITED BY 14

	Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996
	Benny Chor , Niv Gilboa, Computationally private information retrieval (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.304-313, May 04-06, 1997, El Paso, Texas, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Tatsuaki Okamoto, On relationships between statistical zero-knowledge proofs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.649-658, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Markus Jakobsson , Elizabeth Shriver , Bruce K. Hillyer , Ari Juels, A practical secure physical random bit generator, Proceedings of the 5th ACM conference on Computer and communications security, p.103-111, November 02-05, 1998, San Francisco, California, United States
	Tatsuaki Okamoto , Kazuo Ohta, How to simultaneously exchange secrets by general assumptions, Proceedings of the 2nd ACM Conference on Computer and communications security, p.184-192, November 1994, Fairfax, Virginia, United States
	Ran Canetti , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Randomness vs. fault-tolerance, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.35-44, August 21-24, 1997, Santa Barbara, California, United States
	Russell Impagliazzo , Noam Nisan , Avi Wigderson, Pseudorandomness for network algorithms, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.356-364, May 23-25, 1994, Montreal, Quebec, Canada
	Charles Rackoff, Some definitions, protocols and proofs about secure authentication, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991
	Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Provably secure authenticated group Diffie-Hellman key exchange, ACM Transactions on Information and System Security (TISSEC), v.10 n.3, p.10-es, July 2007
	Lenore Cowen , Joan Feigenbaum , Sampath Kannan, A formal framework for evaluating heuristic programs, Annals of Mathematics and Artificial Intelligence, v.22 n.3-4, p.193-206, 1998
	D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States
	R. Ostrovsky, Efficient computation on oblivious RAMs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.514-523, May 13-17, 1990, Baltimore, Maryland, United States