On the (Im)possibility of Cryptography with Imperfect Randomness

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Yevgeniy Dodis Articles by Shien Jin Ong Articles by Manoj Prabhakaran Articles by Amit Sahai

45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)

Rome, Italy

October 17-October 19

ISBN: 0-7695-2228-9

	ASCII Text	x
	Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Amit Sahai, "On the (Im)possibility of Cryptography with Imperfect Randomness," Foundations of Computer Science, Annual IEEE Symposium on, pp. 196-205, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.

	BibTex	x
	@article{ 10.1109/FOCS.2004.44, author = {Yevgeniy Dodis and Shien Jin Ong and Manoj Prabhakaran and Amit Sahai}, title = {On the (Im)possibility of Cryptography with Imperfect Randomness}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2004}, issn = {0272-5428}, pages = {196-205}, doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.44}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - On the (Im)possibility of Cryptography with Imperfect Randomness SN - 0272-5428 SP196 EP205 A1 - Yevgeniy Dodis, A1 - Shien Jin Ong, A1 - Manoj Prabhakaran, A1 - Amit Sahai, PY - 2004 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Yevgeniy Dodis, New York University

Shien Jin Ong, Harvard University

Manoj Prabhakaran, Princeton University and University of California at Los Angeles

Amit Sahai, Princeton University and University of California at Los Angeles

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.44

We investigate the feasibility of a variety of cryptographic tasks with imperfect randomness. The kind of imperfect randomness we consider are entropy sources, such as those considered by Santha and Vazirani, Chor and Goldreich, and Zuckerman. We show the following:

Certain cryptographic tasks like bit commitment, encryption, secret sharing, zero-knowledge, noninteractive zero-knowledge, and secure two-party computation for any non-trivial function are impossible to realize if parties have access to entropy sources with slightly less-than-perfect entropy, i.e., sources with imperfect randomness. These results are unconditional and do not rely on any unproven assumption.

On the other hand, based on stronger variants of standard assumptions, secure signature schemes are possible with imperfect entropy sources. As another positive result, we show (without any unproven assumption) that interactive proofs can be made sound with respect to imperfect entropy sources.

Citation:

Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Amit Sahai, "On the (Im)possibility of Cryptography with Imperfect Randomness," focs, pp.196-205, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.