3 ms·

Quantum Key Distribution (QKD) and Quantum Cryptography (QC)

49 points by mooreds 6mo ago

bem94 6mo ago
All national agencies I'm aware of do not support QKD except in "very specific cases" and instead recommend Post-Quantum Cryptography (PQC). 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-technologies https://www.ncsc.gov.uk/paper/quantum-networking-technologie... [2] https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisationen/Informationen-und-Empfehlungen/Quantentechnologien-und-Post-Quanten-Kryptografie/Quantenkryptografie/quantenkryptografie.html https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisati...
Strilanc 6mo ago
The recommendation is to not use QKD. This is the correct recommendation. QKD solves key agreement if you have an authenticated line. But authentication is the harder more crucial problem. 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 https://en.wikipedia.org/wiki/Entanglement_distillation [2]: https://en.wikipedia.org/wiki/Quantum_teleportation https://en.wikipedia.org/wiki/Quantum_teleportation [3]: https://en.wikipedia.org/wiki/Monogamy_of_entanglement https://en.wikipedia.org/wiki/Monogamy_of_entanglement
- SAI_Peregrinus 6mo ago
  Of course that also means you need a mesh network topology (every node needs a direct link to the node it wants to share qubits with), so a quantum internet (interconnected network of networks) is impossible.
  - Strilanc 6mo ago
    That is not true. A spanning tree of physical links is sufficient to make a network where anyone can talk to anyone else. 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. [1]: https://en.wikipedia.org/wiki/Entanglement_swapping https://en.wikipedia.org/wiki/Entanglement_swapping
er4hn 6mo ago
This page came about because of how long it took PQC to get standardized. This was a slow enough process that a whole slew of QKD vendors arose and sold a lot of products promising this as a solution to dealing with quantum computers and harvest now decrypt later attacks. Many of those products did not do a great job at actually preventing listening in on their lines since QKD is an ongoing field of research where new issues are routinely being discovered.
- amluto 6mo ago
  > QKD is an ongoing field of research where new issues are routinely being discovered. 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.
  - maqp 6mo ago
    QKD is interesting from the PoV of perfect secrecy. But AFAIK with e.g. BB84, the basis orientation communication (used to detect OTP delivery eavesdropping) is done with Wegman-Carter (unconditionally secure) authentication using... a pre-shared key. 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.
    - amluto 6mo ago
      In my opinion, QKD (implemented correctly) performs key exchange, basically like Diffie-Hellman except that it’s secure even against an adversary with unlimited computing power. If I had a quantum computer and a quantum network anyway, may I’d use it, but probably not with Wegman-Carter. If not, I wouldn’t. (BB84 is from 1984. The terminology was different, and the understanding of what mattered in cryptography was different.)
misguidedpqc 6mo ago
Basing modern cryptography on unsolved mathematics where one can say "this algorithm is resistant to quantum computers, but may still, though we BELIEVE unlikely, be vulnerable to a yet discovered classical algorithm" is dangerous.
- mswphd 6mo ago
  that's not what people say? and pre-quantum crypto is also vulnerable to yet discovered classical algorithms?
  - misguidedpqc 6mo ago
    > that's not what people say? 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.
    - mswphd 6mo ago
      you cannot be mathematically rigorous with computational lower bounds. It is not possible with current mathematics. No ones that are relevant to cryptography exist, so any computational cryptography must separate into 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.
beloch 6mo ago
Two points: 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.
- pyinstallwoes 6mo ago
  You don’t have to trust the recommendations, you can analyze the reasoning behind their decisions and argue that. In this case the risk being at the engineering and hardware side and also denial of service. In addition to the trusted relays. Those are valid disputes.
  - beloch 6mo ago
    You can argue these exhaustively. They have not done that here. Some of their arguments are complete bunk. 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.
    - SAI_Peregrinus 6mo ago
      The big hardware issue is that QKD requires point-to-point links between the endpoints that authenticate to one another. That doesn't scale well to more than a handful of endpoints. Even if the endpoint hardware is free. 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).

49 points by mooreds 6mo ago

bem94 6mo ago

All national agencies I'm aware of do not support QKD except in "very specific cases" and instead recommend Post-Quantum Cryptography (PQC). 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-technologies https://www.ncsc.gov.uk/paper/quantum-networking-technologie... [2] https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisationen/Informationen-und-Empfehlungen/Quantentechnologien-und-Post-Quanten-Kryptografie/Quantenkryptografie/quantenkryptografie.html https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisati...

Strilanc 6mo ago

The recommendation is to not use QKD. This is the correct recommendation. QKD solves key agreement if you have an authenticated line. But authentication is the harder more crucial problem. 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 https://en.wikipedia.org/wiki/Entanglement_distillation [2]: https://en.wikipedia.org/wiki/Quantum_teleportation https://en.wikipedia.org/wiki/Quantum_teleportation [3]: https://en.wikipedia.org/wiki/Monogamy_of_entanglement https://en.wikipedia.org/wiki/Monogamy_of_entanglement

SAI_Peregrinus 6mo ago
Of course that also means you need a mesh network topology (every node needs a direct link to the node it wants to share qubits with), so a quantum internet (interconnected network of networks) is impossible.
- Strilanc 6mo ago
  That is not true. A spanning tree of physical links is sufficient to make a network where anyone can talk to anyone else. 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. [1]: https://en.wikipedia.org/wiki/Entanglement_swapping https://en.wikipedia.org/wiki/Entanglement_swapping

er4hn 6mo ago

This page came about because of how long it took PQC to get standardized. This was a slow enough process that a whole slew of QKD vendors arose and sold a lot of products promising this as a solution to dealing with quantum computers and harvest now decrypt later attacks. Many of those products did not do a great job at actually preventing listening in on their lines since QKD is an ongoing field of research where new issues are routinely being discovered.

amluto 6mo ago
> QKD is an ongoing field of research where new issues are routinely being discovered. 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.
- maqp 6mo ago
  QKD is interesting from the PoV of perfect secrecy. But AFAIK with e.g. BB84, the basis orientation communication (used to detect OTP delivery eavesdropping) is done with Wegman-Carter (unconditionally secure) authentication using... a pre-shared key. 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.
  - amluto 6mo ago
    In my opinion, QKD (implemented correctly) performs key exchange, basically like Diffie-Hellman except that it’s secure even against an adversary with unlimited computing power. If I had a quantum computer and a quantum network anyway, may I’d use it, but probably not with Wegman-Carter. If not, I wouldn’t. (BB84 is from 1984. The terminology was different, and the understanding of what mattered in cryptography was different.)

misguidedpqc 6mo ago

Basing modern cryptography on unsolved mathematics where one can say "this algorithm is resistant to quantum computers, but may still, though we BELIEVE unlikely, be vulnerable to a yet discovered classical algorithm" is dangerous.

mswphd 6mo ago
that's not what people say? and pre-quantum crypto is also vulnerable to yet discovered classical algorithms?
- misguidedpqc 6mo ago
  > that's not what people say? 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.
  - mswphd 6mo ago
    you cannot be mathematically rigorous with computational lower bounds. It is not possible with current mathematics. No ones that are relevant to cryptography exist, so any computational cryptography must separate into 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.

beloch 6mo ago

Two points: 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.

pyinstallwoes 6mo ago
You don’t have to trust the recommendations, you can analyze the reasoning behind their decisions and argue that. In this case the risk being at the engineering and hardware side and also denial of service. In addition to the trusted relays. Those are valid disputes.
- beloch 6mo ago
  You can argue these exhaustively. They have not done that here. Some of their arguments are complete bunk. 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.
  - SAI_Peregrinus 6mo ago
    The big hardware issue is that QKD requires point-to-point links between the endpoints that authenticate to one another. That doesn't scale well to more than a handful of endpoints. Even if the endpoint hardware is free. 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).