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

Cryptography, the science of secrecy, is tackled, for example, in the film "Imitation game", which evokes part of the life of the mathematician Alan Turing. Its aim is to protect oneself against adversaries by protecting messages with keys. 

Phong Nguyen is a specialist in cryptography. Research Director at Inria in Paris within the Cascade* project-team, is the winner of an ERC Advanced Grant of 2.5 million euros. His project aims to secure cryptography based on Euclidean networks to counter the risks associated with quantum computers and reconcile big data and privacy.

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.

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 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. 

* 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.