Some 30 years after they were first mooted, quantum computers remain largely theoretical. Yet few people doubt they will one day become a reality. When they do, they will bring many benefits – greater speed and efficiency, for example – but they also pose a potentially seismic security threat.
Much of the encryption we rely on today for protection and authentication when we use bank cards, send emails and connect to secure websites could be breached overnight by these super-computers.
‘The encryption we have at the moment is secure – at least we hope so – but once quantum computers are built, the kinds of online cryptography applications we use today will be insecure – because they are relying on encryptions that quantum computers will be able to break,’ says Dr Christophe Petit, a Lecturer in Computer Security at the School of Computer Science.
Theoretical it may still be, but the drive towards quantum computing is gaining momentum. In December 2017, Microsoft unveiled a complete quantum development kit, while GCHQ has declared an interest in post-quantum cryptography. Earlier this year, Google announced a quantum processor that might one day form the cornerstone of a quantum computer.
This is why global computer experts and mathematicians are engaged in trying to head off the online security threat long before it happens by researching new mathematical techniques in order to come up with strong, post-quantum encryptions and signatures. ‘We need to plan ahead,’ stresses Christophe. ‘Even if we knew the threat wouldn’t come for another 20 years, we would be late in trying to address it now. And although quantum computers don’t exist at the moment, what was considered a theoretical threat is now seen as a plausible one in the not-too-distant future.’
Although it’s not known exactly what quantum computers will be capable of, scientists do know they will be better than conventional computers at factorisation: finding two unknown prime numbers that when multiplied together give a third, known number. This, then, is the starting point for researchers like Christophe, whose background is applied mathematics.
‘We’re still at the early stages, looking at the maths. A lot of work is being done on this across the world, such as at the National Institute of Standards and Technology is the US. There are a lot of people looking at new algorithms.’
Christophe, a member of the University’s Security and Privacy research group, is one of them. His recent paper ‘Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems’, written with Steven Galbraith and Javier Silva, received the Best Paper Award at the 23rd International Conference on the Theory and Applications of Cryptology and Information Security in Hong Kong (ASIACRYPT 2017) last December, and has also been named Paper of the Month by the College of Engineering and Physical Sciences.
‘Online security goals are confidentiality and authentication, and these can be achieved using cryptography building blocks called encryption schemes and signature schemes. Our paper is on signatures for post-quantum security.’
The cryptography that’s been used for the past 20-30 years to ensure online security, such as RSA – one of the first public-key cryptography systems, which is widely used for secure data transmission – relies on mathematical problems that can’t easily be solved. ‘Essentially, the way we “prove” security is that we build a theorem that says, “if you can break my system, then you can also solve this mathematical problem’, explains Christophe. ‘That’s the basis of the RSA crypto system. If you can solve this problem, then RSA is dead. And quantum computers will be able to do that.’
There are three problems that our cryptography applications rely on today: factorisation, discrete logarithm problem and elliptic curve discrete logarithm problem. The three of them will be broken with quantum computers. So, the first step to addressing this is to replace the mathematical problem with another, hopefully harder one.
There are five leading approaches for post-quantum cryptography – lattice-based, code-based, multivariate, isogeny-based and hash-based – all of which have different features, with some allowing things others don’t. Isogeny, which Christophe’s paper is focuses on, is relatively new, but is becoming more popular.
‘Isogeny-based cryptography relies on mathematical problems that have been studied for 20 years, yet no one would know how to solve them even if quantum computers existed already. In the paper we propose a new signature scheme and we prove that this scheme is secure unless someone manages to solve the mathematical problem.
‘There’s still a lot of research to do, and we have submitted a research proposal to develop this further. There’s a real opportunity here, but it’s also very much what I like doing: it’s really nice maths.’