Search

We study the task of deterministically extracting randomness from sources containing computational entropy. The sources we consider have the form of a conditional distribution (f(X)|X), for some function f and some distribution X, and we say that such a source has computational min-entropy k if any circuit of size 2k can only predict f(x) correctly with probability at most 2-k given input x sampled from X. We first show that it is impossible to have a seedless extractor to extract from one single source of this kind. Then we show that it becomes possible if we are allowed a seed which is weakly random (instead of perfectly random) but contains some statistical min-entropy, or even a seed which is not random at all but contains some computational min-entropy. This can be seen as a step toward extending the study of multisource extractors from the traditional, statistical setting to a computational setting. We reduce the task of constructing such extractors to a problem in computational learning theory: learning linear functions under arbitrary distribution with adversarial noise, and we provide a learning algorithm for this problem. In fact, this problem is a well-recognized one in computational learning theory and variants of this problem have been studied intensively before. Thus, in addition to its application to extractors, our learning algorithm also has independent interest of its own, and it can be considered as the main technical contribution of this paper.

In this paper, we consider the task of deterministically extracting randomness from sources consisting of a sequence of n independent symbols from {0,1}d. The only randomness guarantee on such a source is that the whole source has min-entropy k . We give an explicit deterministic extractor which extract Ω(logk-loglog(1/ e)) bits with error e , for any n, d, k ∈ \BBN and e ∈ (0,1). For sources with a larger min-entropy, we can extract even more randomness. When k ≥ n1/2+γ, for any constant γ ∈ (0,1/2), we can extract m=k-O(d log(1/ e)) bits with any error e ≥ 2-Ω(nγ). When k ≥ logcn , for some constant c > 0, we can extract m=k-(1/ e)O(1) bits with any error e ≥ k-Ω(1). Our results generalize those of Kamp and Zuckerman and Gabizon which only work for bit-fixing sources (with d=1 and each bit of the source being either fixed or perfectly random). Moreover, we show the existence of a nonexplicit deterministic extractor which can extract m=k-O(log(1/ e)) bits whenever k=ω(d+log(n/ e)) . Finally, we show that even to extract from bit-fixing sources, any extractor, seeded or not, must suffer an entropy loss k-m=Ω(log(1/ e)). This generalizes a lower bound of Radhakrishnan and Ta-Shma on extracting from general sources.

We study the problem of deterministically extracting almost perfect random bits from multiple weakly random sources that are mutually independent. With two independent sources, we have an explicit extractor which can extract a number of random bits that matches the best construction currently known, via the generalized leftover hash lemma. We also extend our construction to extract randomness from more independent sources. One nice feature is that the extractor still works even with all but one source exposed. Finally, we apply our extractor for a cryptographic task in which a group of parties wants to agree on a secret key for group communication over an insecure channel, without using ideal local randomness.