Séminaire d'arithmétique à Lyon

Réductions cas-moyen pour Ideal-SVP

by Joël Felderhoff

Europe/Paris
Description

Dans un corps de nombre, un idéal est un réseau euclidien. Est-il difficile d'y trouver des vecteurs courts ?

En cryptographie, nous nous intéressons aux problèmes algorithmiques dans le cas moyen, typiquement : "étant donné une clé publique qui a été tirée selon une certaine distribution, peut-ont retrouver la clé secrète associée". L'analyse de ces problèmes est donc un enjeux important pour évaluer la sécurités des systèmes cryptographiques utilisés dans diverses application, du civil (Signal, HTTPS...) au militaire.

Dans cet exposé, nous nous intéresserons au problème "Ideal-SVP" qui consiste à trouver un vecteur court dans un idéal d'un corps de nombre. Après l'avoir présenté, nous discuterons différentes réductions visant à prouver que ce problème est difficile "en moyenne", et donc utilisable comme base pour produire des système cryptographiques sûrs.