Device-independent quantum cryptography

Last updated

A quantum cryptographic protocol is device-independent if its security does not rely on trusting that the quantum devices used are truthful. Thus the security analysis of such a protocol needs to consider scenarios of imperfect or even malicious devices. Several important problems have been shown to admit unconditional secure and device-independent protocols. A closely related topic (that is not discussed in this article) is measurement-device independent quantum key distribution.

Contents

Overview and history

Mayers and Yao [1] proposed the idea of designing quantum protocols using "self-testing" quantum apparatus, the internal operations of which can be uniquely determined by their input-output statistics. Subsequently, Roger Colbeck in his Thesis [2] proposed the use of Bell tests for checking the honesty of the devices. Since then, several problems have been shown to admit unconditional secure and device-independent protocols, even when the actual devices performing the Bell test are substantially "noisy," i.e., far from being ideal. These problems include quantum key distribution, [3] [4] randomness expansion, [4] [5] and randomness amplification. [6]

Key distribution

The goal of quantum key distribution is for two parties, Alice and Bob, to share a common secret string through communications over public channels. This was a problem of central interest in quantum cryptography. It was also the motivating problem in Mayers and Yao's paper. [1] A long sequence of works aim to prove unconditional security with robustness.[ citation needed ] Vazirani and Vidick [3] were the first to reach this goal. Subsequently, Miller and Shi [4] proved a similar result using a different approach.

Randomness expansion

The goal of randomness expansion is to generate a longer private random string starting from a uniform input string and using untrusted quantum devices. The idea of using Bell test to achieve this goal was first proposed by Roger Colbeck in his Ph.D. Thesis. [2] Subsequent works have aimed to prove unconditional security with robustness and the increase the rate of expansion. [ citation needed ] Vazrani and Vidick were the first to prove full quantum security for an exponentially expanding protocol. [7] Miller and Shi [4] achieved several additional features, including cryptographic level security, robustness, and a single-qubit requirement on the quantum memory. The approach was subsequently extended by the same authors to show that the noise level can approach the obvious upper bound, when the output may become deterministic. [5]

Randomness amplification

The goal of randomness amplification is to generate near-perfect randomness (approximating a fair coin toss) starting from a single source of weak randomness (a coin each of whose tosses is somewhat unpredictable, though it may be biased and correlated with previous tosses). This is known to be impossible classically. [8] However, by using quantum devices, it becomes possible even if the devices are untrusted. Roger Colbeck and Renato Renner were motivated by physics considerations to ask the question first. [9] Their construction and the subsequent improvement by Gallego et al. [10] are secure against a non-signalling adversary, and have significant physical interpretations. The first construction that does not require any structural assumptions on the weak source is due to Chung, Shi, and Wu. [6] . Since then, research has focused on making constructions that are suitable for implementation. [11] [12]

Related Research Articles

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that takes advantage of quantum mechanical phenomena.

Quantum key distribution (QKD) is a secure communication method that implements a cryptographic protocol involving components of quantum mechanics. It enables two parties to produce a shared random secret key known only to them, which then can be used to encrypt and decrypt messages. The process of quantum key distribution is not to be confused with quantum cryptography, as it is the best-known example of a quantum-cryptographic task.

<span class="mw-page-title-main">Manuel Blum</span> Venezuelan computer scientist

Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

A cryptosystem is considered to have information-theoretic security if the system is secure against adversaries with unlimited computing resources and time. In contrast, a system which depends on the computational cost of cryptanalysis to be secure is called computationally, or conditionally, secure.

BB84 is a quantum key distribution scheme developed by Charles Bennett and Gilles Brassard in 1984. It is the first quantum cryptography protocol. The protocol is provably secure assuming a perfect implementation, relying on two conditions: (1) the quantum property that information gain is only possible at the expense of disturbing the signal if the two states one is trying to distinguish are not orthogonal ; and (2) the existence of an authenticated public classical channel. It is usually explained as a method of securely communicating a private key from one party to another for use in one-time pad encryption. The proof of BB84 depends on a perfect implementation. Side channel attacks exist, taking advantage of non-quantum sources of information. Since this information is non-quantum, it can be intercepted without measuring or cloning quantum particles.

Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.

In theoretical physics, quantum nonlocality refers to the phenomenon by which the measurement statistics of a multipartite quantum system do not allow an interpretation with local realism. Quantum nonlocality has been experimentally verified under a variety of physical assumptions. Any physical theory that aims at superseding or replacing quantum theory should account for such experiments and therefore cannot fulfill local realism; quantum nonlocality is a property of the universe that is independent of our description of nature.

SARG04 is a 2004 quantum cryptography protocol derived from the first protocol of that kind, BB84.

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).

The noisy-storage model refers to a cryptographic model employed in quantum cryptography. It assumes that the quantum memory device of an attacker (adversary) trying to break the protocol is imperfect (noisy). The main goal of this model is to enable the secure implementation of two-party cryptographic primitives, such as bit commitment, oblivious transfer and secure identification.

Within quantum cryptography, the Decoy state quantum key distribution (QKD) protocol is the most widely implemented QKD scheme. Practical QKD systems use multi-photon sources, in contrast to the standard BB84 protocol, making them susceptible to photon number splitting (PNS) attacks. This would significantly limit the secure transmission rate or the maximum channel length in practical QKD systems. In decoy state technique, this fundamental weakness of practical QKD systems is addressed by using multiple intensity levels at the transmitter's source, i.e. qubits are transmitted by Alice using randomly chosen intensity levels, resulting in varying photon number statistics throughout the channel. At the end of the transmission Alice announces publicly which intensity level has been used for the transmission of each qubit. A successful PNS attack requires maintaining the bit error rate (BER) at the receiver's end, which can not be accomplished with multiple photon number statistics. By monitoring BERs associated with each intensity level, the two legitimate parties will be able to detect a PNS attack, with highly increased secure transmission rates or maximum channel lengths, making QKD systems suitable for practical applications.

Quantum readout is a method to verify the authenticity of an object. The method is secure provided that the object cannot be copied or physically emulated.

<span class="mw-page-title-main">Three-stage quantum cryptography protocol</span>

The three-stage quantum cryptography protocol, also known as Kak's three-stage protocol is a method of data encryption that uses random polarization rotations by both Alice and Bob, the two authenticated parties, that was proposed by Subhash Kak. In principle, this method can be used for continuous, unbreakable encryption of data if single photons are used. It is different from methods of QKD for it can be used for direct encryption of data, although it could also be used for exchanging keys.

In information security, message authentication or data origin authentication is a property that a message has not been modified while in transit and that the receiving party can verify the source of the message.

The six-state protocol (SSP) is the quantum cryptography protocol that is the version of BB84 that uses a six-state polarization scheme on three orthogonal bases.

Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography. Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols, e.g. Quantum Byzantine agreement.

Randomized benchmarking is an experimental method for measuring the average error rates of quantum computing hardware platforms. The protocol estimates the average error rates by implementing long sequences of randomly sampled quantum gate operations. Randomized benchmarking is the industry-standard protocol used by quantum hardware developers such as IBM and Google to test the performance of the quantum operations.

Relativistic quantum cryptography is a sub-field of quantum cryptography, in which in addition to exploiting the principles of quantum physics, the no-superluminal signalling principle of relativity theory stating that information cannot travel faster than light is exploited too. Technically speaking, relativistic quantum cryptography is a sub-field of relativistic cryptography, in which cryptographic protocols exploit the no-superluminal signalling principle, independently of whether quantum properties are used or not. However, in practice, the term relativistic quantum cryptography is used for relativistic cryptography too.

Adrian Kent is a British theoretical physicist, Professor of Quantum Physics at the University of Cambridge, member of the Centre for Quantum Information and Foundations, and Distinguished Visiting Research Chair at the Perimeter Institute for Theoretical Physics. His research areas are the foundations of quantum theory, quantum information science and quantum cryptography. He is known as the inventor of relativistic quantum cryptography. In 1999 he published the first unconditionally secure protocols for bit commitment and coin tossing, which were also the first relativistic cryptographic protocols. He is a co-inventor of quantum tagging, or quantum position authentication, providing the first schemes for position-based quantum cryptography. In 2005 he published with Lucien Hardy and Jonathan Barrett the first security proof of quantum key distribution based on the no-signalling principle.

Antonio Acín Dal Maschio is a Spanish theoretical physicist, currently an ICREA professor at ICFO – The Institute of Photonic Sciences in Castelldefels, near Barcelona.

References

  1. 1 2 Mayers, Dominic; Yao, Andrew C.-C. (1998). Quantum Cryptography with Imperfect Apparatus. IEEE Symposium on Foundations of Computer Science (FOCS). arXiv: quant-ph/9809039 . Bibcode:1998quant.ph..9039M.
  2. 1 2 Colbeck, Roger (December 2006). "Chapter 5". Quantum And Relativistic Protocols For Secure Multi-Party Computation (Thesis). University of Cambridge. arXiv: 0911.3814 .
  3. 1 2 Vazirani, Umesh; Vidick, Thomas (2014). "Fully Device-Independent Quantum Key Distribution". Physical Review Letters. 113 (14): 140501. arXiv: 1210.1810 . Bibcode:2014PhRvL.113n0501V. doi:10.1103/physrevlett.113.140501. PMID   25325625. S2CID   119299119.
  4. 1 2 3 4 Miller, Carl; Shi, Yaoyun (2016). "Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices". Journal of the ACM. 63 (4): 33. arXiv: 1402.0489 . doi:10.1145/2885493. S2CID   53234710.
  5. 1 2 Miller, Carl; Shi, Yaoyun (2017). "Universal security for randomness expansion". SIAM Journal on Computing. 46 (4): 1304–1335. arXiv: 1411.6608 . doi:10.1137/15m1044333. S2CID   6792482.
  6. 1 2 Chung, Kai-Min; Shi, Yaoyun; Wu, Xiaodi (2014). "Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions". arXiv: 1402.4797 [quant-ph].
  7. ↑ Vazirani, Umesh; Vidick, Thomas (2012). "Certifiable quantum dice: or, true random number generation secure against quantum adversaries". The 44th Symposium on Theory of Computing (STOC). pp. 61–76.
  8. ↑ Miklos Santha, Umesh V. Vazirani (1984-10-24). "Generating quasi-random sequences from slightly-random sources" (PDF). Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. University of California. pp. 434–440. ISBN   0-8186-0591-X . Retrieved 2006-11-29.
  9. ↑ Colbeck, Roger; Renner, Roger (2012). "Free randomness can be amplified". Nature Physics. 8 (6): 450–453. arXiv: 1105.3195 . Bibcode:2012NatPh...8..450C. doi:10.1038/nphys2300. S2CID   118309394.
  10. ↑ Gallego, Rodrigo; Masanes, Lluis; De La Torre, Gonzalo; Dhara, Chirag; Aolita, Leandro; Acín, Antonio (2014). "Full randomness from arbitrarily deterministic events". Nature Communications. 4: 2654. arXiv: 1210.6514 . Bibcode:2013NatCo...4.2654G. doi:10.1038/ncomms3654. PMID   24173040. S2CID   14630558.
  11. ↑ Max Kessler, Rotem Arnon-Friedman (31 July 2020). "Device-Independent Randomness Amplification and Privatization". IEEE Journal on Selected Areas in Information Theory. doi:10.1109/JSAIT.2020.3012498.
  12. ↑ Cameron Foreman, Sherilyn Wright, Alec Edgington, Mario Berta, and Florian J. Curchod (2023-03-30). "Practical randomness amplification and privatisation with implementations on quantum computers". Quantum. doi:10.22331/q-2023-03-30-969.{{cite journal}}: CS1 maint: multiple names: authors list (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.