Freja Elbro: Quantum computers will break the world’s cyber security. Is there hope?

For many years, cryptology has enabled governments, companies and private people to participate in secure communication over insecure channels: the phone calls we make, when we pay with our credit card, when we send a confidential email, all these times we know that our information is safe because it is encrypted.

The security of these cryptosystems is based on one-way mathematical problems such as factoring integers or computing discrete logarithms. These problems are easy to solve in one direction, but hard in the other. For example, it is easy to multiply two large primes, but it is hard to find the two primes if you only have their product. Solving the problems in the hard direction would allow you to break the cryptosystems, but it would most likely take billions of years even for our current supercomputers.

Large quantum computers, however, can solve these kinds of problems easily, and thus break the cryptosystems in a matter of minutes. Luckily, big quantum computers do not exist yet. The biggest quantum computers in existence have only tens of something called quantum-bits. In order to break the current crypto systems, it would need thousands of quantum-bits.

Currently, many large companies and famous universities (IBM, Google, Microsoft, MIT) are working to build larger and larger quantum computers. Their technical improvements are so promising that it seems plausible that large quantum computers will be built outside laboratory environments in a foreseeable future. Once this happens, it will be possible to break most of the cryptosystems in use today.

The only way to keep our data protected is to study harder mathematical problems that even a quantum computer cannot easily solve: the term Quantum-Safe cryptography refers to systems that remain secure even in the presence of large quantum computers. There are systems today that will not be completely broken even with quantum computers, but there has been little focus on these systems in the past either because of their high computational cost or their high storage requirements.

Our project aims to generate knowledge on the impact of quantum computing on current crypto systems and on how to design crypto systems, which are robust against attacks using both conventional and quantum computers.

Research section: Cyber Security

Principal supervisor: Lars R. Knudsen

Co-supervisor: Søren Sennels

Title of project: Quantum-safe Cryptology

Project start: 01/02/2020 → 31/01/2023