On Small Degree Extension Fields in Cryptology

Robert Granger
PhD dissertation, University of Bristol, UK, February 2006, 2006
Thèse hors EPFL

Résumé

This thesis studies the implications of using public key cryptographic primitives that are based in, or map to, the multiplicative group of finite fields with small extension degree. A central observation is that the multiplicative group of extension fields essentially decomposes as a product of algebraic tori, whose properties allow for improved communication efficiency. Part I of this thesis is concerned with the constructive implications of this idea. Firstly, algorithms are developed for the efficient implementation of torus-based cryptosystems and their performance compared with previous work. It is then shown how to apply these methods to operations required in low characteristic pairing-based cryptography. Finally, practical schemes for high-dimensional tori are discussed. Highly optimised implementations and benchmark timings are provided for each of these systems. Part II addresses the security of the schemes presented in Part I, i.e., the hardness of the discrete logarithm problem. Firstly, an heuristic analysis of the effectiveness of the Function Field Sieve in small characteristic is given. Next presented is an implementation of this algorithm for characteristic three fields used in pairing-based cryptography. Finally, a new index calculus algorithm for solving the discrete logarithm problem on algebraic tori is described and analysed.

Official source

https://infoscience.epfl.ch/record/215141?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Estimates for Discrete Logarithm Computations in Finite Fields of Small Characteristic

Robert Granger

We give estimates for the running-time of the function field sieve (FFS) to compute discrete logarithms in

\mathbb{F}_{p^n}^{\times}

for small

p

. Specifically, we obtain sharp probability estimates that allow us to select optimal parameters in cases of cryptographic interest, without appealing to the heuristics commonly relied upon in an asymptotic analysis. We also give evidence that for any fixed field size some may be weaker than others of a different characteristic or field representation, and compare the relative difficulty of computing discrete logarithms via the FFS in such cases.

Springer Berlin Heidelberg2003

Chargement

Indiscreet logarithms in finite fields of small characteristic

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

Recently, several striking advances have taken place regarding the discrete logarithm problem (DLP) in finite fields of small characteristic, despite progress having remained essentially static for nearly thirty years, with the best known algorithms being of subexponential complexity. In this expository article we describe the key insights and constructions which culminated in two independent quasi-polynomial algorithms. To put these developments into both a historical and a mathematical context, as well as to provide a comparison with the cases of so-called large and medium characteristic fields, we give an overview of the state-of-the-art algorithms for computing discrete logarithms in all finite fields. Our presentation aims to guide the reader through the algorithms and their complexity analyses ab initio.

2018

Chargement

We explore a few algebraic and geometric structures, through certain questions posed by modern cryptography. We focus on the cases of discrete logarithms in finite fields of small characteristic, the structure of isogeny graphs of ordinary abelian varieties, and the geometry of ideals in cyclotomic rings. The presumed difficulty of computing discrete logarithms in certain groups is essential for the security of a number of communication protocols deployed today. One of the most classic choices for the underlying group is the multiplicative group of a finite field. Yet this choice is showing its age, and particularly when the characteristic of the field is small: recent algorithms allow to compute logarithms efficiently in these groups. However, these methods are only heuristic: they seem to always work, yet we do not know how to prove it. In the first part, we propose to study these methods in the hope to get a better understanding, notably by revealing the geometric structures at play. A more modern choice is the group of rational points of an elliptic curve defined over a finite field. There, the difficulty of the discrete logarithm problem seems at its peak. More generally, the group of rational points of an abelian variety (notably the Jacobian of a curve of small genus) could be appropriate. One of the main tools for studying discrete logarithms on such objects is the notion of isogeny: a morphism from a variety to another one, which allows, among other things, to transfer the computation of a logarithm. Whereas the theory for elliptic curves is already mature, little is known about the structures formed by these isogenies (the isogeny graphs) for varieties of higher dimension. In the second part, we study the structure of isogeny graphs of absolutely simple, ordinary abelian varieties, with a few consequences regarding discrete logarithms on Jacobians of hyperelliptic curves of genus 2, the main object of concern of so-called hyperelliptic cryptography. The security of quite a few protocols, notably those relying on discrete logarithms, would collapse in front of an adversary equipped with a large-scale quantum computer. This perspective motivates cryptographers to study problems that would resist this technological feat. One of the major directions is cryptography based on Euclidean lattices, relying on the difficulty to find short vectors in a given lattice. For efficiency, one benefits from considering lattices endowed with more structure, such as the ideals of a cyclotomic field. In the third part, we study the geometry of these ideals, and show that a quantum computer allows to efficiently find much shorter vectors in these ideals than is currently possible in generic lattices.

EPFL2018

Chargement

Estimates for Discrete Logarithm Computations in Finite Fields of Small Characteristic

Robert Granger

We give estimates for the running-time of the function field sieve (FFS) to compute discrete logarithms in

\mathbb{F}_{p^n}^{\times}

for small

p

Springer Berlin Heidelberg2003

EPFL2018