Ê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

Function Field Sieve in Characteristic Three

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

Résumé

In this paper we investigate the efficiency of the function field sieve to compute discrete logarithms in the finite fields $\mathbb{F}_{3^n}$ . Motivated by attacks on identity based encryption systems using supersingular elliptic curves, we pay special attention to the case where n is composite. This allows us to represent the function field over different base fields. Practical experiments appear to show that a function field over $\mathbb{F}_3$ gives the best results.

Official source

https://infoscience.epfl.ch/record/215133?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, 2004
Article de conférence

Résumé

Official source

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

À propos de ce résultat

Concepts associés (7)

Concepts associés

Chargement

Publications associées (5)

Publications associées

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

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

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

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

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