On Torus-Based Cryptography
Autour de la cryptographie à base de tores algébriques
Résumé
Discrete logarithm-based cryptography has sustained many studies in the last decade. Lenstra and Verheul have especially proposed to make use of algebraic tori. We focus here on the computational aspect of these ideas and on the parametrization of such structures. Van Dijk and Woodruff have recently given an explicit way of compactly representing a large set of points on an algebraic torus. The computational cost of this algorithm can be improved thanks to several tools. First we use a new class of bases for finite field extensions, namely elliptic normal bases due to Couveignes and Lercier. Besides we notice that the size of the groups involved is given in terms of cyclotomic polynomials and their modular inverses. The magnitude of their coefficients plays a dramatic role in the complexity study. In the case of indices dividing the product of two distinct primes, we manage to find bounds or explicit expressions of these coefficients. This allows us to compute the communication cost of protocoles such as Diffie-Hellman multiple key exchange.
La cryptographie basée sur le logarithme discret a connu de nombreuses avancées dans les dix dernières années, notamment avec l'utilisation de tores algébriques introduite par Lenstra et Verheul. Ici on axe notre travail sur la facette constructive de ces idées et se penche sur le paramétrage de ces structures. Van Dijk et Woodruff ont récemment proposé une solution pour représenter de manière compacte une famille de points d'un tore algébrique. Afin d'améliorer la complexité asymptotique de cet algorithme, on a recours à plusieurs outils. D'une part on utilise un nouveau type de bases pour les extensions de corps finis, les bases normales elliptiques dues à Couveignes et Lercier. Par ailleurs, les tailles des objets manipulés font intervenir des polynômes cyclotomiques et leurs inverses modulaires. L'amplitude de leurs coefficients intervient directement dans l'étude de complexité. Dans le cas où leurs indices sont des diviseurs d'un produit de deux nombres premiers, on parvient à des bornes voire des expressions explicites pour ces coefficients, qui permettent de conclure quant à l'amélioration du coût de communication dans des protocoles cryptographiques comme une négociation de clefs multiples de Diffie-Hellman.
Loading...