Post Quantum Cryptography

Global Crypto Transition is Coming

Quantum computing strikes at the heart of the security of the global public key infrastructure (PKI). PKI establishes secure keys for bidirectional encrypted communications over an insecure network. PKI authenticates the identity of information senders and receivers as well as protecting data from manipulation. The two primary public key algorithms used in the global PKI are RSA and Elliptic Curve Cryptography. A quantum computer would easily break these algorithms.

The security of these algorithms is based on intractably hard mathematical problems in number theory.  However, they are only intractable for a classical computer where bits can have only one value (a 1 or a 0). In a quantum computer where k bits represent not one but 2^k values, RSA and Elliptic Curve cryptography can be solved in polynomial time using an algorithm called Shor’s algorithm. If quantum computers can scale to work on even tens of thousands of bits, today’s public key cryptography becomes immediately insecure.

Future Cryptography

Fortunately, there are cryptographically hard problems that are believed to be secure even from quantum attacks.  These crypto-systems are known as post-quantum or quantum-resistant cryptography. In recent years, post-quantum cryptography has received an increasing amount of attention in academic communities as well as from industry. Cryptographers have been designing new algorithms to provide quantum-safe security.

Proposed algorithms are based on a number of underlying hard problems widely believed to be resistant to attacks even with quantum computers. These fall into the following classes:

• Multivariate cryptography
• Hash-based cryptography
• Code-based cryptography
• Supersingular elliptic curve isogeny cryptography

Most post-quantum algorithms will require significantly larger key sizes than existing public key algorithms which may pose unanticipated issues such as compatibility with some protocols. Bandwidth will need to increase for key establishment and signatures. These larger key sizes also mean more storage inside a device.

On the Horizon of Quantum Computing

Quantum computing would have profound impact on science, transforming artificial intelligence and cryptography and many other areas. The challenges in building a quantum computer are immense but experts seem to agree they are no longer insurmountable. The race to build a scalable quantum computer is well underway.

Traditional computers rely on transistors that represent the smallest piece of information, a bit, which can be a zero or a one. In contrast, quantum computers represent information in qubits  which can be multiple states simultaneously. In quantum physics, subatomic particles can act like waves and enigmatically take on being a partical or a wave or a particle and a wave. This is known as superposition. As these states scale, exponential computing power is unleashed.

We need to begin planning today for a future with  quantum-safe security.