“Quantum computers are able to break even the most secure encryption algorithm.”
“Quantum computers could crack Bitcoin.”
“The quantum future may hold many unpleasant surprises.”

If you look through the web for some information about quantum computers, you will find different opinions and statements. Some of them are enthusiastic. And some of them are not very optimistic.

Indeed, a hypothetical sufficiently large quantum computer would be able to retrospectively decrypt, for example, any internet communication that was recorded today, and many types of information need to remain confidential for decades. Thus even the possibility of a future super-powerful quantum computer is something that we should be thinking about today.

The good news is that not all encryption will be broken in the quantum world: some algorithms that do not use factorization as their mathematical base will remain robust. Furthermore, only specific types of quantum computers are suitable for running the algorithms required to break encryption. Even if IBM manages to keep its fifty qubit prototype stable enough in a lab setting, this machine still has two orders of magnitude fewer qubits than are required to break the most commonly used encryption methods. Add to this that as the number of qubits grows, it becomes ever more challenging to keep the system stable.

The study of cryptographic primitives that remain secure even against quantum computers is called “post-quantum cryptography”. The methods of post-quantum cryptography have not been used in the past because they are less efficient than current public-key methods. Most of the proposed PQC algorithms have key lengths that are orders of magnitude larger than those of today’s algorithms. Another issue is that most proposed PQC algorithms currently have much higher CPU performance requirements. Thus post-quantum crypto is a complex area that is still actively being researched.

When quantum computers come, we will be ready for them. I hope so anyway.

21 November 2017