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

Publisher Website
Google Scholar
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..

This publication has 12 references indexed in Scilit: