Warning message

Log in to add comments.

Post Quantum Cryptography

Huzaifa Sidhpurwala published on 2017-07-26T13:30:00+00:00, last updated 2017-07-26T13:50:02+00:00

Traditional computers are binary digital electronic devices based on transistors. They store information encoded in the form of binary digits each of which could be either 0 or 1. Quantum computers, in contrast, use quantum bits or qubits to store information either as 0, 1 or even both at the same time. Quantum mechanical phenomenons such as entanglement and tunnelling allow these quantum computers to handle a large number of states at the same time.

Quantum computers are probabilistic rather than deterministic. Large-scale quantum computers would theoretically be able to solve certain problems much quicker than any classical computers that use even the best currently known algorithms. Quantum computers may be able to efficiently solve problems which are not practically feasible to solve on classical computers. Practical quantum computers will have serious implications on existing cryptographic primitives.

Most cryptographic protocols are made of two main parts, the key negotiation algorithm which is used to establish a secure channel and the symmetric or bulk encryption cipher, which is used to do the actual protection of the channel via encryption/decryption between the client and the server.

The SSL/TLS protocol uses RSA, Diffie-Hellman (DH) or Elliptic Curve Diffie-Hellman (ECDH) primitives for the key exchange algorithm. These primitives are based on hard mathematical problems which are easy to solve when the private key is known, but computationally intensive without it. For example, RSA is based on the fact that when given a product of two large prime numbers, factorizing the product (which is the public key) is computationally intensive. By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find the public key factors. This ability could allow a quantum computer to decrypt many of the cryptographic systems in use today. Similarly, DH and ECDH key exchanges could all be broken very easily using sufficiently large quantum computers.

For symmetric ciphers, the story is slightly different. It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm with key length of n bits by brute force requires time equal to roughly 2^(n/2) invocations of the underlying cryptographic algorithm, compared with roughly 2^n in the classical case, meaning that the strength of symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search. Therefore the situation with symmetric ciphers is stronger than the one with public key crypto systems.

Hashes are also affected in the same way symmetric algorithms are: Grover's algorithm requires twice the hash size (as compared to the current safe values) for the same cryptographic security.

Therefore, we need new algorithms which are resistant to quantum computations. Currently there are 5 proposals, which are under study:

Lattice-based cryptography

A lattice is the symmetry group of discrete translational symmetry in n directions. This approach includes cryptographic systems such as Learning with Errors, Ring-Learning with Errors (Ring-LWE), the Ring Learning with Errors Key Exchange and the Ring Learning with Errors Signature. Some of these schemes (like NTRU encryption) have been studied for many years without any known feasible attack vectors and hold great promise. On the other hand, there is no supporting proof of security for NTRU against quantum computers.

Lattice is interesting because it allows the use of traditional short key sizes to provide the same level of security. No short key system has a proof of hardness (long key versions do). The possibility exists that a quantum algorithm could solve the lattice problem, and the short key systems may be the most vulnerable.

Multivariate cryptography

Multivariate cryptography includes cryptographic systems such as the Rainbow scheme which is based on the difficulty of solving systems of multivariate equations. Multivariate signature schemes like Rainbow could provide the basis for a quantum secure digital signature, though various attempts to build secure multivariate equation encryption schemes have failed.

Several practical key size versions have been proposed and broken. EU has standardized on a few; unfortunately those have all been broken (classically).

Hash-based cryptography

Hash based digital signatures were invented in the late 1970s by Ralph Merkle and have been studied ever since as an interesting alternative to number theoretic digital signatures like RSA and DSA. The primary drawback for any Hash based public key is a limit on the number of signatures that can be signed using the corresponding set of private keys. This fact reduced interest in these signatures until interest was revived due to the desire for cryptography to resist attack by quantum computers. Schemes that allow an unlimited number of signatures (called 'stateless') have now been proposed.

Hash based systems are provably secure as long as hashes are not invertible. The primary issue with hash based systems is the signature sizes (quite large). They also only provide signatures, not key exchange.

Code-based cryptography

Code-based cryptography includes cryptographic systems which rely on error-correcting codes. The original McEliece signature using random Goppa codes has withstood scrutiny for over 30 years. The Post Quantum Cryptography Study Group sponsored by the European Commission has recommended the McEliece public key encryption system as a candidate for long term protection against attacks by quantum computers. The downside, however, is that code based cryptography has large key sizes.

Supersingular elliptic curve isogeny cryptography

This cryptographic system relies on the properties of supersingular elliptic curves to create a Diffie-Hellman replacement with forward secrecy. Because it works much like existing Diffie-Hellman implementations, it offers forward secrecy which is viewed as important both to prevent mass surveillance by governments but also to protect against the compromise of long term keys through failures.


Since this is a dynamic field with cycles of algorithms being defined and broken, there are no standardized solutions. NIST's crypto competition provides a good chance to develop new primitives to power software for the next decades. However it is important to mention here that Google Chrome, for some time, has implemented the NewHope algorithm which is a part of Ring Learning-with-Errors (RLWE) family. This experiment has currently concluded.

In conclusion, which Post-Quantum cryptographic scheme will be accepted will ultimately depend on how fast quantum computers become viable and made available at minimum to state agencies if not the general public.

About The Author

huzaifas@redhat.com's picture

Huzaifa Sidhpurwala

Huzaifa Sidhpurwala is a Principal Product Security Engineer working for the Red Hat Product Security Team.