Extractors for adversarial sources via extremal hypergraphs

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples with no entropy at all or with unwanted dependence. Motivated by this and applications from cryptography, we initiate a systematic study of randomness extraction for the class of adversarial sources defined as follows.

A weak source X of the form X 1 , ..., X N , where each X i is on n bits, is an (N, K, n, k)-source of locality d if the following hold:

1. Somewhere good sources: at least K of the X i 's are independent, and each contains min-entropy at least k. We call these X i 's good sources, and their locations are unknown.