Thèse Sécurité Classique Concrète et Efficacité des Cryptosystèmes Post-Quantiques Basés sur les Isogénies H/F

Doctorat_Gouv

Les cryptosystèmes à base d'isogénies dans un cadre commutatif (notamment CSIDH) reposent sur l'action du groupe de classes G d'un anneau imaginaire quadratique O sur un ensemble X de courbes elliptiques (classes d'isomorphismes de courbes elliptiques). Chaque courbe admet un plongement de O dans son anneau d'endomorphismes, que l'on appelle une « orientation ». L'action du groupe de classes G doit respecter ces orientations, ou commuter avec elles.

Dans CSIDH, et ses précurseurs dus à Couveignes et à Rostovtsev et Stolbunov, l'orientation est évidente (et ne requiert aucun codage ni structure de données particulière). Dans des schémas plus récents comme SCALLOP, les orientations sont non triviales, ce qui permet d'utiliser des groupes de classes plus grands et d'ordre connu - condition essentielle à la bonne implémentation de nouveaux cryptosystèmes post-quantiques basés sur l'action de groupe - mais complexifie considérablement le calcul de l'action de groupe. L'étude mathématique de ces orientations et des cryptosystèmes qui les utilisent est à un stade avancé, mais les études pratiques restent encore peu développées.

Ce projet de doctorat porte sur le calcul efficace avec des courbes orientées. D'une part, il existe d'importantes applications constructives : améliorer les représentations des orientations et les algorithmes qui les manipulent permettrait d'améliorer sensiblement les performances de cryptosystèmes importants basés sur les isogénies. D'autre part, il existe également des applications destructives : les aspects concrets de l'implémentation des attaques classiques sur les actions de groupe n'ont pas été étudiés de manière approfondie en présence d'orientations. Les résultats obtenus jusqu'à présent traitent les isogénies constituant une action de groupe comme de simples opérations atomiques, et leur contribution aux estimations de sécurité concrètes est mal comprise. Les attaques classiques les plus connues sont des variantes mineures d'attaques « génériques » sur les actions de groupe : autrement dit, elles n'exploitent pas efficacement la représentation des éléments (c'est-à-dire les courbes et les orientations). Nous cherchons ici à comprendre pleinement à la fois la « surcharge » due aux orientations et les nouveaux vecteurs d'attaque spécialisés potentiels liés à leur structure algébrique. Une meilleure compréhension de ce phénomène aura également un impact pratique important grâce à une meilleure sélection des paramètres (potentiellement avec des tailles de clés réduites), et en intégrant ces éléments dans les principes de conception constructive.

The rise of quantum computing poses a significant threat to classical public-key cryptosystems. These algorithms rely on the computational complexity of mathematical problems such as the factorization of large integers or the elliptic-curve discrete logarithm problem. These cryptosystems are now threatened by quantum algorithms, such as Shor's algorithm, that can efficiently solve those underlying problems. Thus, currently deployed public-key cryptosystems, such as key agreement and digital signature schemes crucial to internet security, are vulnerable to the existence of powerful general quantum computers.

The international academic and industrial research community is working on developing new 'post-quantum' cryptosystems, designed to resist attacks from both conventional ('classical') and quantum adversaries. Isogeny-based cryptography is a relatively young branch of post-quantum cryptography that uses an extensive body of mathematics and algorithms developed for conventional curve-based cryptography. In theory, isogeny-based cryptography is a convenient setting for many advanced post-quantum protocols. In practice, it generally has the advantage of lower bandwidth (compared with other post-quantum schemes), but the strong disadvantage of heavy algebraic computations which induce high latencies. The security of isogeny-based cryptography is based on supposedly hard problems in computational number theory, but these problems are relatively obscure (when compared with classic problems like Integer Factorization for RSA security, or the Closest Vector Problem for lattice-based post-quantum cryptosytems). Reducing these practical costs, and deepening our understanding of the fundamental hard problems, are vital and interdependent areas of research in contemporary cryptography.