Maria Naya-Plasencia: fighting to protect digital security

What will hackers be capable of with quantum computers? What new types of attack will be possible and how can we prepare for them? These are questions which Maria Naya-Plasencia, Director of Research within the Inria project team Cosmiq - formerly Secret - seeks to answer in her daily work. “We may not yet have a large-scale quantum computer. But we need to start preparing for new, much more powerful types of attack if we want to be able to see them off in good time.” This is true not only for the digital security of our future data, but for our current data as well, which will also come under threat with the arrival of these super-powered computers.

There are two processes for keeping data secure: symmetric cryptography and asymmetric cryptography. “With symmetric cryptography, users employ the same key to encrypt and decipher information”, explains the researcher. “This means sharing a secret key in advance. This is the oldest, quickest and most effective cryptography system.” With asymmetric cryptography, meanwhile, users have two different keys - one to encrypt a message, and another to decipher it, - meaning there is no need to share keys in advance, but this method is slower and less secure. In practice, these two cryptosystems co-exist alongside each other.

But not all researchers in post-quantum cryptography are moving in step with each other. A great deal of research has gone into asymmetric cryptography, as evidenced by the competition launched in 2017 by the NIST, the US National Institute of Standards and Technology. This is aimed at finding new encryption systems - or primitives - with the capability to withstand quantum attacks. The reason for this is simple: the mathematical problems which the majority of these “asymmetric primitives” are based on are vulnerable to the processing power of quantum computers.

In 1994 Shor's Algorithm, a famous quantum attack algorithm, demonstrated the limits of the majority of contemporary asymmetric cryptosystems when faced with a quantum attacker. It was at this point that the IT community decided to take action. The situation with symmetric cryptography, meanwhile, was less clear. The discovery of Grover’s Algorithm in 1996 had implied that doubling the size of keys would be enough to arrive at the current level of security found in standard computing. But was this really the case? Further research was needed in order to find out.

This was something which Maria Naya-Plasencia, a specialist in symmetric cryptography and winner of an ERC Starting Grant (open to young researchers), achieved in 2017 through her research project QUASYModo. “Our strengths lay in being able to bring together specialists in cryptography and quantum computing within the same research space”, she explains. Their objectives were twofold: testing the vulnerability of current “symmetric encryption primitives” when faced with a quantum attacker and, where possible, devising solutions with the capacity to make them more robust.

“We began by working on an open problem: seeking out effective quantum “collisions” within a function.” This problem has a particular impact on the resistance of “hash functions”, which are widely used in digital signatures and for storing passwords. These functions are used to ensure that a unique digital signature corresponds to a given file (or password), with the exception of so-called “collision” attacks, in which two files can generate the same digital signature.  The researchers knew that such attacks would be possible, in some cases, with a large quantum memory. But for more realistic scenarios, there remained a significant amount of uncertainty.

The QUASYModo project team sought to tackle this problem by developing a small quantum memory. Their research was the first to show that it was possible to “break” certain traditional cryptographic constructions using a limited quantum memory. The solution the researchers came up with was to increase the size of “encryption primitives”, including through the use of the Saturnin suite of primitives.

Other research results are anticipated prior to the end of the QUASYModo project, which has been pushed back to September 2023 as a result of the pandemic. Maria Naya-Plasencia is pleased with what they have achieved: “Our research, like others, has underlined the importance and the potential of this field of research, encouraging a number of specialists to focus on these problems. We have developed partnerships, most notably with NTT, a Japanese telecommunications company - with whom we were the first to develop more realistic quantum attacks, with ‘Simon’s Algorithm’ - but also with academic partners from Austria, Germany and the Netherlands.” 

The researcher is keen to stress the vital role played by this research: “It's really important to have independent and extensive academic research with the capacity to test the vulnerability of encryption systems and to make recommendations users can trust.” The challenge is to provide digital security for all, from companies and politicians to citizens.

• María Naya-Plasencia (Inria): “Post-quantum cryptography assumes that attackers will have a quantum computer”, Alliancy, 20/1/2020
• Cryptanalysis: grounds for trust, part 1, part 2, Binaire, 9/4/2021
• Presentation by Maria Naya Plasencia - Cryptanalysis: the foundations for security, Inria, Canal U, 5/3/2015