Quantum Key Distribution (QKD) and Quantum Cryptography (QC)
nsa.gov
nsa.gov
From the UK NCSC [1]:
> QKD does not provide authentication, nor do any other quantum techniques. Therefore, in practice, QKD must be combined with other cryptographic services to provide security against the threat from quantum computing, and therefore should not be relied on as a mechanism that provides substantial security value. [...] The NCSC will not support the use of QKD for government or military applications. PQC is the best mitigation to the threat to cryptography from quantum computers.
And the German BSI (and partners)[2]:
> Together with European partner agencies from France, the Netherlands and Sweden, the BSI has published a Position Paper on QKD. The paper concludes that QKD can only be used in niche use cases due to its technological limitations and that QKD is not yet sufficiently mature from a security perspective. Therefore, in light of the necessary migration to quantum-safe schemes, the clear priority should be the migration to post-quantum cryptography.
This is despite different choices for which PQC algorithms to use. E.g. NIST (and many others including the UK) have gone initially with ML-KEM for key exchange, while Germany/BSI have selected FrodoKEM and Classic McEliece.
[1] https://www.ncsc.gov.uk/paper/quantum-networking-technologie... [2] https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisati...
Here's an interesting related aside: the likely design of a practical quantum internet would make QKD totally trivial. What a quantum internet would do is deliver kinda-noisy entangled Bell pairs to endpoints that wanted to communicate. The endpoints would then purify [1] this kinda-noisy entanglement into actually-good entanglement (e.g. from 1% error to 0.0000000000001% error). The purified Bell pairs can then be consumed in order to transmit qubits [2]. However, because of the monogamy of entanglement [3], the purification process must detect and correct eavesdropping (or else fail to produce output). So, once you have a sufficiently purified Bell pair, it can be measured to get a bit that can be used as a one time pad. (That said, this does still assume you have an authenticated channel! Purification requires communication, because without authentication you can be man-in-the-middle'd.)
[1]: https://en.wikipedia.org/wiki/Entanglement_distillation
The key ingredient here is entanglement swapping [1]. Entanglement between routers A and B can be merged with entanglement between routers B and C to form entanglement between A and C. This accumulates noise, but purification can be used at each merging step to push the noise back down to 1%.
So what transmitting a message looks like is a path between the two endpoints is selected and then entanglement swapping+purification is used to turn 1-hop entanglement into 2-hop entanglement, then into 4-hop, then etc until the entire path is spanned. Then purification+teleportation are used by the endpoints to move the message.
This always bothers me a bit. QKD is on a very solid theoretical footing — if you have an authenticated classical communication channel and an actual quantum communication channel that sends actual qubits that are genuinely only in the basis you think they’re in, then it’s secure, full stop. It’s been proven for decades.
But this is hard (hint: a commercially useful quantum computer does not exist yet), so people fudge it with optical techniques that approximate, poorly, what is needed. And the result is not secure.
So if you're only interested in computational security that is post-quantum, why not pre-share a symmetric key for some AEAD scheme? You'll get forward secrecy with hash ratchet and neither provides future secrecy in principle.
Neither solves the bootstrap and QKD requires a really, really expensive and complex infrastructure just to provide perfect secrecy which we're fine without.
(BB84 is from 1984. The terminology was different, and the understanding of what mattered in cryptography was different.)
I don’t entirely agree. You can build a computationally secure authenticated channel using symmetric primitives (e.g. hashes) that are very, very likely to survive for a long time. And you can build comparably secure asymmetric authentication schemes from the same primitives (hash-based signatures are a thing).
But to build a classical key exchange system, you need more exotic primitives (Diffie-Hellman or public-key encryption / KEM schemes), and the primitives of this sort that are supposedly post-quantum secure have not been studied for nearly as long and have much more structure that might make them attackable.
Not to mention that attacking the authenticated channel in QKD cannot give a store-now-decrypt-later attack.
You absolutely do get forward secrecy with pre-shared keys. You just need to make the protocol derive the next key with a cryptographic hash function, and deliver the iteration count with the packet so the recipient knows which key is the correct one. This is called a SCMIP or hash ratchet, and it's used e.g. in Signal protocol.
(As implementation details, you'll also want to hash the hash ratchet counter with the key to prevent theoretical loops, and you'll probably want to encrypt the ratchet counter during delivery with static header key, or the very least authenticate it.)
1. BB84 key exchange requires an authenticated channel. typically you do this with a 2. Carter-Wegman MAC, which is information-theoretically secure, but requires shared randomness that cannot be reused.
Successful protocol execution refreshes randomness (you can net gain from it), so you can communicate back and forth continuously when everything is working. An MiTM who simulates a network failure though can expend some of your pre-shared randomness (without it being refreshed). If they do this enough, they can exhaust your shared randomness, and bring down the link until you exchange more shared randomness somehow out of band. if you want to maintain information theoretic security, this might involve e.g. a courier with a USB or whatever (or a carrier pigeon, who knows).
This is still "secure", but is also a significant issue any QKD (even "real" QKD) has that classical cryptography does not have, and has always made me question the "solid" story for QKD.
1. There is a strong anti-QKD bias on HN or, at least, a very vocal few who reliably heckle anyone who discusses it. I get shouted at if I even mention it, and will likely get shouted at for saying this.
2. Should you trust the NSA's recommendations? This is a valid question, now more than ever.
e.g. "Quantum key distribution requires special purpose equipment"
Yes, it requires special equipment. That hasn't deterred some from using it where the added expense is warranted. Commercial QKD systems have been in use for decades. The technology is not currently useful for credit card transactions from your living room, but that doesn't mean it has no applications.
"Since QKD is hardware-based it also lacks flexibility for upgrades or security patches."
This is like arguing that, because your internet connection runs on hardware, nothing can be done to upgrade it or fix security vulnerabilities. If your last-mile connection is copper, as it is for many, there have likely been massive upgrades to its bandwidth and security over the years in the form of changes to what's on either end of the copper. Fiber is the same way. A huge part of QKD protocols is software as well.
When I see points like these, I question the source. They appear to have an agenda, and they certainly have motive. Remember, this is an organization whose business has been spying on its own citizens for decades.
The big logical issue is that QKD requires a classically-authenticated channel, so you either need a post-quantum signature scheme (at which point why bother with QKD since you can usually use the same computational hardness assumptions to construct a post-quantum key exchange scheme & use AES-GCM or ChaCha20-Poly1305), or you need pre-shared symmetric key material & a Wegman-Carter MAC a la Poly1305 (at which point why bother since you can just use AES-GCM or ChaCha20-Poly1305).
If you hate the NSA that's fine. Nobody in the EU cried foul over the NSA's recommendations though (and the NIST-winning schemes are European). Chinese scholars submitted some fundamentally similar schemes, the Chinese Academy of Sciences have formally recommended lattice-based schemes. While the Chinese (government-run) standardization is only starting, it is a very good bet that they will use a lattice-based scheme.
So, unless you think all of the world's governments (again, including China) are in a massive cabal to allow the NSA specifically to spy on the entire world, #2 is not a particularly valid question.
Well, they should, if they want to be honest and mathematically rigorous.
For instance, in the case of NIST's proposed post quantum cryptography standard Kyber that relies on lattice based methods.
> and pre-quantum crypto is also vulnerable to yet discovered classical algorithms?
True, and also disconcerting; with the most reckless being allowing fungible currency reliant on such methods.
We should be working on standardising and moving towards methods that are independent of, rather than rely on, unresolved questions in mathematics.
1. provable constructions based on "hard" problems, and 2. best-effort cryptanalysis of "hard" problems.
This is true of lattice-based problems. It is true of EC crypto. It is true of RSA. it is true of McCliece. It is true of AES. That is the nature of things, and there is no avoiding that.
Analysis of Kyber was honest and mathematically rigorous. It's also beside the point, as all of your criticisms hold for EC/AES as well (despite EC having some reasonable lower bounds, e.g. in (extensions of the) generic group model. These of course rely on the conjecture that EC groups are generic groups).
> We should be working on standardising and moving towards methods that are independent of, rather than rely on, unresolved questions in mathematics.
There are no known methods that are remotely economically viable. There is (completely seriously) a clearer path towards fixing climate change than what you say. There is also a clearer path towards fixing global hunger. It is a complete fantasy to want to solely rely on mathematically provable techniques in cryptography, and not one that it is worth engaging with.
Furthermore, it's completely pointless. We might as well frame your question as
> We cannot prove that AES is hard, so we should not use it.
Why? It would be cool to prove that AES is hard. Sounds fun. And practically, the hardness assumptions of deployed cryptography are almost never the cause of a security vulnerability. If we care about secure systems, proving AES is hard is so low down on the priority list that it is difficult to think of something less important. Again, completely seriously, we would have MUCH more secure systems if we paid each person in the country to use better passwords.
Given that this is the case, it seems unreasonable to suggest spending \Omega(billions) updating our network infrastructure to worse-performing links just to "fix" a problem that doesn't exist. I'm even speaking as a cryptographer who (unreasonably) dislikes heuristics in the field, and tries to replace them with provable alternatives. It is a fun academic exercise. But it is not a real world issue.