loading...
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography
Cambridge, Massachusettes October 11-October 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.123818444th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Jesse Kamp, University of Texas
David Zuckerman, University of Texas
We give an efficient deterministic algorithm which extracts \Omega (n^{2\gamma } ) almost-random bits from sources where n^{\frac{1}{2} + \gamma } of the n bits are uniformly random and the rest are fixed in advance. This improves on previous constructions which required that at least n/2 of the bits be random. Our construction also gives explicit adaptive exposure-resilient functions and in turn adaptive all-or-nothing transforms. For sources where instead of bits the values are chosen from [d], for d > 2, we give an algorithm which extracts a constant fraction of the randomness. We also give bounds on extracting randomness for sources where the fixed bits can depend on the random bits. .
Citation:
Jesse Kamp, David Zuckerman, "Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography," focs, pp.92, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.