Name
Abstract | ||
|---|---|---|
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.. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1137/S0097539705446846 | SIAM Journal on Computing |
Keywords | DocType | Volume |
deterministic extractors,n bit,exposure-resilient cryptography,explicit adaptive exposure-resilient function,random bit,randomness,previous construction,bit-fixing sources,bits from sources where n key words. extractors,turn adaptive all-or-nothing,exposure-resilient,random walks,adaptive all-or-nothing,constant fraction,almost-random bit,efficient deterministic algorithm,cryp- tography,resilient function,fixed bit,deterministic,cryptography,random processes,random walk | Journal | 36 |
Issue | ISSN | ISBN |
5 | 0272-5428 | 0-7695-2040-5 |
Citations | PageRank | References |
69 | 3.12 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jesse Kamp | 1 | 137 | 8.60 |
| David Zucherman | 2 | 2588 | 266.65 |