Corentin Jeudy (Orange Labs, Rennes)

Le problème « Module Learning With Errors » (M-LWE) est une hypothèse calculatoire fondamentale en cryptographie sur les réseaux Euclidiens qui offre un compromis intéressant entre efficacité et sécurité des cryptosystèmes qui en résultent. Ce problème est paramétré par une distribution de secret ainsi qu’une distribution d’erreur. Il y a encore aujourd’hui un fossé entre le choix des distributions offrant une difficulté prouvée (formulation standard de M-LWE, c’est-à-dire secret uniforme modulo \(q\) et erreur Gaussienne), et le choix des distributions utilisées par des schémas pratiques (petits secrets et erreurs). Le but de cette présentation est de réduire ce fossé en exposant deux résultats :

(1) M-LWE avec une distribution sur des secrets courts et avec une erreur Gaussienne est aussi difficile que la forme standard de M-LWE, à condition que le rang \(d\) soit au moins logarithmique en le degré de l’anneau \(n\). On prouve d’abord ce résultat pour la version calculatoire, puis pour la version décisionnelle.

(2) M-LWE avec une distribution sur des erreurs courtes et avec des secrets uniformes modulo \(q\) est aussi difficile que la forme standard de M-LWE, à condition que le nombre d’échantillons \(m\) soit proche du rang \(d\).