Quantum Computers Will Not Be The End Of Public Key Encryption

The fact that quantum computers may one day easily crack modern public key encryption does not mean that encryption, or even public key encryption is doomed.  There are a range of alternatives which are "quantum resistant".  A report from the US National Institute of Standards and Technology (NIST) contained a table that prime facie does not bode well for the encryption in use today, and spells the end for public key encryption:

However, we already have several candidates at our disposal which look to be quantum resistant.  In public key encryption there are a number of complex problems which appear to be possible replacements for the one way functions at the heart of the likes of RSA and ECDSA.


These come from fields including:

• Subset-sum - known to many as the knapsack problem
• Subset-product
• Lattices
• Polynomials
• Combinatorial group theory
• Number fields

It is also worth pointing out that whilst RSA and ECDSA have gained popularity (and so they tend to be the schemes that are taught most often) they are not the only encryption schemes. We already have well understood schemes using many of the above mathematical fields such as:

• Buchmann-Williams Key Establishment
• The NTRU Cryptosystem
• The Goldreich-Goldwasser-Halevi Cryptosystem
• The Ajtai-Dwork Cryptosystem
• The McEliece Cryptosystem

We even have some analysis of the levels of quantum resistance of each of these crypto schemes. Not all look hopeful, and some have been all but dismissed as post quantum candidates.  However, some are showing considerable promise with NTRU and the McEliece schemes being particular favourites of mine.  In general, lattice based cryptography looks like the most likely to be the successor to the currently popular crypto schemes.

We have candidates but we need a lot more research to be convinced that the emerging candidates are truly quantum resistant. Plus we need to have practical implementations (software we can all use) that will bring such schemes into common use.  In short, we need investment in this area. Waiting for the problem to be upon us is not a viable option: we need to do the work now.

I would encourage anyone with an interest in information security to become familiar with quantum resistant cryptography as I suspect we will all see a migration towards such schemes in the foreseeable future.