Abstract:

Secrecy is randomness. A perfect secret is one for which all the alternatives are equally likely to the adversary. For secrecy to be possible, we have to assume that the world is not deterministic. Here we show how this necessary assumption, together with the validity of quantum mechanics and relativity, will allow us to generate the first and almost perfect secret, and then to expand it to be arbitrarily long. Unlike all existing solutions, the security of our construction is provable, unconditional (as opposed to computational), and verifiable.  Our method can also be used for the important task of distributing cryptographic keys.

Technically speaking, we formulate a precise model of extracting randomness from quantum devices whose inner-workings may be imperfect or even malicious. We then construct such a "physical extractor" that needs only a single and arbitrarily weak classical source, and the output randomness can be arbitrarily long and almost optimally close to uniform. This is impossible to achieve for classical randomness extractors, which cannot increase entropy and requires two or more *independent* sources. Our construction also differs from quantum-based random number generators in the market, as they all require that the users trust their quantum inner-workings. Such a trust threatens security when the devices are defective or were procured from an untrusted vendor. Several features of our construction, such as maximum noise tolerance and unit quantum memory requirement, have fundamentally lowered the implementation requirements.

Joint work with Kin-Min Chung and Xiaodi Wu (arXiv:1402.4797), and with Carl A. Miller (arXiv:1402.0489 and forthcoming).