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.
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.
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: cryptographic level of security, tolerating a constant level of imprecision in the devices, requiring only a unit size quantum memory per device component for the honest implementation, and allowing a large natural class of constructions for the protocol. In conjunct with a recent work by Chung, Shi and Wu, it also leads to robust unbounded expansion using just 2 multi-part devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof 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.
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: cryptographic level of security, tolerating a constant level of imprecision in devices, requiring only unit size quantum memory (for each device component) in an honest implementation, and allowing a large natural class of constructions for the protocol. In conjunction with a recent work by Chung et al. [2014], it also leads to robust unbounded expansion using just 2 multipart devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the Rényi 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.
Device-independent security is the gold standard for quantum cryptography: not only is security based entirely on the laws of quantum mechanics, but it holds irrespective of any a priori assumptions on the quantum devices used in a protocol, making it particularly applicable in a quantum-wary environment. While the existence of device-independent protocols for tasks such as randomness expansion and quantum key distribution has recently been established, the underlying proofs of security remain very challenging, yield rather poor key rates, and demand very high quality quantum devices, thus making them all but impossible to implement in practice. We introduce a technique for the analysis of device-independent cryptographic protocols. We provide a flexible protocol and give a security proof that provides quantitative bounds that are asymptotically tight, even in the presence of general quantum adversaries. At a high level our approach amounts to establishing a reduction to the scenario in which the untrusted device operates in an identical and independent way in each round of the protocol. This is achieved by leveraging the sequential nature of the protocol and makes use of a newly developed tool, the “entropy accumulation theorem” of Dupuis, Fawzi, and Renner [ Entropy Accumulation, preprint, 2016]. As concrete applications we give simple and modular security proofs for device-independent quantum key distribution and randomness expansion protocols based on the CHSH inequality. For both tasks, we establish essentially optimal asymptotic key rates and noise tolerance. In view of recent experimental progress, which has culminated in loophole-free Bell tests, it is likely that these protocols can be practically implemented in the near future.
As our foundational understanding of quantum information theory broadens, it remains to be seen whether novel foundational developments will lead to corresponding applications. Promising branches are quantum networks and quantum cryptography, which are more intertwined by the day. In particular, a fascinating phenomena is that in networks with independent sources, Bell nonlocality can take place without the need for measurement settings for the parties, i.e. in each round, each source is asked to produce the same state and each party measures the same measurement. This is in stark contrast to standard Bell nonlocality, where seed randomness is necessary to certify nonlocality and through it, randomness of the outcomes. Building on nonlocality without seed randomness in networks, we propose a device-independent quantum key distribution protocol (which can be extended to quantum conference key agreement if it involves more than 2 parties) which allows for the generation of shared secret keys without the need for input randomness. We rely on recent results on nonlocality in networks and its robustness, showing how in a ring network with N bipartite sources, one must only make standard assumptions in order to run the protocol, while no trust is required from the devices themselves. We thus give a device-independent proof of security under this network assumption in the IID setting. In summary, we propose a first-of-a-kind protocol for Device-Independent Quantum Key Distribution which is native to the network setting, and which does not demand input randomness from the parties in order to produce output randomness.
A device-independent randomness expansion protocol aims to take an initial random seed and generate a longer one without relying on details of how the devices operate for security. A large amount of work to date has focussed on a particular protocol based on spot-checking devices using the CHSH inequality. Here we show how to derive randomness expansion rates for a wide range of protocols, with security against a quantum adversary. Our technique uses semidefinite programming and a recent improvement of the entropy accumulation theorem. To support the work and facilitate its use, we provide code that can generate lower bounds on the amount of randomness that can be output based on the measured quantities in the protocol. As an application, we give a protocol that robustly generates up to two bits of randomness per entangled qubit pair, which is twice that established in existing analyses of the spot-checking CHSH protocol in the low noise regime.
A device-independent randomness expansion protocol aims to take an initial random seed and generate a longer one without relying on details of how the devices operate for security.A large amount of work to date has focussed on a particular protocol based on spot-checking devices using the CHSH inequality.Here we show how to derive randomness expansion rates for a wide range of protocols, with security against a quantum adversary.Our technique uses semidefinite programming and a recent improvement of the entropy accumulation theorem.To support the work and facilitate its use, we provide code that can generate lower bounds on the amount of randomness that can be output based on the measured quantities in the protocol.As an application, we give a protocol that robustly generates up to two bits of randomness per entangled qubit pair, which is twice that established in existing analyses of the spot-checking CHSH protocol in the low noise regime.