Index calculus in the trace zero variety

L. M. Adleman, A subexponential algorithm for discrete logarithms with applications to cryptography, in Proceedings of the 20th Annual Symposium on Foundations of Computer Science, IEEE, 1979, 55-60.doi: 10.1109/SFCS.1979.2.

L. M. Adleman, The function field sieve, in Algorithmic Number Theory (ANTS I), vol. 877 of LNCS, Springer, 1994, 108-121.doi: 10.1007/3-540-58691-1_48.

L. M. Adleman, J. DeMarrais and M.-D. A. Huang, A subexponential algorithm for discrete logrithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields, in Algorithmic Number Theory (ANTS I) (eds. L. M. Adleman and M.-D. A. Huang), vol. 877 of LNCS, Springer, 1994, 28-40.doi: 10.1007/3-540-58691-1_39.

R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Discrete Mathematics and its Applications, Chapman & Hall/CRC, Boca Raton, 2006.

R. M. Avanzi and E. Cesena, Trace zero varieties over fields of characteristic 2 for cryptographic applications, in Proceedings of the First Symposium on Algebraic Geometry and Its Applications (SAGA '07), 5 (2007), 188-215.doi: 10.1142/9789812793430_0010.

M. Bardet, J.-C. Faugère, B. Salvy and B.-Y. Yang, Asymptotic behaviour of the index of regularity of quadratic semi-regular polynomial systems, in The Effective Methods in Algebraic Geometry Conference (MEGA '05) (ed. P. Gianni), 2005, 1-14.

D. J. Bernstein, T. Lange and P. Schwabe, On the correct use of the negation map in the Pollard rho method, in Public Key Cryptography - PKC 2011 (eds. D. Catalano, N. Fazio, R. Gennaro and A. Nicolosi), vol. 6571 of LNCS, Springer, 2011, 128-146.doi: 10.1007/978-3-642-19379-8_8.

L. Bettale, J.-C. Faugère and L. Perret, Hybrid approach for solving multivariate systems over finite fields, J. Math. Cryptol., 2 (2008), 1-22.

J. W. Bos, M. E. Kaihara, T. Kleinjung, A. K. Lenstra and P. L. Montgomery, Playstation 3 computing breaks $2^{60}$ barrier: 112-bit prime ECDLP solved, Int. J. Appl. Cryptogr., 2 (2012), 212-228, Available at http://lacal.epfl.ch/112bit_prime, 2009.doi: 10.1504/IJACT.2012.045590.

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235-265.doi: 10.1006/jsco.1996.0125.

C. Bouvier, The filtering step of discrete logarithm and integer factorization algorithms, Available at http://hal.inria.fr/hal-00734654, 2012.

R. Bărbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann, Discrete logarithm in GF($2^{809}$) with FFS, in Public-Key Cryptography - PKC 2014 (ed. H. Krawczyk), vol. 8383 of LNCS, Springer, 2014, 221-238.doi: 10.1007/978-3-642-54631-0_13.

R. Bărbulescu, 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: Proceedings of EUROCRYPT '14 (eds. P. Q. Nguyen and E. Oswald), vol. 8441 of LNCS, Springer, 2014, 1-16.doi: 10.1007/978-3-642-55220-5_1.

E. Cesena, Trace Zero Varieties in Pairing-based Cryptography, PhD thesis, Università degli studi Roma Tre, Available at http://ricerca.mat.uniroma3.it/dottorato/Tesi/tesicesena.pdf, 2010.

D. Coppersmith, Fast evalution of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), 587-594.doi: 10.1109/TIT.1984.1056941.

C. Diem, The GHS attack in odd characteristic, Ramanujan Math. Soc., 18 (2003), 1-32.

C. Diem, An index calculus algorithm for plane curves of small degree, in Algorithmic Number Theory (ANTS VII) (eds. F. Hess, S. Pauli and M. Pohst), vol. 4076 of LNCS, Springer, 2006, 543-557.doi: 10.1007/11792086_38.

C. Diem, On the discrete logarithm problem in elliptic curves, Compos. Math., 147 (2011), 75-104.doi: 10.1112/S0010437X10005075.

C. Diem, On the discrete logarithm problem in elliptic curves II, Algebra & Number Theory, 7 (2013), 1281-1323.doi: 10.2140/ant.2013.7.1281.

C. Diem and S. Kochinke, Computing discrete logarithms with special linear systems, Available at http://www.math.uni-leipzig.de/~diem/preprints, 2013.

C. Diem and J. Scholten, Cover attacks - A report for the AREHCC project, Available at http://www.math.uni-leipzig.de/~diem/preprints, 2003.

C. Diem and E. Thomé, Index calculus in class groups of non-hyperelliptic curves of genus three, J. Cryptology, 21 (2008), 593-611.doi: 10.1007/s00145-007-9014-6.

E. Eberly and K. Kaltofen, On randomized Lanczos algorithms, in Proceedings of the 1997 international symposium on Symbolic and algebraic computation (ISSAC '97) (ed. W. W. Küchlin), ACM, 1997, 176-183.doi: 10.1145/258726.258776.

A. Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comp., 71 (2002), 729-742.doi: 10.1090/S0025-5718-01-01363-1.

A. Enge, Computing discrete logarithms in curves over finite fields, in Finite Fields Appl. (eds. G. L. Mullen, D. Panario and I. E. Shparlinski), vol. 461 of Contemp. Math., AMS, 2008, 119-139.doi: 10.1090/conm/461/08988.

A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith., 102 (2002), 83-103.doi: 10.4064/aa102-1-6.

A. Enge and P. Gaudry, An $L(1/3 + \varepsilon)$ algorithm for the discrete logarithm problem for low degree curves, in Advances in Cryptology: Proceedings of EUROCRYPT '07 (ed. M. Naor), vol. 4515 of LNCS, Springer, 2007, 379-393.doi: 10.1007/978-3-540-72540-4_22.

A. Enge, P. Gaudry and E. Thomé, An $L(1/3)$ discrete logarithm algorithm for low degree curves, J. Cryptology, 24 (2011), 24-41.doi: 10.1007/s00145-010-9057-y.

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139 (1999), 61-88.doi: 10.1016/S0022-4049(99)00005-5.

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC '02), ACM, 2002, 75-83.doi: 10.1145/780506.780516.

J.-C. Faugère, P. Gaudry, L. Huot and G. Renault, Using symmetries and fast change of ordering in the index calculus for elliptic curves discrete logarithm, in Proceedings of the Third International Conference on Symbolic Computation and Cryptography (SCC '12), 2012, 113-118.

J.-C. Faugère, P. Gaudry, L. Huot and G. Renault, Using symmetries in the index calculus for elliptic curves discrete logarithm, J. Cryptology, Springer, 27 (2014), 595-635.doi: 10.1007/s00145-013-9158-5.

J.-C. Faugère, P. Gianni, D. Lazard and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput., 16 (1993), 329-344.doi: 10.1006/jsco.1993.1051.

J.-C. Faugère, L. Perret, C. Petit and G. Renault, Improving the complexity of index calculus algorithms in elliptic curves over binary fields, in Advances in Cryptology: Proceedings of EUROCRYPT '12 (eds. D. Pointcheval and T. Johansson), vol. 7237 of LNCS, Springer, 2012, 27-44.doi: 10.1007/978-3-642-29011-4_4.

G. Frey, How to disguise an elliptic curve, Talk at the 2nd workshop on Elliptic Curve Cryptography (ECC '98), 1998.

G. Frey, Applications of arithmetical geometry to cryptographic constructions, in Proceedings of the 5th International Conference on Finite Fields and Applications, Springer, 2001, 128-161.

S. D. Galbraith, X. Lin and M. Scott, Endomorphisms for faster elliptic curve cryptography on a large class of curves, J. Cryptology, 24 (2011), 446-469.doi: 10.1007/s00145-010-9065-y.

S. D. Galbraith and N. P. Smart, A cryptographic application of Weil descent, in Cryptography and Coding. Proceedings of the 7th IMA International Conference (ed. M. Walker), vol. 1746 of LNCS, Springer, 1999, 191-200.doi: 10.1007/3-540-46665-7_23.

S. D. Galbraith and B. A. Smith, Discrete logarithms in generalized Jacobians, Available at http://uk.arxiv.org/abs/math.NT/0610073, 2006.

R. P. Gallant, R. J. Lambert and S. A. Vanstone, Faster point multiplication on elliptic curves with efficient endomorphisms, in Advances in Cryptology: Proceedings of CRYPTO '01 (ed. J. Kilian), vol. 2139 of LNCS, Springer, 2001, 190-200.doi: 10.1007/3-540-44647-8_11.

P. Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, in Advances in Cryptology: Proceedings of EUROCRYPT '00 (ed. B. Preneel), vol. 1807 of LNCS, Springer, 2000, 19-34.doi: 10.1007/3-540-45539-6_2.

P. Gaudry, Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symbolic Comput., 44 (2009), 1690-1702.doi: 10.1016/j.jsc.2008.08.005.

P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent, J. Cryptology, 15 (2002), 19-46.doi: 10.1007/s00145-001-0011-x.

P. Gaudry, E. Thomé, N. Thériault and C. Diem, A double large prime variation for small genus hyperelliptic index calculus, Math. Comp., 76 (2007), 475-492.doi: 10.1090/S0025-5718-06-01900-4.

J. Gerhard and J. von zur Gathen, Modern Computer Algebra, Cambridge University Press, Cambridge, 1999.

F. Göloǧlu, R. Granger, G. McGuire and J. Zumbrägel, On the function field sieve and the impact of higher splitting probabilities: Application to discrete logarithms in $\mathbbF_{2^{1971}}$, in Advances in Cryptology: Proceedings of CRYPTO '13 (eds. R. Canetti and J. A. Garay), vol. 8043 of LNCS, Springer, 2013, 109-128.doi: 10.1007/978-3-642-40084-1_7.

F. Göloǧlu, R. Granger, G. McGuire and J. Zumbrägel, Solving a 6120-bit DLP on a desktop computer, in Selected Areas in Cryptography - SAC '13 (eds. T. Lange, K. Lauter and P. Lisonĕk), LNCS, Springer, 2013, 136-152.doi: 10.1007/978-3-662-43414-7_7.

D. M. Gordon, Discrete logarithms in GF($p$) using the number field sieve, SIAM J. Discrete Math., 6 (1993), 124-138.doi: 10.1137/0406010.

E. Gorla, Torus-based cryptography, in Encyclopedia of Cryptography (eds. S. Jajodia and H. v. Tilborg), 2nd edition, Springer, Berlin-Heidelberg-New York, 2011, 1306-1308.

E. Gorla and M. Massierer, An optimal representation for the trace zero variety, Preprint, 2013.

E. Gorla and M. Massierer, Point compression for the trace zero subgroup over a small degree extension field, Des. Codes Cryptogr., Springer, 75 (2015), 335-357.doi: 10.1007/s10623-014-9921-0.

R. Granger, A. Joux and V. Vitse, New timings for oracle-assisted SDHP on the IPSEC Oakley 'well known group' 3 curve, NMBRTHRY list, available at http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1007&L=NMBRTHRY&P=R156&1=NMBRTHRY&9=A&J=on&d=No+Match 2010.

R. Granger and F. Vercauteren, On the discrete logarithm problem on algebraic tori, in Advances in Cryptology: Proceedings of CRYPTO '05 (ed. V. Shoup), vol. 3621 of LNCS, Springer, 2005, 66-85.doi: 10.1007/11535218_5.

H. Jeljeli, Accelerating iterative SpMV for discrete logarithm problem using GPUs, Arithmetic of Finite Fields, vol. 9061 of LNCS, Springer, 2015, 25-44.doi: 10.1007/978-3-319-16277-5_2.

H. Jeljeli, Resolution of linear algebra for the discrete logarithm problem using GPU and multi-core architectures, Euro-Par 2014 Parallel Processing, vol. 8632 of LNCS, Springer, 2014, 764-775.doi: 10.1007/978-3-319-09873-9_64.

A. Joux, Faster index calculus for the medium prime case: Application to 1175-bit and 1425-bit finite fields, in Advances in Cryptology: Proceedings of EUROCRYPT '13 (eds. T. Johansson and P. Nguyen), vol. 7881 of LNCS, Springer, 2013, 177-193.doi: 10.1007/978-3-642-38348-9_11.

A. Joux, A new index calculus algorithm with complexity $L(1/4 + o(1))$ in very small characteristic, in Selected Areas in Cryptography - SAC '13 (eds. T. Lange, K. Lauter and P. Lisonĕk), LNCS, Springer, 2013, 355-379.doi: 10.1007/978-3-662-43414-7_18.

A. Joux and R. Lercier, The function field sieve is quite special, in Algorithmic Number Theory (ANTS V) (eds. C. Fieker and D. R. Kohel), vol. 2369 of LNCS, Springer, 2002, 431-445.doi: 10.1007/3-540-45455-1_34.

A. Joux and R. Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method, Math. Comp., 72 (2003), 953-976.doi: 10.1090/S0025-5718-02-01482-5.

A. Joux and R. Lercier, The function field sieve in the medium prime case, in Advances in Cryptology: Proceedings of EUROCRYPT '06 (ed. S. Vaudenay), vol. 4004 of LNCS, Springer, 2006, 254-270.doi: 10.1007/11761679_16.

A. Joux and V. Vitse, A variant of the F4 algorithm, in Topics in cryptology CT-RSA 2011, vol. 6558 of LNCS, Springer, 2011, 356-375.doi: 10.1007/978-3-642-19074-2_23.

A. Joux and V. Vitse, Elliptic curve discrete logarithm problem over small degree extension fields. Application to the static Diffie-Hellman problem on $E(\mathbbF_{q^5})$, J. Cryptology, Springer, 26 (2013), 119-143.doi: 10.1007/s00145-011-9116-z.

N. Koblitz, CM-curves with good cryptographic properties, in Advances in Cryptology: Proceedings of CRYPTO '91 (ed. J. Feigenbaum), vol. 576 of LNCS, Springer, 2001, 179-287.doi: 10.1007/3-540-46766-1_22.

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1, Springer, Berlin-Heidelberg-New York, 2000.doi: 10.1007/978-3-540-70628-1.

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer, Berlin-Heidelberg-New York, 2005.doi: 10.1007/3-540-28296-3.

B. A. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, in Advances in Cryptology: Proceedings of CRYPTO '90 (eds. A. J. Menezes and S. A. Vanstone), vol. 537 of LNCS, Springer, 1990, 109-133.doi: 10.1007/3-540-38424-3_8.

T. Lange, Efficient Arithmetic on Hyperelliptic Curves, PhD thesis, Univerität GHS Essen, Available at http://www.hyperelliptic.org/tanja/preprints.html, 2001.

T. Lange, Trace zero subvarieties of genus 2 curves for cryptosystem, Ramanujan Math. Soc., 19 (2004), 15-33.

K. Nagao, Decomposition attack for the Jacobian of a hyperelliptic curve over an extension field, in Algorithmic Number Theory (ANTS IX) (eds. G. Hanrot, F. Morain and E. Thomé), vol. 6197 of LNCS, Springer, 2010, 285-300.doi: 10.1007/978-3-642-14518-6_23.

C. Petit and J. Quisquater, On polynomial systems arising from a Weil descent, in Advances in Cryptology: Proceedings of ASIACRYPT '12 (eds. X. Wang and K. Sako), vol. 7658 of LNCS, Springer, 2012, 451-466.doi: 10.1007/978-3-642-34961-4_28.

K. Rubin and A. Silverberg, Supersingular abelian varieties in cryptology, in Advances in Cryptology: Proceedings of CRYPTO '02 (ed. M. Yung), vol. 2442 of LNCS, Springer, 2002, 336-353.doi: 10.1007/3-540-45708-9_22.

K. Rubin and A. Silverberg, Using abelian varieties to improve pairing-based cryptography, J. Cryptology, 22 (2009), 330-364.doi: 10.1007/s00145-008-9022-1.

O. Schirokauer, The special function field sieve, SIAM J. Discrete Math., 16 (2002), 81-98.doi: 10.1137/S0895480100372668.

I. Semaev, Summation polynomials of the discrete logarithm problem on elliptic curves, Available at http://eprint.iacr.org/2004/031, 2004.

M. Shantz and E. Teske, Solving the elliptic curve discrete logarithm problem using Semaev polynomials, Weil descent and Gröbner basis methods - an experimental study, Number Theory and Cryptography, vol. 8260 of LNCS, Springer, 2013, 94-107.doi: 10.1007/978-3-642-42001-6_7.

N. Thériault, Index calculus attack for hyperelliptic curves of small genus, in Advances in Cryptology: Proceedings of ASIACRYPT '03 (ed. C. S. Laih), vol. 2894 of LNCS, Springer, 2003, 75-92.doi: 10.1007/978-3-540-40061-5_5.

C. Traverso, Gröbner trace algorithms, in Proceedings of the 1988 international symposium on Symbolic and algebraic computation (ISSAC '88), vol. 358 of LNCS, Springer, 1989, 125-138.doi: 10.1007/3-540-51084-2_12.

M. D. Velichka, M. J. Jacobson, Jr. and A. Stein, Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields, Math. Comp., 83 (2014), 935-963.doi: 10.1090/S0025-5718-2013-02748-2.

D. H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, 32 (1986), 54-62.doi: 10.1109/TIT.1986.1057137.

B.-Y. Yang, J.-M. Chen and N. T. Courtois, On asymptotic security estimates in XL and Gröbner bases-related algebraic cryptanalysis, in Information and Communications Security (ICICS '04) (eds. J. López, S. Qing and E. Okamoto), vol. 3269 of LNCS, Springer, 2004, 401-413.doi: 10.1007/978-3-540-30191-2_31.