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}}$

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.


Editor(s):
Canetti, Ran
Garay, Juan A.
Published in:
Advances in Cryptology – CRYPTO 2013, 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II., 109-128
Presented at:
Advances in Cryptology – CRYPTO 2013, Santa Barbara, CA, USA, August 18-22, 2013
Year:
2013
Publisher:
Springer Berlin Heidelberg
Keywords:
Note:
Best Paper Award (by unanimous decision of the Program Committee)
Laboratories:




 Record created 2016-01-19, last modified 2018-03-17

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)