Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography

Abstract

We give an efficient deterministic algorithm that 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 upon previous constructions, which required that at least $n/2$ of the bits be random in order to extract many bits. Our construction also has applications in exposure‐resilient cryptography, giving 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 that 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.