Cryptology ePrint Archive: Report 2013/582

The Special Number Field Sieve in $\F _{p^{n}}$, Application to Pairing-Friendly Constructions

Antoine Joux and Cécile Pierrot

Abstract: In this paper, we study the discrete logarithm problem in finite fields related to pairing-based curves. We start with a precise analysis of the state-of-the-art algorithms for computing discrete logarithms that are suitable for finite fields related to pairing-friendly constructions. To improve upon these algorithms, we extend the Special Number Field Sieve to compute discrete logarithms in $\F_{p^{n}}$, where $p$ has an adequate sparse representation. Our improved algorithm works for the whole range of applicability of the Number Field Sieve.

Category / Keywords: foundations / Discrete logarithms, SNFS, pairing-based

Date: received 9 Sep 2013

Contact author: Antoine Joux at m4x org

Available format(s): PDF | BibTeX Citation

Version: 20130914:023816 (All versions of this report)

Short URL: ia.cr/2013/582

Discussion forum: Show discussion | Start new discussion