A new type of cryptography to withstand attacks from quantum computers?

Date:
Changed on 31/08/2020
Phong Nguyen, Director of Research at Inria Paris in the Cascade* project team, has been awarded an ERC Advanced Grant of €2.5 million. His project aims to secure cryptography using Euclidean networks to counter threats posed by quantum computers and to reconcile big data and privacy.

Phong Nguyen is a specialist in cryptography. This science of secrecy, demonstrated for example in the film Imitation game which recounts part of the life of mathematician Alan Turing, aims to protect against enemy attacks. Cryptography is one of the pillars of cybersecurity. It is used in numerous everyday objects such as WiFi, transport passes, mobile phones, game consoles, payment cards, electronic passports etc. Although this discipline dates back to the earliest forms of writing, it is constantly evolving alongside developments in means of communication such as the Internet revolution.

Phong Nguyen
Photo Coll. part.

 

I started my PhD in 1996", explains Phong Nguyen. “Two years earlier, the American mathematician Peter Shor had made an extraordinary discovery, demonstrating that a quantum computer could rapidly factor large integers, which would make it possible to crack the cryptography of electronic commerce."

Before this result, quantum computers were more of a curiosity, we didn't really know what they could be used for. At the time, building a quantum computer still seemed like science fiction, but this discovery led cryptographers to consider alternatives.

Euclidean network cryptography

Euclidean networks define a regular layout of points, like a checkerboard or a honeycomb. Network cryptography is based on the difficulty of solving geometric problems involving Euclidean networks with several thousand dimensions.

The first generation of this type of cryptography appeared in 1996. It aroused interest because it proved to be much faster than other cryptosystems, using number theory and boasting innovative security properties. “If this technology is now on the point of being released, it wasn’t at all on the agenda at the time. It takes time to assess the security of a system and build confidence”, continues Phong Nguyen.  

During my thesis, I showed that early network cryptosystems weren’t quite as secure as intended, and sometimes not even at all. I was doing crypto analysis: just as car manufacturers crash-test cars before bringing them to the market, crypto analysts devise the worst sorts of attacks to make sure a cryptosystem is reliable.

Today, cryptography based on Euclidean networks is much better understood and offers major advantages, namely its strength against quantum computers and its applications in big data.

Quantum computers: what threats do they pose?

The threats that quantum computers pose for cryptography are now taken very seriously. An international competition on the subject was launched by the NIST (National Institute of Standards and Technology), beginning in 2016. The aim is to standardise, by 2024, cryptographic algorithms able to withstand attacks by quantum computers if they become available. Euclidean networks are the most popular family of algorithms in the competition," observes Phong Nguyen.

What is a quantum computer?

A quantum computer is radically different from a standard computer in that it uses the principles of quantum mechanics, such as superposition and entanglement. This makes it highly complex to manufacture. Today, there are some small quantum computers such as the ones by Google and IBM, which are prototypes, but their computing power is very limited and it is not known whether they can be scaled up. For the moment, they do not pose a threat to cryptography even though they are already able to perform operations much faster than our best computers.

Many private and public actors in the United States, China and Europe are currently investing in quantum computing. But the scientific community is not sure what these new kinds of computers will be used for, what form they will take, or how to use them. “There's a lot of research and questioning. No one really knows what's going to happen: this is just the beginning!” Phong Nguyen adds enthusiastically.

This new form of cryptography could also meet another challenge: reconciling privacy and big data. Today's digital players, notably GAFA, collect large quantities of personal data from our phones and computers. “And they're exploiting them using artificial intelligence, which raises numerous questions about privacy, especially if the data is sensitive like health-related data. This is what led to the creation of the GDPR** in Europe."

We're looking for a compromise: protecting information while still allowing useful data processing, explains the researcher.

When data is encrypted, it cannot normally be exploited: it has to be decrypted, which makes it vulnerable. To solve this dilemma, cryptographers have invented a new type of encryption, known as homomorphic encryption, which makes it possible to handle encrypted data. This is one of the solutions used for electronic voting. The most powerful homomorphic encryption is provided by cryptography based on Euclidean networks, which is currently being standardized.

Configuring network cryptography

The project I am working on, which has been awarded an ERC Advanced Grant, consists in configuring new cryptography based on Euclidean networks in order to withstand attackers with exceptionally large computing capacities, those of today or tomorrow, such as future quantum computers.

ERC

ERC Winners of the Paris Center 

Find here the list of ERC winners in the project teams of the Inria centre in Paris.

“You have to choose the right parameters. If they are too big, the cryptography cannot be implemented due to the inferior performance of computers today; if they are too small, the security of the data is threatened. So you have to find the right balance while trying to predict the development of hardware and algorithms over the next few years, which is very difficult!"

The issue is at the crossroads between several disciplines, and Phong Nguyen will be working with specialists in different fields. His team will include experts in quantum computing such as Frédéric Magniez (CNRS) and Thomas Vidick (California Institute of Technology). Thanks to the ERC grant, the team will also be able to acquire powerful machines to test new algorithms.

ERC funding provides very good working conditions for 5 years," says the researcher. “This allows us to recruit and train the next generation, organise symposiums and invite or visit experts. It is also a form of recognition, a label, facilitating meetings with specialists in other fields who don’t know you."

Phong Nguyen's main interest in the research process is to "understand and learn".

With this project, I kind of feel like I'm back in school, and it's exciting. There's a lot of new information to take in and digest. 

Phong Nguyen: a few key dates

1999: obtained a PhD in the Computer Science Department of the École normale supérieure 

2000-2008: Researcher at the CNRS 

2007: Habilitation thesis from Université Paris 7 Denis Diderot

Since 2008: Senior Researcher at Inria, Cascade team.

2013-2015: European Director of the LIAMA Sino-European Laboratory and guest professor at Tsinghua University, China;

2015-2019: Director of the JFLI Franco-Japanese Computer Science Laboratory and guest professor at the University of Tokyo, Japan.

*Cascade: Conception and Analysis of Systems for the Confidentiality and Authentication of Data and Entities

**GDPR: the General Data Protection Regulation, which strengthens and unifies data protection for individuals within the European Union, entered into force in May 2018.

 

This project is funded by the European Research Council (ERC) as part of the Horizon 2020 program.