Multi angle

H 1 Computing discrete logarithms in $GF(p^n)$: practical improvement of the individual logarithm step

Auteurs : Guillevic, Aurore (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : This talk will focus on the last step of the number field sive algorithm used to compute discrete logarithms in finite fields. We consider here non-prime finite fields of very small extension degree: $1 \le n \le 6$. These cases are interesting in pairing-based cryptography: the pairing output is an element in such a finite field. The discrete logarithm in that finite field must be hard enough to prevent from attacks in a given time (e.g. $10$ years). Within the CATREL project we aim to compute DL records in finite fields of moderate size (e.g. in $GF(p^n$) of global size from $600$ to $800$ bits) to estimate more tightly the hardness of DL in fields of cryptographic size ($2048$ bits at the moment). The best algorithm known to compute discrete logarithms in large finite fields (with small $n$) is the number field sieve (NFS):

    (1) polynomial selection: select two distinct polynomials $f,g$ defining two number fields, such that they share modulo $p$ an irreducible degree $n$ factor, and have additional properties to improve the next two steps.
    (2) sieving: sieve over elements that satisfy relations, to build the factor basis made of prime ideals of small norm.
    (3) linear algebra: compute the kernel of a large matrix computed the step before. Then the logarithm of each element in the factor basis is known.
    (4) individual logarithm: for a given element $s \in GF(p^n)$, decompose it over the factor basis to finally compute its discrete logarithm.

    The most time consuming steps are the second and third: sieving and linear algerbra. After the sieve and the linear algebra, the logarithms of the prime ideals of small norm are known. To finally compute the discrete logarithm of the given element $s$, we lift $s$ in one of the number fields and factor it in prime ideals as with “small” elements in the sieve step. However here, $s$ does not have a small norm (bounded by $B \ll Q$). Its norm is very large, in particular, larger than $Q$. The usual way is to test for many $s' = s \cdot g^e$ with $g$ the given generator of $GF(p^n)$ until the norm of $s'$ is smooth enough. The time spent to find a good $e$ is asymptotically less than the sieving time. In practice, another modification of $s'$ is computed to reduce its norm. In [?], the authors write $s' = a(x) / b(x)$ with $a, b$ of coefficients of size $\sim p^{1/2}$ instead of $p$. With $n = 4$ the norm of $s$ is $O(p^{11/2})$. Their method compute $a,b$ of norm $O(p^{7/2})$. One need to factor into small prime ideals two elements $a,b$ instead of one $s'$.
    for our record computations of discrete logarithms in $\mathbb{F}_pn$ with $2 \leqslant n \leqslant 6$, we improve the preparation of $s$, so that its norm in the number field is less than $Q$. This improves its smoothness property. Assume that we want to compute the discrete logarithm of $s$ in the larger subgroup of prime order $\ell$ of $GF(p^n)$, with $\ell$ $|$ $\Phi_np$. We decompose $s$ in $\epsilon \cdot s'$ with $\epsilon$ in a subfield or in a subgroup of order prime to $\ell$ and $s?$ with reduced coefficient size. We still have $log_g s = log_g s'$ mod $\ell$. We use a tower representation of $GF(p^n)$ with subfields for our purpose. We reduce the norm of $s \in \mathbb{F}_{p4}$ from $O(p^{11/2})$ to $O(p^{7/2}), s \in GF(p^3)$ from $O(p^6)$ to $O(p^2)$ and $s \in \mathbb{F}_{p2}$ from $O(p^4)$ to $O(p)$. This does not change the asymptotic complexity of this last step but this improves a lot its running time for small $n$.

    Codes MSC :
    11T71 - Algebraic coding theory; cryptography
    11Y16 - Algorithms; complexity
    94A60 - Cryptography

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 04/06/15
      Date de captation : 20/05/15
      Collection : Computer Science ; Number Theory
      Sous collection : Research talks
      Format : quicktime ; audio/x-aac
      Domaine : Computer Science ; Number Theory
      Durée : 00:25:52
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2015-05-20_Guillevic.mp4

    Informations sur la rencontre

    Nom de la rencontre : Arithmetics, geometry, cryptography and coding theory / Arithmétique, géométrie, cryptographie et théorie des codes
    Organisateurs de la rencontre : Bassa, Alp ; Couvreur, Alain ; Kohel, David
    Dates : 18/05/15 - 22/05/15
    Année de la rencontre : 2015
    URL Congrès : http://conferences.cirm-math.fr/1193.html

    Citation Data

    DOI : 10.24350/CIRM.V.18766803
    Cite this video as: Guillevic, Aurore (2015). Computing discrete logarithms in $GF(p^n)$: practical improvement of the individual logarithm step. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18766803
    URI : http://dx.doi.org/10.24350/CIRM.V.18766803


    1. Joux, A., Lercier, R., Smart, N., & Vercauteren, F. (2006). The number field sieve in the medium prime case. In C. Dwork (Ed.), Advances in cryptology – CRYPTO 2006 (pp. 326-344). Berlin: Springer. (Lecture Notes in Computer Science, 4117) - http://dx.doi.org/10.1007/11818175_19

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée