Professor Alan Woodward and Professor Bill Buchanan have outlined their ideas on the effect the Quantum Computers will have on public key encryption:
The abstract is:
The emergence of practical quantum computers poses a significant threat
to the most popular public key cryptographic schemes in current use.
While we know that the well-understood algorithms for factoring large
composites and solving the discrete logarithm problem run at best in
superpolynomial time on conventional computers, new, less well
understood algorithms run in polynomial time on certain quantum computer
architectures. Many appear to be heralding this next step in computing
as ‘the end of public key encryption’. We argue that this is not the
case and that there are many fields of mathematics that can be used for
creating ‘quantum resistant’ cryptographic schemes.
We present a high-level review of the threat posed by quantum computers, using RSA and Shor’s algorithm as an example but we explain why we feel that the range of quantum algorithms that pose a threat to public key encryption schemes is likely to be limited in future. We discuss some of the other schemes that we believe could form the basis for public key encryption schemes, some of which could enter widespread use in the very near future, and indicate why some are more likely to be adopted.