A quantum computer is a special-purpose computer which uses the physics of quantum phenomena to calculate answers to certain specific types of problems significantly faster than a classical computer can.
A classical computer uses bits — each of which can be 1 or 0. If a classical computer wants to explore the 1 value *and* the 0 value, it has to use two hardware bits, or it has to use a single bit twice, which takes twice as much time as using the bit once.
A quantum computer can take advantage of the quantum properties of certain fundamental physical objects (for example, ions) to implement qubits. Qubits are sort of like bits, except that a qubit can be a 1 and a 0 at the same time. Because of this “superposed” nature of qubits, a quantum computer can explore the 1 value of the qubit and the 0 value at the same time. By using multiple qubits in each calculation, a quantum computer can thus speed up certain kinds of computations by a factor of two per bit (because it’s twice as fast as a classical computer per bit) — which means that quantum computers can achieve exponential speedup for some problems.
Quantum computers can’t do this for all types of computations; their potential speedup only applies to certain specific types of problems. Among the problems a quantum computer can solve significantly faster than a classical computer are:
· Simulations of physical systems which have quantum properties
· Searches
· Fourier transforms
The last bullet is what creates the risk of a “quantum apocalypse”. It turns out that for technical reasons, the problems today’s public-key cryptosystems are based on (factoring, calculating discrete logarithms, and solving elliptic curve equations) are only hard if you can’t compute Fourier transforms fast. When a large, error-corrected quantum computer is built, we’ll be able to calculate Fourier transforms exponentially faster than we can today, which means that we’ll be able to break public-key cryptosystems exponentially faster than we can today. When this happens, we’ll have to abandon today’s public-key cryptographic algorithms and move to new algorithms which can’t be solved efficiently by quantum computers. Luckily, the US National Institute of Standards and Technology (NIST) is already working on developing and standardizing such algorithms, which are known as “Post-Quantum Cryptographic Algorithms”.
The big question is “will Post-Quantum Cryptography be ready in time?”
The answer, of course, depends on how long it will take for a large quantum computer to be built. Lots of people currently believe that it will take 20 years or more for scientists and engineers to build a quantum computer powerful enough to break today’s most widely deployed Public-Key cryptographic algorithm — which is RSA-2048.
But that’s not necessarily good news. 20 years sounds like a long time — and it is — but it’s very likely that it will take 20 years or more to invent, test, standardize, implement, and deploy quantum-safe cryptography, and to decommission all the vulnerable systems that currently rely on today’s Public-Key algorithms. So the time to start working on replacing today’s Public-Key cryptographic infrastructure is now.
Of course, until NIST finishes selecting the new standard Post-Quantum cryptographic algorithms, you can’t start deploying them, so it’s logical to ask:
“What can I do right now to prepare for the Post-Quantum cryptographic future?”
Here are a few things you can do now:
1. Assign responsibility for quantum readiness to a named executive.
2. Create a quantum readiness roadmap with timelines.
3. Review the roadmap and status regularly with senior stakeholders.
4. Participate in industry sector activities and standards bodies focused on quantum readiness.
5. Plan and execute tabletop and simulation exercises for crypto algorithm failure response.
6. Ask your infrastructure and application providers and your third parties for their quantum readiness plans.
7. Hire or train staff to develop expertise in quantum computing and its applications.
Originally appeared on Medium
