Amphi émeraude, Télecom Paris Tech, 46 rue Barrault
- 10:00. Pierre Loidreau « Codes cellulaires et applications cryptographiques »
Dans le domaine de la cryptographie à clé publique reposant sur les codes correcteurs d’erreurs, un problème essentiel pour les concepteurs de systèmes est de parvenir à gérer la très grande taille de clé publique nécessaire pour assurer une sécurité convenable. Un moyen consiste à utiliser des codes structurés tels les codes quasi-cycliques qui permettent des représentations compactes de la clé publique. Cependant, même si en théorie la sécurité des systèmes n’en est pas affectée, dans la pratique la structure algébrique sous-jacente est assez peu considérée dans la mise au point d’attaques par décodage. Dans cet exposé on étudiera une famille de codes généralisant la notion de codes quasi-cycliques. La matrice génératrice est formée de « cellules » qui sont des matrices carrées prises dans une algèbre de matrices engendrée par un polynôme. On montrera qu’un diviseur de ce polynôme permet d’engendrer des codes de paramètres plus petits. On décrira les effets de cette projection sur le décodage et la recherche de mots de petit poids dans des codes quasi-cycliques tant en métrique de Hamming qu’en métrique rang. On montrera comment cette approche peut réduire la complexité des attaques déjà connues, en fonction du poids du polynôme considéré ou bien de l’espace de ses coefficients. Les résultats soulèvent des questions sur l’existence de polynômes particuliers qui divisent des polyômes de type $X^n-1$ dans des corps finis.
Bien que le sujet ne soit pas lié à la cryptographie à base de réseaux, on montrera, si le temps le permet comment ces idées ont été appliquées ou pourraient être appliqués à des problèmes de décodage de type Ring-LWE.
- 11:15. Léo Ducas, « Fast Fourier Orthogonalization »
The classical Fast Fourier Transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the circular convolution ring $\mathbb R[x]/(x^d -1)$ — a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix-vector products when the matrix is circulant. In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of a circulant matrix. We show that, when $n$ is composite, it is possible to proceed to the orthogonalization in an inductive way, leading to a structured Gram-Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the Nearest Plane algorithm. The results easily extend to cyclotomic rings, and can be adapted to Gaussian Samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.
- 14:15. Philippe Langevin, Institut mathématique de Toulon, « propriété d’extension de la métrique de Lee »
Le théorème d’extension de MacWilliams affirme qu’une isométrie définie sur un code linéaire se prolonge en une transformation monomiale, c’est-à-dire, une isométrie de l’espace de Hamming tout entier. La question du prolongement d’une isométrie à l’espace ambiant se pose pour toutes les métriques dans mon exposé je ferai le point sur des travaux récents concernant la propriété d’extension de la métrique de
Lee dans le cas des codes linéaires définis sur un corps premier.
- 15:30. Renaud Sirdey, CEA List, « Mise en œuvre pratique du chiffrement homomorphe »
Nous présentons des travaux d’implémentation du chiffrement (fully) homomorphe et de développement d’outils logiciels supports (compilateurs) permettant de faire le lien entre des algorithmes applicatifs et ce formalisme bas-niveau, de manière aussi performante que possible. L’exposé portera également sur les problématiques d’intégration du chiffrement homomorphe dans des cas d’applications concrets, en particulier pour ce qui est de son interfaçage avec du chiffrement symétrique. Enfin, nous essaierons de faire un point sur les performances actuelles et présenterons quelques scénarios applicatifs qui semblent aujourd’hui être à la portée du FHE.
