“The CNRS hampers the chances of European systems to be part of future cryptography standards”

Research – IT specialists have been working for years on this selection process which should lead to new recommendations on security standards. Can you detail the steps that have already taken place?

Damien Stehle – Many companies and institutions are working on the quantum computer, the arrival of which threatens the security of digital exchanges. However, these exchanges have now become essential to the functioning of our societies. Also, not to be taken aback – because the development of security systems is long – the American Institute of Standards and Technology (National Institute of Standard and Technology, NIST) has launched a great international competition to evaluate different systems and, ultimately, choose what will become the standard for these new exchanges. At the end of 2017, 82 submissions were made by teams around the world. In July 2020, after several phases of open evaluationsthe NIST has announced the finalists : 4 submissions in the category of public key encryption (key exchange protocols to establish confidential communications) and 3 in the category of digital signatures (protocols for the protection of integrity and authentication).

On what mathematical principles are these submissions based?

The idea behind these post-quantum systems is to find mathematical problems that are difficult to solve by any type of computer, including using quantum computing, and at the same time exploitable for cryptography. Many types of problems are assessed: error correcting codesthem euclidean networks, systems of multivariate equations Where hash functions. In the encryption category, one of the proposed protocols is based on error-correcting codes (Classic McEliece) and three on Euclidean networks (CRYSTALS-KYBER, NTRU and SABER); for digital signatures, we have GeMSS which uses systems of multivariate equations, FALCON and CRYSTALS-DILITHIUM which are based on Euclidean networks.

Are the CNRS claims about Euclidean networks?

Absolutely. Problems related to Euclidean networks have been evaluated for a long time, because they have the advantage of being robust and flexible. By modifying the parameters, by tweaking the system, we obtain different and effective protocols. This is why there were more than twenty candidate Euclidean networks in the initial submissions and why there are still five in the final – out of seven finalists – including three on encryption. For the latter, there is the American submission NTRU, whose patents date from 1996, and have expired. The other two submissions are European: there is KYBER, of which I am co-author with colleagues based among others in Belgium, the Netherlands, Germany and Switzerland; and SABER, carried by colleagues from KU Leuven University, Belgium. The CNRS claim relates to KYBER and SABER, concerning a patent whose inventors are researchers Philippe Gaborit, from the University of Limoges, and Carlos Aguilar-Melchor, from the University of Toulouse, and which is held by the CNRS.

How did this patent appear in the competition?

The patent was declared because it applied to two initial NIST competition submissions that used it: BIKE and HQC. Submissions in which the inventors of the patent were parties. In the NIST competition requirements, applicants’ authors had to declare whether they were aware of any intellectual property applying to their applicant, and the rights holder – the patent owner – then had to indicate what they intended to do in the process. the case where the tenders were retained for standardization. So the patent had been mentioned at the time, and the CNRS had then declared that this patent would be free of rights for these candidates. But these two candidates were not selected among the finalists.

What changed ?

It gradually became apparent that the CNRS claimed intellectual property rights over these two finalists that I mentioned, and not only over BIKE and HQC.

For you, this patent is not applicable to NIST finalists. For what reasons ?

Basically, this patent is about sharing a secret with an explicit condition of switchability between elements. The secret is the product of three elements has, s and you. And the secret shared between the two protagonists (Alice and Bob traditionally) is a*s*t for Alice, and a*t*s for Bob. So for this secret to be truly shared – for Alice and Bob to hold the same value of the key – it needs that st be equal to you*s, in other words that the operations are commutative. And this property is well specified in the patent: the operations mentioned must be commutative. The problem from the point of view of the applicability of the patent to KYBER and SABER, is that a few months before the filing of the patent, a article by three computer scientists, including Vadim Lyubashevsky, a researcher at IBM’s cryptography laboratory in Zurich (Switzerland) who is co-author of the KYBER proposal, proposed the same principle of secret sharing with vectors and matrices. And it works without having to invoke commutativity. Indeed, in this article, the roles of Alice and Bob are symmetrical (technically, there is one who multiplies on the left and the other on the right). As a result, the article which does the same thing as the patent, but in a more general way (by taking in the article matrices of dimension 1 we find the patent), is prior to the patent. KYBER and SABER based on the article, so the patent has no legitimacy against these submissions.

What motivations are there to assert this patent in this case?

This is the question that I ask myself and that I asked the general direction of innovation as well as the presidency of the CNRS, without obtaining an answer as to the legitimacy of the claim. As I explained, the claim of applicability of this patent to KYBER and SABER is not scientifically legitimate. Moreover, asserting a patent can make sense if one solution is truly better than the others. However, here the three proposals examined for the final are based on similar assumptions and stand in a pocket handkerchief in terms of security and performance. NTRU’s key generation algorithm is slower, but that’s not too bad, because we don’t generate keys all the time.

What could be the consequences of this claim?

It’s not very complicated to predict: at the start of the competition, the NIST announced that it preferred royalty-free solutions. If you want a standard solution, usable by all, that’s what you have to do. If the NIST fears that choosing one of the two solutions for which the CNRS claims a patent will hinder the adoption of the future standard, it will choose NTRU. This is what my colleague Vadim and I recommended to NIST. But it would be a shame not to have a European solution because of a wish to derive benefit from a patent, without scientific applicability vis-à-vis the finalists. The mathematical foundations of cryptography are really a theme where the French school – whether it be researchers in France or French researchers established abroad – is very strong. It is distressing to see the CNRS intervening by ransacking the work and efforts of this community.

Interview by Philippe Pajot

To know more

The technical aspects of the non-applicability of the patent to this scenario are detailed in this article:

© Inria / Photo B. Fourrier

We would like to say thanks to the author of this article for this outstanding content

“The CNRS hampers the chances of European systems to be part of future cryptography standards”

Visit our social media profiles along with other pages related to themhttps://metfabtech.com/related-pages/