L’algorithme Falcon sélectionné pour la nouvelle norme de cryptographie postquantique

Tout commence par un article publié en 1996. Le mathématicien Peter Shor y présente un algorithme capable de briser RSA, le système de chiffrement asymétrique devenu la pierre angulaire des échanges sur Internet. Mais pas d’inquiétudes immédiates : pour réaliser cette prouesse, l’algorithme aurait besoin d’une puissance de calcul que seul un ordinateur quantique pourrait offrir. Or, à la fin du siècle dernier, l’échéance paraît encore lointaine. Dans la communauté des cryptographes, en revanche, on comprend que les jours de RSA sont comptés. Même chose d’ailleurs pour une autre méthode appelée chiffrement par courbes elliptiques. Il faut donc anticiper l’inéluctable et réfléchir à quelque chose de plus solide.

« Quatre alternatives ont émergé, énumère Pierre-Alain Fouque, professeur à l’université de Rennes 1. La méthode de McEliece basée sur un code correcteur d’erreurs, celle à plusieurs variables, celle basée sur les isogénies et celle basée sur les réseaux euclidiens. A priori, elles résistent toutes aux ordinateurs quantiques. Mais nous les appelons des conjectures. En effet, nous n’avons pas de preuve formelle que ces alternatives résistent, même s’il n’existe pas actuellement d’algorithmes permettant de les casser. »

Deux décennies plus tard, l’ordinateur quantique s’apprête à devenir réalité. Anticipant cette révolution, fin 2016, l’Institut américain des normes et de la technologie (NIST) lançait un concours international pour choisir les meilleurs algorithmes susceptibles de devenir ensuite des standards du chiffrement postquantique. Des équipes de scientifiques du monde entier ont déposé 82 candidatures. Le NIST a retenu un premier lot de quatre propositions : le chiffrement Kyber pour l’accès sécurisé aux sites web, les systèmes Sphinx+, Dilithium et Falcon pour les signatures numériques.

Une cryptographie compacte et sécurisée

L’algorithme Falcon est un schéma de signature basé sur la méthode des réseaux euclidiens.

« Les signatures sont utilisées tous les jours pour plein de choses. Par exemple, quand on achète sur Internet, il y a un certificat qui nous assure que nous sommes bien sur le bon site marchand et pas sur un faux. De façon plus générale, la signature garantit l’intégrité du message et l’authenticité de l’émetteur. En pratique, il faut qu’elle soit sûre, mais aussi très compacte. Si elle est trop grosse, on doit l’envoyer en plusieurs paquets... arrivant donc souvent avec des délais différents. Ce qui engendre des temps de communication plus longs. »

À cet égard, Falcon s’avère justement très compacte. Ce qui constitue un gros avantage. Nous avons vraiment voulu proposer des choses efficaces pour les industriels. La méthode actuellement utilisée repose sur les courbes elliptiques qui permettent également des signatures très compactes. Pour la remplacer, il fallait donc quelque chose d’aussi bien.

Algorithmes sans brevet

La candidature Falcon a été portée par un groupe de chercheurs^[1] appartenant à différentes organisations. « Il y avait des gens de Thales, d’IBM, de PQShield, de NCC Group, ou encore des mathématiciens de l’université de Brown qui avaient été précurseurs avec un schéma de chiffrement appelé NTRU. Ils avaient ensuite fondé l’entreprise NTRU Cryptosystems rachetée plus tard par OnBoardSecurity, une société du groupe Qualcomm. Le schéma NTRU repose un peu sur le même principe que Falcon. C’est pour cela que nous les avons conviés à rejoindre notre proposition. »

Précision importante : « il ne s’agit pas du tout d’un consortium industriel. D’ailleurs, dans le processus NIST, les algorithmes candidats ne doivent pas faire l’objet de brevets. Il faut qu’ils soient publics de façon à pouvoir être ensuite utilisés par le plus grand nombre de personnes. Dans le passé, on a vu des systèmes de chiffrement couverts par un brevet, ce qui a eu pour effet de ralentir le développement de certaines méthodes de cryptographie. »

Pierre-Alain Fouque avait déjà participé, à différents degrés, aux compétitions AES puis SHA-3. « J’ai toujours aimé ce type de concours. C’est un formidable accélérateur de la recherche. Cela permet d’obtenir beaucoup de résultats sur un domaine. Il y a beaucoup de personnes qui travaillent. Beaucoup de moyens alloués. C’est très stimulant. »

Et la sélection par le NIST ? « Très gratifiante, évidemment. On se dit que nos travaux vont être utiles pour tout le monde. Cela étant, il faut conserver à l’esprit que Falcon n’est pas une création ex nihilo. Nous nous appuyons sur des recherches amorcées par d’autres il y a une vingtaine d’années. »

Le projet Post-Quantum TLS

Le chercheur a pris récemment la direction de Capsule, une nouvelle équipe dédiée à la cryptographie créée par l’Université de Rennes, le CNRS et Inria. « Nous avions auparavant une équipe en cybersécurité qui commençait à beaucoup grossir et que nous avons choisi de scinder en deux. C’était l’occasion d’en consacrer une complètement à la cryptographie. Cela permet de donner plus de visibilité à cette thématique. »

Pierre-Alain Fouque est par ailleurs responsable scientifique du projet Post-Quantum TLS qui fait partie du PEPR Quantique, un "Programme et équipement prioritaire de recherche" lancé par le Gouvernement dans le cadre du volet France 2030 / Financement des investissements stratégiques^[2] . « Notre projet regroupe treize équipes au niveau national. Il est doté de huit millions d’euros. Il vise à intéresser les industriels français pour qu’ils soient à l’état de l’art et les premiers à implémenter la cryptographie postquantique dans leurs produits afin d’en tirer un avantage concurrentiel. »