Does 'Quantum encryption' defend against a quantum computer?

May 18, 2016

Quantum computing research is receiving a huge boost from the European Union. Today a Dutch newspaper mentioned that KPN, a large Dutch telecom operator, is going to secure one of their main links using 'quantum encryption' to protect against attacks using such quantum computers. I doubt that is going to help much.

Quantum encryption actually is a misnomer. What is meant is quantum key distribution (QKD). QKD allows two parties to securely establish a secret session key. This session key is then used in a traditional symmetric key encryption scheme to secure the actual data transfer between the two endpoints.

This traditional method is vulnerable to a quantum computer attack using Grover's search. This attack allows an adversary to recover the key used to encrypt the message in a significantly fewer number of steps than a traditional brute force search. (If the key is n bits long, brute force search requires 2n steps while Grover's search requires only \sqrt{2^n}=2^{n/2} steps.) For equivalent levels of security, the session key must be twice as long (for example 512 bits instead of 256 bits).

Moreover, QKD requires the existence of an authenticated (put public) channel over which the two endpoints can verify whether an adversary tried to eavesdrop on the quantum key exchange. This authenticated channel does not magically exist: it must be implemented using traditional cryptography. Using public key cryptography, so that an endpoint only needs to know the public key of the other endpoint, would be a natural option. But this type of cryptography is extremely vulnerable to attacks with a quantum computer so this does not protect against an active quantum adversary. This means a method based on shared secrets needs to be used, which introduces a key distribution issue.

(Update: note that the theoretical papers on QKD assume that the established key is used as a one time pad, where one key bit is used to encrypt one message bit. In practice, QKD does not create key bits very fast due to the privacy amplification required to detect eavesdropping. Therefore, in practice the established key is used as a session key to encrypt all traffic for say 1 second using a symmetric cipher like AES.)

Finally, the real security of QKD really depends on the actual implementation of the key distribution protocol using some kind of quantum phenomenon, and attacks on these physical instances are known (see e.g. here and here). These type of attacks are quite similar to the side-channel attacks on implementations of classical cryptography.

In any case, this suggests a traditional method to exchange keys based on symmetric key cryptography but using larger keys than usual would offer a similar level of security.

(Update: In particular I wonder whether the following scheme wouldn't offer the same level of security, in software only, without relying on quantum effects. Assume the QKD protocol establishes a key of b bits. Now distribute two secrets, both b bits long, between both parties: a key k0 and a seed s. And assume a cryptographic hash function that maps ${0,1}^{2b} {0,1}^b$. Both parties use for time slot i key ki. To create the new key, both parties execute ki = h(ki − 1,s) and throw away the old key (but keep the seed). This solution assumes perfect synchronisation between parties, but this can be achieved by letting one party be the master that sends a special synchronisation command over the encrypted communication link.)

What will help is to invest in and apply post-quantum cryptography (PQCrypto), a line of research a few of my colleagues are involved in.

In case you spot any errors on this page, please notify me!
Or, leave a comment.