Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Publication

Estimates for Discrete Logarithm Computations in Finite Fields of Small Characteristic

Robert Granger
Springer Berlin Heidelberg, 2003
Article de conférence

Résumé

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.

Official source

https://infoscience.epfl.ch/record/215134?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

Robert Granger
Springer Berlin Heidelberg, 2003
Article de conférence

Résumé

Official source

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

À propos de ce résultat

Concepts associés (10)

Concepts associés

Chargement

Publications associées (13)

Chargement

Afficher plus

Publications associées

Chargement

Publications associées (13)

On Small Degree Extension Fields in Cryptology

Robert Granger

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.

PhD dissertation, University of Bristol, UK, February 20062006

Chargement

In this paper we show how some recent ideas regarding the discrete logarithm problem (DLP) in finite fields of small characteristic may be applied to compute logarithms in some very large fields extremely efficiently. By combining the polynomial time relation generation from the authors’ CRYPTO 2013 paper, an improved degree two elimination technique, and an analogue of Joux’s recent small-degree elimination method, we solved a DLP in the record-sized finite field of

2^{6120}

elements, using just a single core-month. Relative to the previous record set by Joux in the field of

2^{4080}

elements, this represents a 50% increase in the bitlength, using just 5% of the core-hours. We also show that for the fields considered, the parameters for Joux’s

L_Q(1/4+o(1))

algorithm may be optimised to produce an

L_Q(1/4)

algorithm.

Springer Berlin Heidelberg2013

Chargement

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$

Robert Granger, Jens Markus Zumbrägel

In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as

L_{q^n}(1/3,(4/9)1/3)

for computing arbitrary logarithms, but also in an heuristic polynomial time algorithm for finding the discrete logarithms of degree one and two elements when the field has a subfield of an appropriate size. To illustrate the efficiency of the method, we have successfully solved the DLP in the finite fields with

2^{1971}

and

2^{3164}

elements, setting a record for binary fields.

Springer Berlin Heidelberg2013

Chargement

Afficher plus

2^{6120}

elements, using just a single core-month. Relative to the previous record set by Joux in the field of

2^{4080}

elements, this represents a 50% increase in the bitlength, using just 5% of the core-hours. We also show that for the fields considered, the parameters for Joux’s

L_Q(1/4+o(1))

algorithm may be optimised to produce an

L_Q(1/4)

algorithm.

Springer Berlin Heidelberg2013

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$

Robert Granger, Jens Markus Zumbrägel

In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as

L_{q^n}(1/3,(4/9)1/3)

2^{1971}

and

2^{3164}

elements, setting a record for binary fields.

Springer Berlin Heidelberg2013