Post-doctorat au sein de l'équipe capsule

Post-doctorat au sein de l'équipe CAPSULE

L'IRISA est le plus grand laboratoire public de recherche français dans le domaine de l'informatique et des technologies de l'information. Il regroupe plus de 850 personnels (chercheurs, enseignants-chercheurs, ingénieurs, techniciens et administratifs). L'équipe CAPSULE s'intéresse à la sécurité des implémentations logicielles et matérielles de la cryptographie post-quantique. Ce poste d'ingénieur de recherche s'inscrit dans le projet PQ-TLS du PEPR Quantique.

Les problèmes d’isomorphismes entre structures combinatoires ou algébriques sont classiques en théorie de la complexité. Leur difficulté sert parfois de fondation pour des cryptosystèmes, typiquement lorsque la structure algébrique sous-jacente est celle d’un code correcteur d’erreurs ou d’une variété algébrique. Dans le cas des réseaux Euclidiens, autrement dit, des groupes abéliens discrets vivant dans des espaces vectoriels avec une notion de géométrie, le problème est étonnamment peu étudié. Sa version la plus naturelle consiste à décider si un réseau est une rotation du réseau cubique Zn. Un algorithme dû à Ducas permet de détecter cette situation en temps 2^(n/2+ε), et de conclure ; c’est essentiellement le meilleur algorithme connu à ce jour.

Informellement, l’algorithme découvre (ou non) des vecteurs unitaires orthogonaux en cherchant à construire une base bien réduite du réseau ambiant. L’intérêt de la méthode de Ducas est qu’il est suffisant de travailler dans la moitié de la dimension pour résoudre le problème — l’algorithme considère en effet des sous-réseaux et des routines exponentielles en leur dimension. Le critère utilisé pour détecter l’orthogonalité de vecteurs a le bon goût d’être simple à utiliser, mais est cependant peu raffiné et n’exploite pas une partie non négligeable de l’information obtenue après une étape de réduction.

Nos expériences et analyses suggèrent en particulier qu’il est possible de réduire ce nombre d’étapes d’une part ; d’autre part qu’il doit être possible de travailler en dimension strictement plus petite que n/2, d’un facteur constant. Ce facteur a cependant un impact dans les analyses de sécurité de certains schémas de cryptographie théorique, où tout progrès non négligeable peut entraîner une réévaluation substantielle des paramètres.

L’objectif de ce post-doctorat est dans un premier temps de reprendre l’analyse de Ducas et d’exploiter justement les vecteurs supplémentaires pour raffiner le critère de détection. L’analyse pourra reposer sur des arguments ou hypothèses heuristiques sur le comportement de projections aléatoires et le nombre de vecteurs orthogonaux espérés à chaque étape. Si l’analyse conduit comme escompté à un gain constant dans l’exposant, idéalement une amélioration à n/3 + ε, un article sera rédigé dans un second temps pour permettre la diffusion du résultat. Nous espérons une soumission dans une conférence en lien avec la théorie de la complexité ou sur des thèmes généraux d’algorithmique.

Un prototype d’implémentation (en Python) de l’algorithme décrit sera espéré en complément des analyses proposées, mais n’est cependant pas un objectif primaire. On veillera à ce que les données expérimentales obtenues pour formuler les hypothèses heuristiques soient publiques et reproductibles.

Profil / Compétences :

* Algorithmique des réseaux Euclidiens
* Implémentation d'algorithmes pour réseaux Euclidiens
* Formation mathématique
#J-18808-Ljbffr