Laboratoire IMATH

Titre :
Polynomial Modular Number System, un tour d’horizon

Résumé :
L’Arithmétique Modulaire est un thème au cœur d’un certain nombre de protocoles cryptographiques. Parmi les protocoles pré-quantiques se trouvent le protocole RSA ou encore la cryptographie basée sur les Courbes Elliptiques (ECC) tandis que du côté des protocoles post-quantiques figurent les variantes de NTRU tels que Kyber, qui a été sélectionné par le NIST pour standardisation, ainsi que les protocoles basés sur les Isogénies. Le Polynomial Modular Number System (PMNS) permet une arithmétique facilement parallélisable ce qui explique son intérêt dans un tel contexte.
Le PMNS a fait ses preuves dans des protocoles d’Arithmétique Modulaire portant sur des entiers premiers de petite taille pour l’ECC et pour les Isogénies (en dessous de 736 bits). Dans cet exposé sera présenté le PMNS et son adaptation à différents cas d’utilisations pour des tailles d’entiers diverses jusqu’à 8192 bits inclus mais aussi de nouveaux cas d’usages en petite taille.
Le processus de génération classique comportant une étape en O(2^n), une nouvelle méthode est utilisée pour contourner cette étape lorsque n est grand, typiquement pour les grands entiers. L’utilisation d’algorithmes de multiplication sous-quadratiques est important lorsque la taille des entiers augmente et le PMNS se trouve particulièrement adapté à ceux-ci grâce au manque de nécessité du passage de retenue. De plus, pour les mêmes raisons, les PMNS se trouvent adaptés à l’utilisation du multi-threading.
Enfin, la découverte d’une classe d’entiers premiers permet une arithmétique aussi rapide que celle des Pseudo-Mersennes avec une bien plus grande densité.