QKD useless? This article refutes the NSA!

Recently, the US National Security Agency (NSA) issued a publication evaluating the usability of quantum cryptography, which concluded that the use of the technology is not recommended, which has attracted a lot of attention. In a preprint paper recently posted on arXiv, Swiss scientists respond to this criticism and argue that some of the points made in it don't make sense; Others, though problematic now, are expected to be resolved in the foreseeable future.

“The debate over QKD: A rebuttal to the NSA's objections”

NSA: QKD not recommended?

The US National Security Agency (NSA) recently analyzed quantum cryptography, specifically quantum key distribution (QKD) availability and current technical limitations. The report identifies several challenges and concludes that the use of QKD is not recommended until some challenges are overcome.

In the NSA article, NSA does not recommend the use of quantum key distribution and quantum cryptography to ensure the security of data transmission in National security systems (NSS) and does not expect to certify or approve any QKD or QC security products for use by national security system customers (unless the technical limitations mentioned in the article are addressed).

So in this article, the Swiss scientists set out their arguments against each of the NSA's proposed limitations.

A summary of the assessment of whether the NSA's five proposed issues are limited to the present, medium, and long-term future. The "medium future" refers to an era when cheaper optical devices and quantum Repeaters are widely available, while the "long future" refers to an era of universal quantum computers connected by quantum networks.

Limitation 1: Quantum key distribution provides only a partial solution.

Regarding this view, the Swiss scientists believe that this statement, while correct, cannot be regarded as a limitation specific to quantum cryptography. Whether classical or quantum techniques are used, verification always requires a pre-shared secret or a trusted third party: solving this problem is not the goal of QKD.

Limitation 2: Quantum key distribution requires special purpose equipment.

The Swiss scientists behind this paper believe that the need for specialized hardware, and therefore expensive, is indeed one of the main reasons why QKD is not widely used at present. Nevertheless, with future advances in optical communication technology, this hardware is expected to become more accessible. And the difficulty of patching defective hardware is not a problem specific to quantum cryptography.

Limitation 3: Quantum key distribution increases infrastructure costs and insider threat risk.

Currently, the QKD protocol does require trusted intermediate stations for longer distances. The Swiss scientists counter: "However, this will change once the quantum repeater is developed." These devices work entirely at the quantum level and therefore require no trust. This eliminates any insider threats; While QKD hardware costs are expected to decrease over the next few years, they are still likely to be more expensive than classic communications infrastructure."

Limitation 4: Security and verification of quantum key distribution is a major challenge.

To this view, Swiss scientists argue that the gap between theoretical security and implementation security is a general problem in cryptography, which already exists at the classical level. Since quantum communication is a relatively young field, it has little experience with these issues and is still vulnerable to side-channel attacks. However, this can be solved with a (semi-) device-independent QKD, which requires only minimal (weak) assumptions about the quantum device and is therefore well protected against such attacks. Although the technology is still in its preliminary stages, it offers a clear path to overcoming this challenge in the long-term future.

Limitation 5: Quantum key distribution increases the risk of denial of service.

The current implementation of QKD is usually a single point-to-point link. An adversary with access to the link may successfully carry out a denial of service attack. However, future quantum encryption solutions are expected to operate on quantum-connected networks: as with classical communication networks, information can be rerouted if one of the links fails. Once this stage is reached, there will be no essential difference between classical and quantum cryptography in terms of vulnerability to denial-of-service attacks.

QKD only offers a partial solution?

QKD does not provide authentication, but relies on real classical communication channels that are already established. Because authentication comes at A cost: as shown in the figure, party A must either obtain a pre-shared secret from Party B, or invoke a trusted third party (TTP), who can confirm B's identity to Party A.

In the absence of any initial information about Bob (B), Alice (A) is unable to distinguish whether the information she receives is from Bob (B) or from Eve (E), an opponent pretending to be Bob (B) (left). Any verification scheme (classical or quantum) must rely on something that breaks the symmetry between B and E (from A's point of view). This can be A secret s that A and B share in advance (center picture). Alternatively, A can rely on A trusted third party (T) to distinguish B from E, which requires some sort of initial authentication connection between A and T (right).

This price must be paid whether classical or quantum cryptographic protocols are used. Therefore, QKD's reliance on authentication communication is not a problem specific to quantum cryptography.

Even if the verification method used by QKD is not information theoretically secure, but relies on (computationally secure) asymmetric encryption, QKD is still future-proof, because a "store first, decrypt later" attack won't work. An attacker must breach the verifier in real time to obtain the generated key. Simply storing the exchanged information and waiting for a more powerful computer to decrypt it is not enough to get the key. Once the key generation process is over, no information about the generated key will be revealed even if the verification program is completely cracked.

Of course, there are those who argue that the confidentiality provided by QKD can also be achieved through post-quantum encryption (PQC) (also known as quantum anti-jamming or quantum secure encryption), claiming that the latter has a better understood risk profile.

In this paper, the scientists compare the level of understanding of protocol security and implementation security in post-quantum cryptography (PQC) and quantum key distribution (QKD). Protocol security refers to abstract protocols. For classical protocols, it usually relies on the difficulty of guessing certain mathematical problems, such as hard-to-quantify mathematical problems such as factorization. In contrast, in quantum cryptography, protocol security depends on the laws of physics. Execution security depends on the security of the hardware and software running the abstract protocol, such as their robustness to side-channel attacks. Classical cryptography has an advantage in this respect compared to quantum cryptography because it has accumulated decades of experience, while quantum hardware and software engineering is still in its early stages.

PQC protocols can become unsafe overnight. This is not just a theoretical problem, but a real threat, as evidenced by the National Institute of Standards and Technology's (NIST) PQC standardization process. This search process continued for several years, until some standardized final candidates were announced in 2022, as well as some alternatives. However, it only took a few months for one of these alternatives, called SIKE (short for Superequal Homologous Key Encapsulation), to be cracked on a single-core classical computer.

There are many other examples in the history of cryptography that illustrate the difficulty of evaluating and quantifying the security of computational cryptographic protocols. For example, the inventors of the widely used RSA encryption algorithm originally calculated that factoring a 200-digit number using the best-known factorization method would take several billion years, which is about the same as the estimated remaining life.

In contrast, the security of the QKD protocol can be proven according to the laws of physics. Therefore, it is not affected by algorithm discovery or hardware development. In addition, protocol security can be quantified by the boundary of the probability of the protocol being cracked.

In terms of implementation safety, PQC has an advantage over QKD, although this advantage is temporary. The implementation of PQC can draw on decades of experience in classical computers to gain a good understanding of potential side-channel attacks. On the other hand, the implementation safety of QKD is still in the exploratory stage. Because QKD is a relatively young technology, researchers have little experience with possible side-channel attacks and countermeasures. However, in the next few years, people will learn more and more about this.

With the advancement of optical communication technology, hardware will not be the limit

Another criticism concerns QKD's inability to integrate easily into existing network devices and the difficulty of managing security patches.

QKD requires a communication link that transmits information encoded into a single quantum optical pattern from the sender to the receiver in a high-fidelity manner. In today's implementation of quantum encryption technology, this is achieved through point-to-point fiber or free-space connections. However, current optical communication networks do not provide such high-fidelity links. Therefore, integrating QKD does require expensive specialized hardware.

However, as the efficiency of classical optical communication steadily improves, it is expected to eventually reach the point where each photon can encode one (or even more) bits. In this way, classical technologies will naturally approach the requirements of quantum communication, thus facilitating more direct and cheaper integration of QKD.

There is no essential difference between classical and quantum cryptography when it comes to implementing security: if the hardware is found to be defective or vulnerable to side-channel attacks, patching at the hardware level is required in both cases.

Time-varying protocol security of cryptographic protocols. The graph above shows that if an adversary has all the computing power in the world, the probability of the encryption protocol being broken changes over time. Due to the development of hardware and the discovery of algorithms, classical protocols designed to provide computational security, including post-quantum protocols, are becoming increasingly insecure. If an efficient quantum algorithm is found to crack it (which is the case with RSA), the scheme will become insecure once the first general-purpose quantum computers are available. On the other hand, the probability of failure of quantum key distribution always remains the same because it relies only on the laws of quantum physics, which do not change over time.

The cost of trusted relay is too high

Current QKD implementations require trusted relays, and rightly so.

The typical information carrier in quantum communication is single photon. Since the loss of photons in optical fibers is usually very high, intermediate stations are currently needed to achieve long-distance transmission. There is also the problem of signal loss in classical communication, which requires the use of Repeaters. The repeater measures the received signal, copies it and retransmits it to the other end at higher power, effectively amplifying the signal. But the same technique doesn't work for quantum information because, as the non-cloning theorem asserts, copying quantum information is fundamentally forbidden.

Therefore, the current implementation of QKD is limited to point-to-point connections with no repeater in the middle. When such point-to-point connections are combined into a network, each link of the network must be encoded and decoded separately for communication. But because intermediate nodes need to store secret classical information, they must be trusted.

Long distance QKD is realized through trusted intermediate station and quantum repeater. Using a trusted intermediate station requires establishing a key Ki on each segment. Since these keys are secret classical information, these sites must be trusted. Quantum Repeaters (QR) operate entirely at the quantum level (as shown in the quantum state Ψi). As such, they are protected by the laws of quantum theory and require no trust.

Although this method is mature in theory, it still needs to be applied in practice. The main obstacle is that quantum Repeaters require quantum memory. The most advanced quantum memories are not long enough to outperform direct optical links, although considerable progress has been made in recent years. However, since quantum memory is an important part of quantum computers, it is currently being studied in depth on various technology platforms.

The current implementation of QKD requires a trusted repeater. These Repeaters have to be housed in secure facilities, which is costly. In the medium term, trusted Repeaters can be replaced by quantum Repeaters. While the cost of these devices is expected to decrease with the development of optical technology, the construction cost of quantum communication networks is likely to remain higher than the corresponding infrastructure for classical communication.

And, when trusted nodes are replaced by quantum Repeaters, insider threats do not pose any additional risk.

Theoretical protocol and practical implementation of security measures

The devices used in the implementation, such as quantum sources and detectors, often deviate from their theoretical descriptions, which leads to side-channel attacks that exploit flaws in quantum sources and detectors.

One way to ban such attacks is to adapt the protocol or related parameters so that they tolerate known imperfections; However, imperfections are often unknown, especially in practical applications where devices are exposed to changing environmental conditions.

Another way to rule out the possibility of side-channel attacks is semi-device-independent or device-independent QKD. In this approach, security is guaranteed through weak or even minimum assumptions about the quantum source and detector, thus closing the gap between protocol and implementation security. However, this high level of security comes at a cost: in complete device-independence (neither source nor detector need to be characterized), the protocol requires a proven bug-free Bell test, which presents a huge challenge for experimental implementation.

On the positive side, once a general-purpose quantum computer is available, it will be possible to create perfect Bell pairs on its logical (i.e., error-correcting) qubits. Although the technology is still in its preliminary stages, it offers a clear path to fully safe QKD.

In principle, classical cryptography faces the same threat, namely that the implementation may not be secure; In fact, side channel attack is a huge topic in classical cryptography and an active research area. The problem arises when information is encoded directly into the state of the physical system (that is, without going through other stages, such as storing the information in memory). While this is the case with current QKD implementations, it is not an inherent problem with the use of quantum information.

QKD increases the risk of denial of service

A classic communication network consists of many connections that can be rerouted when one of them fails to work properly. This redundancy helps protect the network from denial-of-service attacks. In contrast, current implementations of QKD are often based on a single point-to-point link, so an adversary with access to the link can easily interrupt service.

However, this is not an inherent problem with QKD. Rather, it is the result of the high price of quantum communication technology, which currently prevents us from building quantum networks with many links. In the long run, when there are larger quantum communication networks, or even quantum Internet, denial-of-service attacks can be fended off by repeated routes, much the same way as in classical networks.

QKD＋PQC＝The most secure encryption method

In fact, the issues highlighted by the NSA are so important that they severely limit the current availability of quantum cryptography. However, it is important to note that these limitations are not inherent to quantum cryptography, but are due to the fact that the new hardware required is still in its early stages. Some of these limitations could be addressed in the medium term with the advent of cheaper and more advanced quantum technologies; However, overcoming the remaining limitations will require long-term investment in the development of quantum communication technologies.

The effort is worth it: quantum cryptography has the potential to offer real advantages over classical cryptography. Unlike traditional encryption schemes, which need to be constantly updated and strengthened to keep pace with technological advances, quantum cryptography breaks this cycle and provides protocol security from all potential threats, including those posed by quantum computers. Quantum cryptographic protocols not only ensure communication security during execution, but also provide eternal security. Regardless of future software and hardware developments, communications using quantum encryption today will always be secure.

Since quantum encryption technology is not yet widely used, it is crucial to develop a strategy for securing perceptual data in the meantime. While standard encryption schemes such as RSA can still be used for data with shorter lifespans (as universal quantum computers have not yet been implemented), for data with longer lifespans, "store first, decrypt later" attacks need to be protected. Therefore, combining quantum key distribution (QKD) and post-quantum encryption (PQC) into a hybrid scheme is currently the most secure data encryption method.

QKD and PQC hybrid cryptosystem. Information M is first encrypted by a PQC scheme, which requires some (quantum-secure) public key infrastructure (PKI) to distribute the required keys. The ciphertext is then additional encrypted by a one-time pad (OTP) using the QKD scheme key.

Finally, there is another current limitation of QKD - namely, its key generation rate is still relatively low, which is not mentioned in the NSA report. This is not a problem if you use QKD to periodically replace AES keys, but if you use it for single-slice encryption, the communication rate is severely limited; We expect to overcome this shortcoming in the medium term.