Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms

Antoine Joux; Cécile Pierrot

doi:10.3934/amc.2022085

Article Contents

2024, Volume 18, Issue 5: 1266-1302. Doi: 10.3934/amc.2022085

This issue Previous Article Improved lower bounds for self-dual codes over $ \mathbb{F}_{11} $, $ \mathbb{F}_{13} $, $ \mathbb{F}_{17} $, $ \mathbb{F}_{19} $ and $ \mathbb{F}_{23} $ Next Article On the symmetric 2-adic complexity of periodic binary sequences

Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms

Antoine Joux^{1, 2, ,} and
Cécile Pierrot^3,

1.
CISPA Helmholtz Center for Information Security Saarbrücken, Germany
2.
Sorbonne Université, Institut de Mathématiques de Jussieu–Paris Rive Gauche, CNRS, INRIA, Univ Paris Diderot. Campus Pierre et Marie Curie, F-75005, Paris, France
3.
Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

^*Corresponding author
^*Corresponding author

Received: November 2021

Revised: October 2022

Early access: November 2022

Published: October 2024

This work has been supported in part by the European Union as H2020 Programme under grant agreement number ERC-669891.

Abstract / Introduction Full Text(HTML) Figure(4) / Table(2) Related Papers Cited by

Abstract

Elliptic bases, introduced by Couveignes and Lercier in 2009, give an elegant way of representing finite field extensions. A natural question which seems to have been considered independently by several groups is to use this representation as a starting point for discrete logarithm algorithms in small characteristic finite fields.

This idea has been recently proposed by two groups working on it, in order to achieve provable quasi-polynomial time for discrete logarithms in small characteristic finite fields.

In this paper, we do not try to achieve a provable algorithm but, instead, investigate the practicality of heuristic algorithms based on elliptic bases. Our key idea is to use a different model of the elliptic curve used for the elliptic basis that allows for a relatively simple adaptation of the techniques used with former Frobenius representation algorithms.

We have not performed any record computation with this new method but our experiments with the field $ {\mathbb F}_{3^{1345}} $ indicate that switching to elliptic representations might be possible with performances comparable to the current best practical methods.

Keywords:

Mathematics Subject Classification: Primary: 11Y16, 12Y05; Secondary: 11G20.

Citation:

Full Text(HTML)

Figure 1. Frobenius action on the point $ F \in {\mathscr E}/ {\mathbb F}_{q^k} $

Download: Full-size image PowerPoint slide

Figure 2. Commutative diagram of our algorithm

Download: Full-size image PowerPoint slide

Figure 3. Tower of extensions over the base field $ {\mathbb F}_q $ in the classical zig-zag descent.

Download: Full-size image PowerPoint slide

Figure 4. Tower of elliptic curves extensions in the elliptic zig-zag descent. The path in green represents how we decompose $ p_z $ in smaller degree places over higher extensions during the algorithm

Download: Full-size image PowerPoint slide

Table 1. Some functions of $ {\mathbb F}_q[ {\mathscr C}] $ and their height in $ {\mathscr E} $

Functions of $ {\mathscr C} $	Height of the associated divisors in $ {\mathscr E} $
1	0
$ U,\,V,\,W$	2
$UV, \, VW, \, UW$	4
$U+V, \, V+W, \, U+W$	4
$U^tV, \, UV^t$	$2t+2$
$U^tV+UV^t$	$\hbox{at most } 2t+2$
$U^tV^{t+1}W, \, UV^{t+1}W^t, \, U^tV^2W^t, \, U V^{2t}W$	$4t+4$

| Show Table

DownLoad: CSV

Table 2. Functions appearing on both side of the diagram, and their corresponding heights in $ {\mathscr E} $. $ A $ and $ B $ are linear combinations of monomials from $ \mathcal{M}_t $

Functions of $ {\mathscr C} $	Height of the associated divisors in $ {\mathscr E} $
$A(U,V) - \alpha B(U,V) \quad\hbox{ where } \alpha \in {\mathbb F}_q$	$\hbox{at most } 4t$
$A(V,W)B(U,V) -A(U,V)B(V,W)$	$\hbox{at most } 8t $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	L. M. Adleman and M.-D. A. Huang, Function field sieve method for discrete logarithms over finite fields, Inf. Comput., 151 (1999), 5-16. doi: 10.1006/inco.1998.2761.
[2]	R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, In Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, 1-16, 2014. doi: 10.1007/978-3-642-55220-5_1.
[3]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language,Computational algebra and number theory (London, 1993), J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[4]	H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercauteren, editors, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2005. doi: 10.1201/9781420034981.
[5]	J.-M. Couveignes and R. Lercier, Elliptic periods for finite fields, Finite Fields and Their Applications, 15 (2009), 1-22. doi: 10.1016/j.ffa.2008.07.004.
[6]	F. Göloglu and A. Joux, A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms, Math. Comp., 88 (2019), 2485-2496. doi: 10.1090/mcom/3404.
[7]	R. Granger, T. Kleinjung and J. Zumbrägel, On the powers of 2, IACR Cryptology ePrint Archive, 2014 (2014), 300.
[8]	R. Granger, T. Kleinjung and J. Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Trans. Amer. Math. Soc., 370 (2018), 3129-3145. doi: 10.1090/tran/7027.
[9]	A. Joux and C. Pierrot, Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms - simplified setting for small characteristic finite fields, In Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, 2014,378-397. doi: 10.1007/978-3-662-45611-8_20.
[10]	A. Joux and C. Pierrot, Technical history of discrete logarithms in small characteristic finite fields - the road from subexponential to quasi-polynomial complexity, Des. Codes Cryptogr., 78 (2016), 73-85. doi: 10.1007/s10623-015-0147-6.
[11]	T. Kleinjung and B. Wesolowski, A new perspective on the powers of two descent for discrete logarithms in finite fields, IACR Cryptology ePrint Archive, 2018,647.
[12]	T. Kleinjung and B. Wesolowski, Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic, J. Amer. Math. Soc., 35 (2022), 581-624, Cryptology ePrint Archive, Report, 2019/751, 2019, https://eprint.iacr.org/2019/751. doi: 10.1090/jams/985.
[13]	T. Kleinjung and B. Wesolowski, Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic, Journal of the American Mathematical Society, 35 (2022), 581-624. doi: 10.1090/jams/985.
[14]	G. Lido, Discrete logarithm over finite fields of small characteristic, Master's thesis, Universita di Pisa, September 2016. Available from https://etd.adm.unipi.it/t/etd-08312016-225452.
[15]	G. Lido, Discrete logarithm over finite fields of small characteristic, Unpublished (personal communication), 2019.
[16]	G. Lido, A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic, 2022.
[17]	G. Micheli, On the selection of polynomials for the dlp quasi-polynomial time algorithm for finite fields of small characteristic, SIAM Journal on Applied Algebra and Geometry, 3 (2019), 256-265. doi: 10.1137/18M1177196.
[18]	V. S. Miller, The Weil pairing, and its efficient calculation, J. Cryptology, 17 (2004), 235-261. doi: 10.1007/s00145-004-0315-8.
[19]	S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.), IEEE Transactions on Information Theory, 24 (1978), 106-110. doi: 10.1109/tit.1978.1055817.
[20]	C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, In Discrete Algorithms and Complexity, 1987,119-143.
[21]	H. Stichtenoth, Algebraic Function Fields and Codes, Springer Publishing Company, Incorporated, 2nd edition, 2008.
[22]	E. Ughi, On the number of points of elliptic curves over a finite field and a problem of B. Segre, European Journal of Combinatorics, 4 (1983), 263-270. doi: 10.1016/S0195-6698(83)80021-3.
[23]	D. Wan, Generators and irreducible polynomials over finite fields, Mathematics of Computation, 66 (1997), 1195-1212. doi: 10.1090/S0025-5718-97-00835-1.
[24]	W. C. Waterhouse, Abelian varieties over finite fields, Annales Scientifiques de l'Ecole Normale Supérieure, 2 (1969), 521-560. doi: 10.24033/asens.1183.