Abstract:
Randomness is an essential resource for information theory, cryptography, and computation. The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. In this report, we first define classical randomness extractors, or when the source of randomness yields a classical string X. When considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system, and the question arises of how much classical randomness can we extract from a quantum system. To understand and analyze this question, we will first provide the relevant quantum preliminary background, and then define quantum-to-classical (QC) and quantumto-quantum (QQ) randomness extractors. Finally, we will explore cryptographic applications of QC randomness extractors, such as security in the noisy-storage model, and discuss possible future applications, such as privacy amplification.