Pseudo-random functions and factoring (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pseudo-random functions and factoring (extended abstract)

Full text

Pdf (1.11 MB)

Source

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

Portland, Oregon, United States

Pages: 11 - 20

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Moni Naor	Dept. of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
Omer Reingold	AT&T Labs - Research, 180 Park Avenue, Bldg. 103, Florham Park, NJ
Alon Rosen	Dept. of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 33, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/335305.335307 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	Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
	2	D. Angluin, D. Lichtenstein, Provable security of cryptosystems:A survey. Tech. Rep. 288, Dept. of Computer Science, yale Univ. new Haven, Conn., 1983.
	3	Eli Biham , Dan Boneh , Omer Reingold, Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring, Information Processing Letters, v.70 n.2, p.83-87, April 30, 1999 [doi>10.1016/S0020-0190(99)00047-2 ]
	4	Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
	5	L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
	6	Manuel Blum , Shafi Goldwasser, An efficient probabilistic public key encryption scheme which hides all partial information, Proceedings of CRYPTO 84 on Advances in cryptology, p.289-302, August 1985, Santa Barbara, California, United States
	7	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]
	8	G. Brassard, On computationally secure authentication tags requiring short secret shared keys, Advances of Cryptology: Proceedings of Crypto-82, D. Chaum, R.L. Rivest and A.T. Sherman, Eds. Plenum Press, New- York, 1983, pp. 79-86.
	9	R. Fischlin - Private communication.
	10	R. Fischlin and C. P. Schnorr, Stronger security proofs for RSA and Rabin bits, Advances in Cryptology- EU- ROCRYPT '97, Lecture Notes in Computer Science, vol. 1233, Springer-Verlag, 1997, pp. 267-279.
	11	O. Goldreich, Foundations of Cryptography Fragments of a Book, 1995. Electronic publication: http:///www, eccc. uni-trier, de/eccc//info//ECCC- Books//eccc-books.html (Electronic Colloquium on Computational Complexity).
	12	Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
	13	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 [doi>10.1145/6490.6503]
	14	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]
	15	Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
	16	Michael George Luby , Luby Michael, Pseudorandomness and Cryptographic Applications, Princeton University Press, Princeton, NJ, 1994
	17	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	18	Moni Naor , Omer Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions, Journal of Computer and System Sciences, v.58 n.2, p.336-375, April 1999 [doi>10.1006/jcss.1998.1618 ]
	19	M. Naor , O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.458, October 19-22, 1997
	20	Moni Naor , Omer Reingold, From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs (Extended Abstract), Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.267-282, August 23-27, 1998
	21	A. M. Odlyzko, The ~uture of integerfactorization, RSA CyptoBytes, 2(1), 1995, pp. 5-12.
	22	M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
	23	O. Reingold, Pseudo-Random Synthesizers, Functions and Permutations, PhD Thesis, Weizmann Institute of Science, 1998.
	24	U.V. Vazirani and V.V. Vazirani, Efficient and Secure Pseudo-Random Number Generation, Proc. ~5th IEEE Syrup. on Foundations of CornputerScience, 1984, pp. 458-463.
	25	A. C. Yao, Theory and applications of trapdoor functions, Proc. ~3rd IEEE Syrnp. on Foundations of Computer Science, 1982, pp. 80-91.