Explicit two-source extractors and more
MetadataShow full item record
In this thesis we study the problem of extracting almost truly random bits from imperfect sources of randomness. This is motivated by the wide use of randomness in computer science, and the fact that most accessible sources of randomness generate correlated bits, and at best contain some amount of entropy. We follow Chor and Goldreich [CG88] and Zuckerman [Z90], and model weak sources using min-entropy, where an (n,k)-source X is a distribution on n bits and takes any string x with probability at most 2^-k. It is known that it is impossible to extract random bits from a single (n,k)-source, and Chor and Goldreich [CG88] raised the question of extracting randomness from two such independent (n,k)-sources. Existentially, such 2-source randomness extractors exist for min-entropy k >=log n + O(1), but the best known construction prior to work in this thesis requires min-entropy k >=0.499 n [B2]. One of the main contributions of this thesis is an explicit 2-source extractor for min-entropy log^C n, for some constant C. Other results in this thesis include improved ways of extracting random bits from various other sources of randomness, as well as stronger notions of randomness extraction. Our results have applications in privacy amplification [BBR88,Mau92,BBCM95], which is a classical problem in information cryptography, and give protocols that achieve almost optimal parameters. Other applications include explicit constructions of non-malleable codes, which is a relaxation of the notion of error-detection codes and have applications in tamper-resilient cryptography [DPW10].