Advantage of quantum key distribution over post-quantum cryptography

Question

Post-quantum cryptography like lattice-based cryptography is designed to be secure even if quantum computers are available. It resembles currently employed encryptions, but is based on problems which are most likely not efficiently solvable by a quantum computer.

Obviously research on quantum key distribution (QKD) continues. But what exactly are advantages of quantum key distribution over post-quantum cryptography?

The development of a new technology like QKD can have great side effects, and maybe QKD will be more cost-efficient or faster in the very long term, but I doubt that this is the main reason.

Answer 1

If it is proven that a given asymmetric encryption protocol relies on a problem which cannot be solved efficiently even by a quantum computer, then quantum cryptography becomes largely irrelevant.

The point is that, as of today, no one was able to do this. Indeed, such a result would be a serious breakthrough, as it would prove the existence of $\text{NP}$ problems which are not efficiently solvable on a quantum computer (while this is generally believed to be the case, it is still unknown whether there are problems in $\text{NP}\!\setminus\!\text{BQP}$).

Generally speaking, all classical asymmetric encryption protocols are safe under the assumption that a given problem is hard to solve, but in no case, to my knowledge, it has been proven (in the computational complexity sense) that that problem is indeed exponentially hard to solve with a quantum computer (and for many not even that the problem is not efficiently solvable with a classical computer).

I think this is nicely explained by Bernstein in his review of post-quantum cryptography (Link). Quoting from the first section in the above, where he just talked about a number of classical encryption protocols:

Is there a better attack on these systems? Perhaps. This is a familiar risk in cryptography. This is why the community invests huge amounts of time and energy in cryptanalysis. Sometimes cryptanalysts find a devastating attack, demonstrating that a system is useless for cryptography; for example, every usable choice of parameters for the Merkle–Hellman knapsack public-key encryption system is easily breakable. Sometimes cryptanalysts find attacks that are not so devastating but that force larger key sizes. Sometimes cryptanalysts study systems for years without finding any improved attacks, and the cryptographic community begins to build confidence that the best possible attack has been found—or at least that real-world attackers will not be able to come up with anything better.

On the other hand, the security of QKD does, ideally, not rely on conjectures (or, as it is often put, QKD protocols provide in principle information-theoretic security). If the two parties share a secure key, then the communication channel is unconditionally secure, and QKD provides an unconditionally secure way for them to exchange such a key (of course, still under the assumption of quantum mechanics being right). In Section 4 of the above-mentioned review, the author presents a direct (if possibly somewhat biased) comparison of QKD vs Post-Quantum cryptography. It is important to note that of course "unconditional security" is here to be meant in the information-theoretic sense, while in the real world there may be more important security aspects to consider. It is also to be noted that the real-world security and practicality of QKD is not believed to be factual by some (see e.g. Bernstein here and the related discussion on QKD on crypto.SE), and that the information-theoretic security of QKD protocols is only true if they are properly followed, which in particular means that the shared key has to be used as a one-time pad.

Finally, in reality, also many QKD protocols may be broken. The reason is that experimental imperfection of specific implementations can be exploited to break the protocol (see e.g. 1505.05303, and pag.6 of npjqi201625). It is still possible to ensure the security against such attacks using device-independent QKD protocols, whose security relies on Bell's inequalities violations and can be proven to not depend on the implementation details. The catch is that these protocols are even harder to implement than regular QKD.

Answer 2

Quantum key distribution requires that you wholesale replace your entire communications infrastructure built out of 5 EUR ethernet cables and 0.50 EUR CPUs by multimillion-euro dedicated fiber links and specialized computers that actually just do classical secret-key cryptography anyway.

Plus you have to authenticate the shared secret keys you negotiate with quantum key distribution, which you will probably do using classical public-key cryptography unless you're rich enough to afford couriers with suitcases handcuffed to their wrists.

More details from François Grieu on crypto.se about what makes quantum cryptography secure.

The crux of the technical difference—costs and deployability and politics and class divisions aside—is that the physical protocol of a QKD system is intended to be designed so that it need not leave a physical trace that future mathematical breakthroughs could enable to retroactively recover the shared secret negotiated over these dedicated fiber links. In contrast, with classical cryptography, public-key key agreements over the internet, where an eavesdropper records every bit over the wire, could in principle be broken by future mathematical breakthroughs.

Then, in both cases, the peers use the shared secret they negotiated, whether with quantum key distribution or with classical public-key key agreement, as a secret key for classical secret-key cryptography, which could in principle be broken by future mathematical breakthroughs. (But very smart well-funded people haven't made those breakthroughs after trying for decades.) And this doesn't mean that practical implementations of QKD won't leave physical traces either.

All that said, QKD is quantum, so it is sexy and makes a good sell to rich governments and banks, who have multimillion-euro discretionary funds for useless toys like QKD. The physics is also pretty cool for nerds to play with.

M. Stern calls to mind another advantage of QKD: It operates at the link layer, negotiating a secret key shared by the two endpoints of a fiber link—which might be one legitimate user and the MITM who spliced into that fiber link with a rogue QKD device. If, in the era of quantum supremacy, we replaced all the world's classical public-key key agreement by QKD, then where applications currently negotiate secret keys with their peer across the internet for end-to-end authenticated encryption over any routable medium, they would instead have to negotiate secret keys with their ISP, who would negotiate secrets with their upstream ISP, and so on, for hop-by-hop authenticated encryption. This would be a boon for the good guys in major world governments trying to (retroactively) monitor user communications to root out terrorists and activists and journalists and other inconvenient elements of society, because the ISPs would then necessarily have the secret keys ready to turn over to the police.

Answer 3

Comparison between classical forward secrecy and QKD

As mentioned by others, we don't have any provably safe post quantum public key algorithm, just like we don't have any provably safe public key algorithm in a world where quantum computers don't exist (only ones that are provably broken by quantum computers).

Of course, things are even riskier for quantum computers, since everything is newer, and therefore we don't have the "people have tried to break it for several years" argument, e.g. Rainbow from the NIST competition was recently was broken on the 3rd round on a classical computer.

But from a purely mathematical point of view, the answer is very similar to the "QKD vs classical public key cryptography?" question, which I shall analyze next.

What does QKD give you and what are its requirements?

First, just to make sure that I'm not wrong about it/so that we are on the same page, I'll state the hypothesis:

• what you need:

  • a custom quantum channel in addition to the classical channel, e.g. linking up two points with specialized hardware via optic fiber

  • a pre-shared key, i.e. one securely shared common secret,e.g. by driving over in a car with a USB. This is used to sign messages on the classical channel.

    Without this, you could get man-in-the-middle'd exactly as you could by an attacker that splices your classical + quantum channel and fakes the key generation for both sides.

• what you get: you can now generate common secrets in a way that simply cannot be snooped according the known laws of physics without you noticing it.

  If someone tries to snoop, you will be able to notice it every time, and therefore abort the communication without compromising your information.

  The rate of generation of the common secret may be limited. Wikipedia reports speeds of kbit/s to Mbit/s range.

  Every time you want to setup a new secret, communication over the classical channel is necessary. If someone were to steal your pre-shared key, they can perform man in the middle for any new key generation.

What you could do with a pre-shared key classically?

As we've mentioned on the previous section, a pre-shared key is a requirement for QKD.

Note however that is not a a problem exclusive to QKD: if you assume that the attacker can always man in the middle you (i.e. read and alter any encrypted message on the wire), then you also need a pre-shared key in classic cryptography for authentication. In both cases, given a shared key you don't need public key signature: we can instead just do something like sending (message + secret + sequence number + hash of the previous string), schemes like these are called message authentication codes.

So now let's review what you could do with such a pre-shared key classically, before we finally compare with the advantage of QKD:

• option 0) use it as a one time pad

  • upside: provably secure encryption
  • downside:
    • you can only encrypt one bit per secret bit as you can't reuse the one time pad bits. So that is generally too restrictive
    • no forward secrecy, i.e. if someone ever obtains the key, they crack all messages they ever intercepted.

• option 1) just the secret directly as the password of a symmetric encryption like AES.

  • upside:
    • we can reuse the password as many times as we want, thus solving the bit limit of option 0
    • it is not looking like quantum computers will break symmetric encryption so far
  • downside: no forward secrecy

• option 2) if you want forward secrecy (you do!), you could just use a classical forward secrecy protocol with the pre-shared key:

  • use the shared key only to sign/authenticate messages and prevent MITM, not to encrypt
  • whenever you are going to send a new message, first setup a new shared secret in memory using public key cryptography like RSA. Prevent MITM by signing this communication with the secure common secret.

  This gives:

  • upside:

    • if any intermediate encryption key is captured (unlikely since was only in memory, and used for a short period of time), the attacker can decrypt only one message
    • if the pre-shared key is captured, the attacker still cannot decrypt messages that were sent up until that point, as these were encrypted

  • downside:

    • if the pre-shared key is captured and we don't notice, future communications are susceptible to man in the middle
    • you have to rely on public key cryptography, of which we are less certain about quantum computer resistance than symmetric encryption

QKD vs the classical options

Finally, we can see how QKD solves one of the problems of option 2:

• if the key generation rate is high enough we can have perfect one-time pad encryption with the shared key.

  Otherwise, we can just use it as a password for symmetric encryption to encrypt a larger message.

  But in any case, we don't need public key cryptography, and so we feel more safe against yet undiscovered future quantum computer attacks, since it doesn't seem that quantum computers will break symmetric encryption.

However, we still have the second problem of option 2):

• if the pre-shared key is captured without us noticing we can get man in the middle'd starting from the next key generation phase.

Besides that, the downside of QKD is cost, as we need a new type of hardware for the quantum channel. If longer distances are reached however, it is not unimaginable that these costs may be justified for certain applications, like communication between governmental entities like embassies and intelligence services. Or perhaps in telecom backbones.