loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
On the (Im)possibility of Cryptography with Imperfect Randomness
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, IEEE Annual 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, IEEE Annual 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, IEEE Annual 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, IEEE Annual 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
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
    Usage of this product signifies your acceptance of the Terms of Use.