Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices
- 31 May 2014
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
Randomness is a vital resource for modern day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high quality random numbers generated securely. Here we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: tolerating a constant level of implementation imprecision, requiring only a unit size quantum memory per device component for the honest implementation, and allowing a large natural class of constructions. In conjunct with a recent work by Chung, Shi and Wu (QIP 2014), it leads to robust unbounded expansion using just 2 multi-part devices. It can also be adapted for distributing cryptographic keys securely. The proof begins with a known protocol and proceeds by showing that the Renyi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements, and a method for simulating trusted measurements with untrusted devices. A full version of this paper containing additional results developed after the conference submission is available as arXiv:1402.0489.Keywords
Other Versions
Funding Information
- National Science Foundation (1318070, 1216729, 1017335)
- Ministry of Science and Technology of the People's Republic of China (2011CBA00300, 2011CBA00301)
This publication has 27 references indexed in Scilit:
- Free randomness can be amplifiedNature Physics, 2012
- Private randomness expansion with untrusted devicesJournal of Physics A: Mathematical and Theoretical, 2011
- Random numbers certified by Bell’s theoremNature, 2010
- Information causality as a physical principleNature, 2009
- Non-Abelian anyons and topological quantum computationReviews of Modern Physics, 2008
- Extractors and pseudorandom generatorsJournal of the ACM, 2001
- Unconditional security in quantum cryptographyJournal of the ACM, 2001
- Simple Proof of Security of the BB84 Quantum Key Distribution ProtocolPhysical Review Letters, 2000
- Unconditional Security of Quantum Key Distribution over Arbitrarily Long DistancesScience, 1999
- Quantum cryptography based on Bell’s theoremPhysical Review Letters, 1991