Will quantum computers be the end of public key encryption?

Buchanan, William; Woodward, Alan

Abstract

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.

• Journal Article Type: Article
• Acceptance Date: Aug 17, 2016
• Online Publication Date: Sep 20, 2016
• Publication Date: Sep 20, 2016
• Deposit Date: Nov 22, 2016
• Publicly Available Date: Mar 22, 2018
• Journal: Journal of Cyber Security Technology
• Print ISSN: 2374-2917
• Electronic ISSN: 2374-2925
• Publisher: Taylor & Francis
• Peer Reviewed: Peer Reviewed
• Volume: 1
• Issue: 1
• Pages: 1-22
• DOI: https://doi.org/10.1080/23742917.2016.1226650
• Keywords: Post-quantum cryptography, Shor’s algorithm, hidden subset problem
• Public URL: http://researchrepository.napier.ac.uk/Output/426508
• Contract Date: Mar 22, 2018