arXiv:1402.0489

Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

Carl A. Miller, Yaoyun Shi

Published Feb 3, 2014• 2 citations

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: 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.

DOI: 10.48550/arxiv.1402.0489

Related papers

Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices

Carl A. Miller, Yaoyun Shi

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.

Journal of the ACMOct 26, 2016103 citations

Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

Carl A. Miller, Yaoyun Shi

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.

ACM Symposium on Theory of Computing (STOC)May 31, 201470 citations

Simple and Tight Device-Independent Security Proofs

Rotem Arnon-Friedman, Renato Renner, Thomas Vidick

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.

arXiv:1607.01797SIAM Journal on ComputingJan 1, 2019155 citations

A Framework for Quantum-Secure Device-Independent Randomness Expansion

Peter J. Brown, Sammy Ragy, Roger Colbeck

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.

arXiv:1810.13346IEEE Transactions on Information TheoryDec 17, 201947 citations

Robust device independent quantum key distribution

Umesh V. Vazirani, Thomas Vidick

Quantum cryptography is based on the discovery that the laws of quantum mechanics allow levels of security that are impossible to replicate in a classical world [2, 8, 12]. Can such levels of security be guaranteed even when the quantum devices on which the protocol relies are untrusted? This fundamental question in quantum cryptography dates back to the early nineties when the challenge of achieving device independent quantum key distribution, or DIQKD, was first formulated [9]. We answer this challenge affirmatively by exhibiting a robust protocol for DIQKD and rigorously proving its security. The protocol achieves a linear key rate while tolerating a constant noise rate in the devices. The security proof assumes only that the devices can be modeled by the laws of quantum mechanics and are spatially isolated from each other and any adversary's laboratory. In particular, we emphasize that the devices may have quantum memory. All previous proofs of security relied either on the use of many independent pairs of devices [6, 4, 7], or on the absence of noise [10, 1].

Conference on Innovations in Theoretical Computer ScienceJan 12, 201411 citations

A framework for quantum-secure device-independent randomness expansion

Peter J. Brown, Sammy Ragy, Roger Colbeck

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.

May 1, 202013 citations