The new age of quantum computing

Quantum encryption is the holy grail of truly secure communications. If and when quantum computing becomes a widespread reality, many public-key algorithms will become obsolete. This includes those whose security relies on one of three hard mathematical dilemmas: the integer factorization dilemma, the discrete logarithm dilemma or the elliptic-curve discrete logarithm dilemma.

It is important to note that all of these issues can be solved on a powerful quantum computer running Shor’s algorithm. Shor’s algorithm demonstrates that the integer factorization dilemma can be efficiently solved through this computing and is therefore in the complexity class BQP.

Proper symmetric algorithms, such as AES with large keys, do not have the same weaknesses that allow the dramatic brute forcing speedup promised by quantum computers, so the security of those systems should remain high. To break current cryptosystems, quantum computers must have between 500 and 2000 qubits (depending on the algorithm and key length). However, existing quantum computers that we know about only operate with less than 15 qubits at present, so there is no immediate worry.

How does it all work?

Quantum encryption works quite spectacularly as entangled photons interact via a Bell-state measurement so that the state of one member is teleported over arbitrary distances to the second member. This has been demonstrated in laboratory conditions but recently NASA’s Jet Propulsion Laboratory (JPL) in California demonstrated it working on a standard city fibre network where the quantum state of a photon was teleported over 3.7 miles. They used no repeaters and have made a large step towards a global quantum Internet.

What the JPL has worked on is quantum key distribution. This offers an information-theoretically secure solution to the key exchange problem, but there is also a wider discipline known as quantum cryptography which focuses on exploiting quantum mechanical properties to perform cryptographic tasks.

What about post-quantum?

It must be kept in mind that all known current quantum computers are too limited to attack any real cryptographic algorithm. Yet, cryptographers are creating new algorithms to prepare for a time when quantum computing does become a real threat.

The term ‘post-quantum cryptography’ refers to cryptographic algorithms that are believed to be secure against an attack by a quantum computer. Again, the dangers of quantum computing relate to the security of public key algorithms. Most symmetric cryptographic algorithms (symmetric ciphers and hash functions) are believed to be relatively secure against attacks by quantum computers.

The promise of post-quantum technologies

Currently, the most promising post-quantum cryptography research is focused on the following approaches: Lattice-based, Multivariate, hash-based, code-based, supersingular elliptic curve isogency cryptography and symmetric key quantum resistance. I’ve shared them with you below so you can understand how they work:

• Lattice-based cryptography includes cryptographic systems such as Learning with Errors. Schemes like NTRU encryption have shown promise. Yet, some cryptographers have called into question the security of some of the most efficient lattice-based schemes.
• Multivariate cryptography includes cryptographic systems which rely on error-correcting codes. A critical advantage of this signature system over hash-based signature systems is that each signature is short. Multivariate cryptography makes it possible to design signature schemes in which the verification of the signature is very fast. Still, many experts have declared hash-based cryptography (i.e. Lamport signatures and the Merkle signature) as a convincing argument for the existence of secure post-quantum public-key signature systems.
• For code-based cryptography, all cryptographic constructions rely on hard problems from the theory of error-correcting codes. The issue is that they require a large random looking binary matrix, so they are not the best candidate for the most memory constrained environments.
• Supersingular elliptic curve isogeny cryptography relies on the properties of supersingular elliptic curves to create a Diffie-Hellman replacement with forward secrecy. This solution offers forward secrecy, which is important in protecting against the compromise of long term keys through failures.
• And lastly, symmetric key quantum resistance focuses on using large key sizes. In fact, a characteristic of many post-quantum cryptography algorithms is that they require larger key sizes than commonly used classical public key algorithms.

Even with the cryptographic community’s increased focus on postquantum cryptography, more time is needed to improve its efficiency and usability. We may very well find that we do not actually need post-quantum cryptography, but that risk is perhaps too large to take and if we don’t conduct the research now, then we may lose years of critical research in this area.

Dr Kevin Curran is a senior member of the Institute of Electrical and Electronics Engineers (IEEE).