13
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Sanchayan Dutta May 15 at 14:16
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Sanchayan Dutta May 15 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.