Score:15

Why Quantum Key Distribution (QKD) is impractical

in flag

In NSA's FAQ on Quantum Computing and Post-Quantum Cryptography, it is mentioned as

Q: Should I use a QKD system to protect my NSS from a quantum computer?
A: No. The technology involved is of significant scientific interest, but it only addresses some security threats and it requires significant engineering modifications to NSS communications systems. NSA does not consider QKD a practical security solution for protecting national security information. NSS owners should not be using or researching QKD at this time without direct consultation with NSA. For specific questions, NSS owners can contact NSA.

and In a Tweet, Nigel Smart responded as

It is not just NSA who does not see the point of QKD.
All serious cryptographers think the same.....

While there are many companies and researchers working on these, why is Quantum Key Distribution (QKD) impractical?

kelalaka avatar
in flag
A canonical answer is required!
kelalaka avatar
in flag
This might be dupe of this [What makes Quantum Cryptography secure?](https://crypto.stackexchange.com/q/51311/18298) and cross-site dupe of this [Advantage of quantum key distribution over post-quantum cryptography](https://quantumcomputing.stackexchange.com/q/142/4866)
Paul Uszak avatar
cn flag
Slightly opinionated question given the megabucks spent globally progressing QKD?
us flag
Yes, the question is intentionally opinionated. Dollars spent is not always a great proxy for merit.
Paul Uszak avatar
cn flag
Consider what some dude in a weird hat said a while ago: _”You can fool of the people some of the time, and you can fool some of the people all of the time, but you can’t fool all of the people all of the time”_ Was he wrong? Are all of the governments /banks /NATO /universities /corporations /physicists /engineers being fooled? Or is it just that with QKDN we don’t need cryptographers any more and it’s just sour grapes? And so a very biased and leading question. And so the downvote.
Geoffroy Couteau avatar
cn flag
"With QKDN we don't need cryptographers anymore" sounds plain nonsensical, since (1) QKD addresses (at best) at teeny-tiny fraction of what cryptography and cryptographer's work is about, and (2) it addresses it terribly. Let me try to make the point super clear: if you want to use QKD to avoid having to trust anything, either a computational assumption or a third party, you're going to fail, since QKD does not let you do that. What it enables is considerably weaker and less appealing than that, and it costs a lot.
Vadym Fedyukovych avatar
in flag
Quantum key exchange was the first application that was taken serious enough, like this NSA recommendation. It shows direct replacement, leading to cost/efficiency discussion. Bell inequality is another cornerstone that might lead to something new, rather than a sort of replacement. With "Mermin-Peres square" game, it might be easier to introduce a novel interactive proof system with properties beyond classic.
poncho avatar
my flag
@PaulUszak: if you believe that QKD is practical, why don't you add an answer detailing the reasons for that (and please don't make it just "there's a large group of people who agree with me", instead spell out the reasons...)
Score:22
cn flag

When we say a solution is impractical, we don't mean that it can't work at all; instead, we mean that it has serious deficiencies compared to other ways to solve the same problem. For example, one could use an airplane to go visit your neighbor who lives 100 meters away; we would all agree that there are considerably easier methods, and so using the airplane is "impractical".

The problem that QKD attempts to solve is secure communication; that is, how can Alice send a message to Bob in a way that is "secure". Of course, to try to determine practicality, we would need to consider the other possible solutions and how they compare to the QKD solution. In this case, the obvious alternatives include an entirely symmetric based system (e.g. a Kerberos-like system), and something that uses postquantum cryptography (e.g. Classic McEliece and Sphincs+) [1].

The line of thoughts which I sketch below is the opinion of most experts and should make it relatively clear.

Here is a list of some major points where the solutions differ:

QKD requires specific types of media to operate

As of right now, QKD can been demonstrated only on short-to-medium length (< 400 km) fiber optic, and free-space communication (point a laser at a target that's within line-of-sight) [2]. If your existing network that uses any other media a significant amount (e.g. microwave or satellite or long distance fiber optic or WiFi), well, you'd have to rework a large part of your network (and good luck trying to get a secure connection from, say, London to Tokyo).

In contrast, the alternative solutions have no such limitation.

What are the security assumptions?

QKD proponents often make the claim "the laws of Quantum Mechanics imply the no-cloning theorem, hence your data is provably secure". While the first part is certainly true, it does not necessarily follow that the data is secure. After all, the laws of Quantum Mechanics do not prove that your QKD device is actually operating as designed, and does not prove that there are no side-channel attacks (that is, attacks where the adversary takes advantage of information beyond what the abstract model gives the attacker) available. Those are security assumptions that a QKD user needs to make (in addition to the relatively safe "QM is a good description of the universe" assumption). Now, QKD vendors are aware of this, and do attempt to provide protections - you still need to assume that there isn't something they missed. See for example this article from The Register.

When we look at the alternative solutions, they are complexity-based (that is, they assume that the computational problem that the attacker must solve is just too hard). At first glance, this might seem like a stronger [3] assumption; however we can fairly cheaply use overdesigned crypto (e.g. 5xAES256 or AES-ChaCha-Serpent combination, or McEliece with double the matrix size); doing so certainly has a cost; however a far smaller cost than a QKD system. Hence, I would call this point a tie...

How are you planning to authenticate the key exchange?

Plain key exchange can only protect you against passive observers. But real world adversaries tend to refuse to follow our nice idealized attack models. If you want (and you do) protection against active adversaries, who can mount man-in-the-middle attacks, you need authenticated key exchange (see e.g. this paper). How will you authenticate, given that there exists no magical assumption-less quantum signature scheme? You have two options:

(1) With a traditional (computationally secure) signature scheme. But then, you're given up on the reason you were using QKD in the first place, which is to avoid computational assumptions. If you choose (1), then you should definitely consider just running a nice classical authenticated key exchange protocol with computational security, e.g. one based on LWE or coding theoretic assumptions. (*)

(2) With a short pre-shared random key, hardcoded in the device by the manufacturer, then using the Carter-Wegman MAC and QKD to re-generate shared key material along the way. But then, congratulations: you've successfully replaced well-studied computational hardness assumption by a trusted setup assumption: the assumption that the manufacturer is a perfectly trusted third party, who honestly hardcoded uniformly random identical keys in the devices, and of course did not keep any trace of this key, nor did not share it with anyone else. If you are familiar with cryptography, this should ring a bell: avoiding this type of trusted setup assumption is the whole point of cryptography in the first place. In this case, I urge you to consider that "LWE is secure" is a much safer assumption that "my manufacturers is perfectly honest, not greedy, cannot be corrupted, and will not keep the key or share it with anyone".

(*) For completeness, there are two ways in which we should tone down (1) a bit: (a) one might prefer have perfect privacy and computational authentication, since the former is everlasting and the latter is on-the-spot; (b) signatures can be built from symmetric cryptography, and it is theoretically possible that symmetric cryptography exists while public key cryptography (necessary for key exchange) does not. Now, it's a tiny theoretical window, but if this is what you fear and you are ready to pay the cost of QKD to cope with this fear, it is technically a valid reason.

What are you planning to do with this shared key?

QKD just provides a key to both sides; how do we use this key to protect the message (which is, after all, the entire point of this exercise)?

If you plan to use them to encrypt your data with AES, then you're again making a computational assumption, and you lost again this nice perfect privacy QKD was promised to come with. So, here again, you are not paying the price of QKD to get perfect security, but only to gain the ability to rely on post-quantum symmetric assumption (e.g. "AES is secure against quantum computers") instead of public-key assumption. And, remember, one of our alternatives already relied only on this symmetric assumption.

On the other hand, if you use the QKD-generated key stream to directly encrypt the data (with an informationally-secure MAC, one would hope), then we run into the next problem - QKD systems are not that fast. Now, they have been getting faster over time, and given that performance is an engineering problem, not a physics-based limitation, it seems plausible that the speed up will continue over time. However, the speed they go right now is far slower than how fast real networks run - this is a significant performance bottleneck.

Cost

Right now, QKD systems are expensive (the cost has been going down; however they're still pricy). In contrast, the alternative solutions can be implemented on standard hardware cheaply.

Bottom line: the alternatives are as good or better on all points.

[1]: A third alternative that I chose not to expand on would be "one-time-pad". I believe that is also impractical; however it may bear comparing to an OTP...

[2]: Quantum entanglement has been demonstrated as a proof-of-concept between ground and a satellite, however there's a long way to go between what they have and a practical usable system.

[3]: "Stronger" means "we have to assume more". In this instance, "stronger" is a bad thing - we want our security assumptions to be a weak as possible.

poncho avatar
my flag
While I agree that QKD is rarely (if ever) the appropriate solution, I would disagree that the requirement for authentication is the technically difficult point. As the Paterson et al paper states, a Carter-Wegman MAC is informationally secure (given a short initial shared seed) for a single message, and you can use some of the QKD generated bits to generate MAC keys for later messages (and yes, practical QKD systems do this). This leaves the requirement to have an initial seed; since these are physical boxes, shipping pairs of devices with the same initial seed is not impractical.
Geoffroy Couteau avatar
cn flag
I did not say that it is hard, I say it uses computational assumptions in any realistic implementation. How do you intend to pre share these necessary short seeds? If you have a secure way to do that, why not use this instead of QKD?
Geoffroy Couteau avatar
cn flag
and yes, I know you can "ship physical boxes". But (1) does this really scale? and (2) is this really ever mentioned when people sell you QKD? This is the point I am trying to make here.
poncho avatar
my flag
The obvious way to share the short seeds is to install them in the QKD devices before they are shipped from the manufacturer. Now, QKD manufacturers have other ways to reestablish the seeds (otherwise they'd be an obvious DoS attack), however I don't recall the details on what that might be. Of course, if you do assume manufacturer-installed pairwise seeds, the obvious question is "we know how to convert seeds into long streams using symmetric cryptography, why don't we do that?". I haven't heard a satisfying answer to that...
poncho avatar
my flag
Does this really scale? Well, if QKD devices are point-to-point links, well, only two devices share the same seed - I don't see the scaling problem...
Geoffroy Couteau avatar
cn flag
then we essentially agree, feel free to modify the answer to put more emphasis on the second point (what do you intend to do with the keys?), which applies equally to the pre-shared key "solution" to authentication and to the QKD generated keys
Geoffroy Couteau avatar
cn flag
(what I mean above is that I'd be fine if various people modify this answer heavily to make it something we can commonly agree on, and make it a community wiki answer, since OP is asking for a canonical answer)
Paul Uszak avatar
cn flag
@poncho There is now work on multi-point QKDN. See https://www.researchgate.net/figure/The-QKD-point-to-multipoint-PON-Alice-and-all-of-the-Bobs-are-constructed-from-fiber_fig6_2974954 and there are others...
poncho avatar
my flag
Ok, I **massively** edited the text (I'm pretty sure there's more new text than what I left unchanged); feel free to correct it...
Paul Uszak avatar
cn flag
This argument isn't going to work at all . See history. Geoffroy; OTPs are useless and impractical too if you listen to the rhetoric here within. Yet $QKND \to OTP$. And that's why you speak French and not German. This is hard stuff [ :-) ] but we can try to be objective. Just because cryptographers are no longer required doesn't mean the people should be denied perfect (informationally secure) privacy.
SAI Peregrinus avatar
si flag
OTPs are useless in practice for almost all cases, and for the same reasons as QKD. The overhead of sharing and managing massive amounts of key material is ridiculously expensive for no practical confidentiality gain. And the confidentiality loss if any part of the keystream gets re-used makes them less secure than something like AES-GCM-SIV or ChaCha20-DAENCE.
Geoffroy Couteau avatar
cn flag
After pondering for a moment, I'm really convinced that the computational assumption argument, which poncho removed from the current answer, is actually an important and convincing one. I'll try to flesh it out and add it back later, and people can tell me if it sounds appropriate. Btw, I did not understand most of your comment, Paul (OTP is indeed impractical, I don't see the relation with the fact that I speak French or the point of mentioning "cryptographers are no longer required").
Geoffroy Couteau avatar
cn flag
@poncho I added back a paragraph about authentication, because I feel it's an important point to convey. In particular, it is the only point that makes it 100% clear that your choice is not "perfect security or computational security", but "trusted setup assumption or computational security", which sounds much less appealing.
kodlu avatar
sa flag
Nice answer. In the context of your paragraph "what are you planning to do with this shared key?", one scenario may be that the two parties having this shared key with a 100% guarantee that it has not been tampered with (due to quantum properties) can use it to securely decrypt (classical) transmissions from a central transmitter, perhaps a satellite. Overkill? For most commercial applications, most likely yes.
Score:6
ng flag

Impracticability of Quantum Key Distribution (QKD), starting with the two showstoppers

  1. QKD is network-adverse, because it requires setting up a QDK-compatible link between the two crypto endpoints. AFAIK the only two options are direct line of sight, and laying out an optical fiber. Ordinary fiber transceiver and switches are not usable, thus forget about the existing fiber network infrastructure. QKD crypto at endpoints of a network is still a research topic, for it requires QKD-compatible optical switches. Using single photons is necessary for the security, but for a given speed/reliability limits path length. The bleeding edge is like 500 km between endpoints even with ultra-low loss fiber and no optical switch (which could only lower that). Options envisioned for larger distance are line of sight (launching a satellite or drone, aiming something to it precisely enough, and hoping there's no cloud, fog, or rain); or/and... trusting intermediary endpoints won't eavesdrop!!

  2. QKD's security requires inconvenient setup procedures for each pair of crypto endpoints, comparable to those of symmetric cryptography, and much worse than those of asymmetric cryptography ubiquitously used for key distribution (e.g. with the https protocol of a web browser). Insuring a quantum-distributed key is not available to an attacker requires one of:

    • Physically insuring attackers can't insert on the link (e.g. make the whole fiber or optical path observable).
    • Sending a "pre-established secret key" (reference) using a trusted courier before the setup, just like in symmetric cryptography. That's the least inconvenient, and thus most common in secure QKD. The courier can carry the secret as ink on paper in an opaque envelope before link setup, and carry several numbered envelopes, with allows to repeat the setup procedure a few times without sending a new courier.
    • Start the link setup procedure, then send a public value determined in that phase using a trusted courier or other link with assumed integrity, then finish the setup. But it's inconvenient to wait for the courier and insure physical security of an extremity device during that time, so it's tempting to assume tone of voice over the phone will do for integrity.
  3. QKD itself is slow. We are talking few kbit/s over 100 km for commercial offers, enough for voice and text. For high rates, QKD is thus typically paired with classic high-speed fiber links protected by classical symmetric cryptography. That solves the speed problem, but removes one of the security benefits of QKD, and makes the system more complex.

  4. QKD needs complex algorithms to overcome its error rate in a secure way. This is believed OK, but requires a new setup procedure after a glitch like power loss. Overcoming that adds on complexity and makes security harder to analyze.

  5. QKD systems have a poor track record when it comes to security. Two commercial systems have been practically broken (reference), and that's for physical reasons independent of errors in the implementation of the software for 4. Broadly speaking, attackers exploit the differences between the physical devices used, and their model in the security proofs of QKD.

  6. No QKD system has passed security certification AFAIK (though a Quantum Random Number Generator has, as well as a classical high-speed encryption device that can be connected to a QKD device explicitly excluded from the certification).

  7. QKD systems are not standardized, not interoperable, not widely used outside of labs. Those marketed for field use are expensive (I don't know a price tag but I'd bet it compares to that of a car, and that excludes putting down the fiber).

Benefits of QKD, starting with the most striking:

  • QKD's security does not rely on hardness conjectures about solving problems used in asymmetric cryptography (current and post-quantum); like integer factorization, discrete logarithm in some group, lattice problems. That's of considerable theoretical interest, and could become of practical interest if Quantum Computers ever become useful for cryptanalysis (but many doubt this will happen; and Post Quantum Cryptography does asymmetric crpyto on today's computers and networks, and hopes to resist these hypothetical QCs).
  • If we can tolerate the slowness (see 3), then QKD does not rely on P≠NP, nor on hardness conjectures about solving problems used in symmetric cryptography; thus provides the strongest assurance that future progress won't allow to break intercepts made before such progress. From this standpoint, the slow breed of QKD is thus superior to today's hybrid cryptosystems with forward-secrecy (but this benefit is moot, because it seems inconceivable that QC or anything will break comfortably-sized symmetric cryptography, thus today's forward secrecy adequately deals with attacks enabled by future progress).
  • QKD allows the third setup option in 2 (that is, use a courier or other mean trusted for integrity to transfer a public value during the link setup) while that's impossible with symmetric cryptography (which requires confidentiality for the transfer of a secret value). That's still less convenient than asymmetric cryptography, which can use a courier or other mean trusted for integrity before link setup to establish trust in a public key, and then a PKI to establish a link between any two points of the globe under a second.
Maarten Bodewes avatar
in flag
Please review. Note that I understood that it is perfectly possible to fuse existing fibers to use QKD - but I'm not an engineer. Generally there would be no need for a shovel if I understood correctly - assuming that it is possible to create a single fiber connection from several strands that connect A to B. Most businesses in the first world would use fiber anyway. It's probably not cheap though, as you would need to rent the fiber connections from the telco.
fgrieu avatar
ng flag
@Maarten Bodewes: It's common practice to join together two standard optical fibers, with a Fiber Optic Fusion Splicer. But It causes some attenuation, and is avoided inasmuch as possible. I don't know if QKD survives splicing, but I am sure splicing does not allow to get around the 500 km practical limit I mention for QKD. A data point: [421 km claimed record in late 2018](https://www.unige.ch/gap/qic/qtech//news/421km-record-distance-qkd) with ultralow-loss fiber. No way to get much longer distance with fiber without a trusted relay station (which needs a courier at setup).
Nike Dattani avatar
in flag
A great contribution to this stack site indeed! One comment that came to mind was about paragraph 1, in which you talk about needing optical fibers; and you also talk about a 500km practical limit. What about satellite-based QKD like in this paper discussing [QKD over 1200km](https://www.nature.com/articles/nature23655)? You did mention "launching a satellite" later in the paragraph, but it wasn't clear whether or not you thought that would lead to a "practical" way forward for QKD.
fgrieu avatar
ng flag
@Nike Dattani: I think the answer already makes it clear the 500 km limit applies to fiber. I intentionally mentioned the possibility of satellite to overcome that limit without taking a position about if it's practical or not, because I have no informed opinion. I remember claims of QKD at long distance or/and high bit rate that on analysis were totally unsustainable in a secure system, for lack of proper consideration about the error rate, or because multiple-photon bursts had been used.
Nike Dattani avatar
in flag
For the 500km limit I was also referring to your comment, but since you're aware of the paper claiming 1200km, I'm not too concerned anymore. About the requirement for a link between two points, isn't that necessary for any type of communication?
fgrieu avatar
ng flag
@Nike Dattani: when your browser communicates with stackexchange's server, there is no (direct) link between the two. There's a network. The classical crypto between these two endpoints does not need to be aware of the network. But when using QKD as currently commercialized, every intermediary point in the network needs to perform QKD, and needs to be trusted (and further needs a trusted courier or channel for setup). I reworked 1 to make this clear.
fgrieu avatar
ng flag
@kodlu: I added in (6.) a link to the page where the QRNG vendor lists its certifications. I give weight to the AIS-31 PTG.3 certificate (even though it is apparently no longer actively maintained, and I failed to locate the test report, only the [certificate](https://marketing.idquantique.com/acton/attachment/11868/f-0040/1/-/AIS31%20Test%20Report.pdf#page=2)) because it was supposed to validate the soundness of the system including health monitoring of the source and cryptographic postprocessing. Of course, this QRNG in no way does QKD; it's only a sound building block for QKD.
kelalaka avatar
in flag
@MaartenBodewes this video should be helpful. Splicing is not really hard, at least with such a tool. You will see that there is a loss on each slice.
Maarten Bodewes avatar
in flag
@kelalaka Which video would that be? Did you try and include a link in that comment?
kelalaka avatar
in flag
@MaartenBodewes sorry, here it is https://www.youtube.com/watch?v=ekzlonBS7d8
Score:1
cn flag

Just to interject a voice of sanity, can I tell you about Keith?

I have a Mini(Keith). He's little and a grand piano won't fit into the trunk. Neither will a small flock of sheep. He also has a wading depth of only 210 mm compared with the new Bronco's 600 mm. And the Frangivento can do > 200 mph. Keith doesn't go up hill.

Does Keith exist, or is he too impractical? He can only carry(encode) one sheep at a time. It seems not by this forum's standards. He's too slow and too small. Faster is better cryptographically it seems. It seems that member's members matter. We get this problem with cryptographers over and over and over. What is it that you want to say at 100 GBit/s? But they're not needed if a QKDN is bought off the shelf.

Yet. No one here can mathematically prove that TLS/AES is secure, can they? Go on, try. And will they still be in 50 years time? If we're flogging nuclear secrets to that country in the middle east, we use one time pads. And so does NATO. Perhaps they're all fools too.

Horse's for courses. I'm perfectly happy to transmit strategic material at 9600 baud with perfect informational secrecy. For all time. Ever. I have software that does just that. And what if they're only 100 km away?

The problem with this question isn't technical. That's been solved years ago. It's philosophical. And job preservation.

fgrieu avatar
ng flag
For 15 years, the French population did useful things with the [Minitel](https://en.wikipedia.org/wiki/Minitel), which sent keystrokes at 7.5 byte/s. Thus indeed the drawbacks of slowness are overrated, which is why it's a distant (3.) in my list. Showstoppers for QKD are: (1.) when running it on a network, edges are severely limited in length, and one has to trust each vertex crossed; (2) unless you trust voice over phone or similar for determing who the secure key has been distributed to, the time and effort to setup each link is that of sending a trusted courier; so why not use a large OTP?
Paul Uszak avatar
cn flag
@fgrieu But Minitel was impractical and couldn't be used at all. It was too slow (<100 MByte/s) and you had to trust the device manufacturer and Postes, Télégraphes et Téléphones. And the terminals were way too big consuming a lot of electricity in terms of nano Watts/byte. Comms applications must fit on smartphones. And it didn't use authenticated encryption which meant that the signal could be intercepted/forged. So not a good example. Or is it?
Geoffroy Couteau avatar
cn flag
So basically, you are saying: if you are so paranoid about security that even using AES feels too risky, and if you do absolutely not care about speed or efficiency, then you have a usecase for QKD. Sure, but that is not a "voice of sanity": that's just restating something that was already mentioned in the other answers, while forgetting to mention that you would have to be paranoid BUT still happy to rely on a strong trusted setup assumption (which is something I personally would find much more concerning than using AES, but as you say this is more philosophical than technical at this stage).
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.