Quantum cryptography

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks.

History

In the early 1970s, Stephen Wiesner, then at Columbia University in New York, introduced the concept of quantum conjugate coding. His seminal paper titled "Conjugate Coding" was rejected by the IEEE Information Theory Society but was eventually published in 1983 in SIGACT News.

Companies that manufacture quantum cryptography systems include MagiQ Technologies, Inc. (Boston), ID Quantique (Geneva), QuintessenceLabs (Canberra, Australia), Toshiba (Tokyo), QNu Labs (India) and SeQureNet (Paris).

Advantages

Cryptography is the strongest link in the chain of data security.

Applications

Quantum cryptography is a general subject that covers a broad range of cryptographic practices and protocols. Some of the most notable applications and protocols are discussed below.

Quantum key distribution

The best-known and developed application of quantum cryptography is QKD, which is the process of using quantum communication to establish a shared key between two parties (Alice and Bob, for example) without a third party (Eve) learning anything about that key, even if Eve can eavesdrop on all communication between Alice and Bob. If Eve tries to learn information about the key being established, discrepancies will arise causing Alice and Bob to notice. Once the key is established, it is then typically used for encrypted communication using classical techniques. For instance, the exchanged key could be used for symmetric cryptography (e.g. one-time pad).

The security of quantum key distribution can be proven mathematically without imposing any restrictions on the abilities of an eavesdropper, something not possible with classical key distribution. This is usually described as "unconditional security", although there are some minimal assumptions required, including that the laws of quantum mechanics apply and that Alice and Bob are able to authenticate each other, i.e. Eve should not be able to impersonate Alice or Bob as otherwise a man-in-the-middle attack would be possible.

While QKD is secure, its practical application faces some challenges. There are in fact limitations for the key generation rate at increasing transmission distances.

Mistrustful quantum cryptography

In mistrustful cryptography the participating parties do not trust each other. For example, Alice and Bob collaborate to perform some computation where both parties enter some private inputs. But Alice does not trust Bob and Bob does not trust Alice. Thus, a secure implementation of a cryptographic task requires that after completing the computation, Alice can be guaranteed that Bob has not cheated and Bob can be guaranteed that Alice has not cheated either. Examples of tasks in mistrustful cryptography are commitment schemes and secure computations, the latter including the further examples of coin flipping and oblivious transfer. Key distribution does not belong to the area of mistrustful cryptography. Mistrustful quantum cryptography studies the area of mistrustful cryptography using quantum systems.

In contrast to quantum key distribution where unconditional security can be achieved based only on the laws of quantum physics, in the case of various tasks in mistrustful cryptography there are no-go theorems showing that it is impossible to achieve unconditionally secure protocols based only on the laws of quantum physics. However, some of these tasks can be implemented with unconditional security if the protocols not only exploit quantum mechanics but also special relativity. For example, unconditionally secure quantum bit commitment was shown impossible by Mayers

Unlike quantum key distribution, quantum coin flipping is a protocol that is used between two participants who do not trust each other.

A coin flip protocol generally occurs like this:

Cheating occurs when one player attempts to influence, or increase the probability of a particular outcome. The protocol discourages some forms of cheating; for example, Alice could cheat at step 4 by claiming that Bob incorrectly guessed her initial basis when he guessed correctly, but Alice would then need to generate a new string of qubits that perfectly correlates with what Bob measured in the opposite table.

One theoretically surefire way for Alice to cheat is to utilize the Einstein-Podolsky-Rosen (EPR) paradox. Two photons in an EPR pair are anticorrelated; that is, they will always be found to have opposite polarizations, provided that they are measured in the same basis. Alice could generate a string of EPR pairs, sending one photon per pair to Bob and storing the other herself. When Bob states his guess, she could measure her EPR pair photons in the opposite basis and obtain a perfect correlation to Bob's opposite table.

In addition to quantum coin-flipping, quantum commitment protocols are implemented when distrustful parties are involved. A commitment scheme allows a party Alice to fix a certain value (to "commit") in such a way that Alice cannot change that value while at the same time ensuring that the recipient Bob cannot learn anything about that value until Alice reveals it. Such commitment schemes are commonly used in cryptographic protocols (e.g. Quantum coin flipping, Zero-knowledge proof, secure two-party computation, and Oblivious transfer).

In the quantum setting, they would be particularly useful: Crépeau and Kilian showed that from a commitment and a quantum channel, one can construct an unconditionally secure protocol for performing so-called oblivious transfer.

Unfortunately, early quantum commitment protocols

Yet, the result by Mayers does not preclude the possibility of constructing quantum commitment protocols (and thus secure multi-party computation protocols) under assumptions that are much weaker than the assumptions needed for commitment protocols that do not use quantum communication. The bounded quantum storage model described below is an example for a setting in which quantum communication can be used to construct commitment protocols. A breakthrough in November 2013 offers "unconditional" security of information by harnessing quantum theory and relativity, which has been successfully demonstrated on a global scale for the first time.

Physical unclonable functions can be also exploited for the construction of cryptographic commitments.

Bounded- and noisy-quantum-storage model

One possibility to construct unconditionally secure quantum commitment and quantum oblivious transfer (OT) protocols is to use the bounded quantum storage model (BQSM). In this model, it is assumed that the amount of quantum data that an adversary can store is limited by some known constant Q. However, no limit is imposed on the amount of classical (i.e., non-quantum) data the adversary may store.

In the BQSM, one can construct commitment and oblivious transfer protocols.

The protocols in the BQSM presented by Damgård, Fehr, Salvail, and Schaffner

The advantage of the BQSM is that the assumption that the adversary's quantum memory is limited is quite realistic. With today's technology, storing even a single qubit reliably over a sufficiently long time is difficult. (What "sufficiently long" means depends on the protocol details. By introducing an artificial pause in the protocol, the amount of time over which the adversary needs to store quantum data can be made arbitrarily large.)

An extension of the BQSM is the noisy-storage model introduced by Wehner, Schaffner and Terhal.

In the classical setting, similar results can be achieved when assuming a bound on the amount of classical (non-quantum) data that the adversary can store.

Position-based quantum cryptography

The goal of position-based quantum cryptography is to use the geographical location of a player as its (only) credential. For example, one wants to send a message to a player at a specified position with the guarantee that it can only be read if the receiving party is located at that particular position. In the basic task of position-verification, a player, Alice, wants to convince the (honest) verifiers that she is located at a particular point. It has been shown by Chandran et al. that position-verification using classical protocols is impossible against colluding adversaries (who control all positions except the prover's claimed position).

Under the name of 'quantum tagging', the first position-based quantum schemes have been investigated in 2002 by Kent. A US-patent

Device-independent quantum cryptography

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.

In 2018, theoretical studies performed by Arnon- Friedman et al. suggest that exploiting a property of entropy that is later referred to as "Entropy Accumulation Theorem (EAT)", an extension of Asymptotic equipartition property, can guarantee the security of a device independent protocol.

Post-quantum cryptography

Quantum computers may become a technological reality; it is therefore important to study cryptographic schemes used against adversaries with access to a quantum computer. The study of such schemes is often referred to as post-quantum cryptography. The need for post-quantum cryptography arises from the fact that many popular encryption and signature schemes (schemes based on ECC and RSA) can be broken using Shor's algorithm for factoring and computing discrete logarithms on a quantum computer. Examples for schemes that are, as of today's knowledge, secure against quantum adversaries are McEliece and lattice-based schemes, as well as most symmetric-key algorithms.

There is also research into how existing cryptographic techniques have to be modified to be able to cope with quantum adversaries. For example, when trying to develop zero-knowledge proof systems that are secure against quantum adversaries, new techniques need to be used: In a classical setting, the analysis of a zero-knowledge proof system usually involves "rewinding", a technique that makes it necessary to copy the internal state of the adversary. In a quantum setting, copying a state is not always possible (no-cloning theorem); a variant of the rewinding technique has to be used.

Post quantum algorithms are also called "quantum resistant", because – unlike quantum key distribution – it is not known or provable that there will not be potential future quantum attacks against them. Even though they may possibly be vulnerable to quantum attacks in the future, the NSA is announcing plans to transition to quantum resistant algorithms.

Quantum cryptography beyond key distribution

So far, quantum cryptography has been mainly identified with the development of quantum key distribution protocols. Unfortunately, symmetric cryptosystems with keys that have been distributed by means of quantum key distribution become inefficient for large networks (many users), because of the necessity for the establishment and the manipulation of many pairwise secret keys (the so-called "key-management problem"). Moreover, this distribution alone does not address many other cryptographic tasks and functions, which are of vital importance in everyday life. Kak's three-stage protocol has been proposed as a method for secure communication that is entirely quantum unlike quantum key distribution, in which the cryptographic transformation uses classical algorithms

Besides quantum commitment and oblivious transfer (discussed above), research on quantum cryptography beyond key distribution revolves around quantum message authentication,

Y-00 protocol

H. P. Yuen presented Y-00 as a stream cipher using quantum noise around 2000 and applied it for the U.S. Defense Advanced Research Projects Agency (DARPA) High-Speed and High-Capacity Quantum Cryptography Project as an alternative to quantum key distribution.

Unlike quantum key distribution protocols, the main purpose of Y-00 is to transmit a message without eavesdrop-monitoring, not to distribute a key. Therefore, privacy amplification may be used only for key distributions.

The principle of operation is as follows. First, legitimate users share a key and change it to a pseudo-random keystream using the same pseudo-random number generator. Then, the legitimate parties can perform conventional optical communications based on the shared key by transforming it appropriately. For attackers who do not share the key, the wire-tap channel model of Aaron D. Wyner is implemented. The legitimate users' advantage based on the shared key is called "advantage creation". The goal is to achieve longer covert communication than the information-theoretic security limit (one-time pad) set by Shannon.

Although the main purpose of the protocol is to transmit the message, key distribution is possible by simply replacing the message with a key.

On the other hand, it is currently unclear what implementation realizes information-theoretic security, and security of this protocol has long been a matter of debate.

Implementation in practice

In theory, quantum cryptography seems to be a successful turning point in the information security sector. However, no cryptographic method can ever be absolutely secure.

Single-photon source assumption

The theoretical basis for quantum key distribution assumes the use of single-photon sources. However, such sources are difficult to construct, and most real-world quantum cryptography systems use faint laser sources as a medium for information transfer.

Identical detector efficiency assumption

In practice, multiple single-photon detectors are used in quantum key distribution devices, one for Alice and one for Bob.

Deprecation of quantum key distributions from governmental institutions

Because of the practical problems with quantum key distribution, some governmental organizations recommend the use of post-quantum cryptography (quantum resistant cryptography) instead. For example, the US National Security Agency,

For example, the US National Security Agency addresses five issues: