November  2015, 9(4): 515-539. doi: 10.3934/amc.2015.9.515

Index calculus in the trace zero variety

1. 

Institut de Mathématiques, Université de Neuchâtel, Rue Emile-Argand 11, 2000 Neuchâtel

2. 

Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland

Received  April 2014 Published  November 2015

We discuss how to apply Gaudry's index calculus algorithm for abelian varieties to solve the discrete logarithm problem in the trace zero variety of an elliptic curve. We treat in particular the practically relevant cases of field extensions of degree 3 or 5. Our theoretical analysis is compared to other algorithms present in the literature, and is complemented by results from a prototype implementation.
Citation: Elisa Gorla, Maike Massierer. Index calculus in the trace zero variety. Advances in Mathematics of Communications, 2015, 9 (4) : 515-539. doi: 10.3934/amc.2015.9.515
References:
[1]

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.

[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.

[3]

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.

[4]

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.

[5]

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.

[6]

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.

[7]

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.

[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.

[9]

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.

[10]

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.

[11]

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

[12]

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.

[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.

[14]

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.

[15]

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.

[16]

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

[17]

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.

[18]

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

[19]

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.

[20]

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

[21]

C. Diem and J. Scholten, An attack on a trace-zero cryptosystem, Available at http://www.math.uni-leipzig.de/~diem/preprints.

[22]

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

[23]

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.

[24]

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.

[25]

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.

[26]

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.

[27]

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.

[28]

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.

[29]

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.

[30]

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.

[31]

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.

[32]

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.

[33]

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.

[34]

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.

[35]

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.

[36]

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

[37]

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.

[38]

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.

[39]

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.

[40]

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

[41]

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.

[42]

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.

[43]

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.

[44]

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.

[45]

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.

[46]

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

[47]

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.

[48]

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.

[49]

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.

[50]

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.

[51]

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

[52]

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.

[53]

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.

[54]

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.

[55]

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.

[56]

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.

[57]

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.

[58]

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.

[59]

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.

[60]

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.

[61]

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.

[62]

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.

[63]

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.

[64]

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.

[65]

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

[66]

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

[67]

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.

[68]

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

[69]

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

[70]

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.

[71]

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.

[72]

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.

[73]

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.

[74]

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

[75]

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

[76]

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.

[77]

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.

[78]

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.

[79]

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.

[80]

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

[81]

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.

show all references

References:
[1]

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.

[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.

[3]

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.

[4]

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.

[5]

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.

[6]

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.

[7]

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.

[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.

[9]

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.

[10]

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.

[11]

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

[12]

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.

[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.

[14]

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.

[15]

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.

[16]

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

[17]

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.

[18]

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

[19]

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.

[20]

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

[21]

C. Diem and J. Scholten, An attack on a trace-zero cryptosystem, Available at http://www.math.uni-leipzig.de/~diem/preprints.

[22]

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

[23]

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.

[24]

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.

[25]

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.

[26]

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.

[27]

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.

[28]

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.

[29]

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.

[30]

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.

[31]

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.

[32]

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.

[33]

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.

[34]

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.

[35]

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.

[36]

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

[37]

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.

[38]

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.

[39]

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.

[40]

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

[41]

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.

[42]

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.

[43]

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.

[44]

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.

[45]

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.

[46]

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

[47]

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.

[48]

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.

[49]

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.

[50]

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.

[51]

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

[52]

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.

[53]

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.

[54]

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.

[55]

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.

[56]

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.

[57]

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.

[58]

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.

[59]

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.

[60]

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.

[61]

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.

[62]

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.

[63]

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.

[64]

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.

[65]

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

[66]

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

[67]

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.

[68]

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

[69]

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

[70]

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.

[71]

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.

[72]

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.

[73]

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.

[74]

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

[75]

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

[76]

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.

[77]

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.

[78]

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.

[79]

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.

[80]

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

[81]

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.

[1]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169

[2]

Roberto Avanzi, Nicolas Thériault. A filtering method for the hyperelliptic curve index calculus and its analysis. Advances in Mathematics of Communications, 2010, 4 (2) : 189-213. doi: 10.3934/amc.2010.4.189

[3]

Ketty A. De Rezende, Mariana G. Villapouca. Discrete conley index theory for zero dimensional basic sets. Discrete and Continuous Dynamical Systems, 2017, 37 (3) : 1359-1387. doi: 10.3934/dcds.2017056

[4]

Steven D. Galbraith, Ping Wang, Fangguo Zhang. Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm. Advances in Mathematics of Communications, 2017, 11 (3) : 453-469. doi: 10.3934/amc.2017038

[5]

Santos González, Llorenç Huguet, Consuelo Martínez, Hugo Villafañe. Discrete logarithm like problems and linear recurring sequences. Advances in Mathematics of Communications, 2013, 7 (2) : 187-195. doi: 10.3934/amc.2013.7.187

[6]

Koray Karabina, Berkant Ustaoglu. Invalid-curve attacks on (hyper)elliptic curve cryptosystems. Advances in Mathematics of Communications, 2010, 4 (3) : 307-321. doi: 10.3934/amc.2010.4.307

[7]

Viviana Alejandra Díaz, David Martín de Diego. Generalized variational calculus for continuous and discrete mechanical systems. Journal of Geometric Mechanics, 2018, 10 (4) : 373-410. doi: 10.3934/jgm.2018014

[8]

Robert Skiba, Nils Waterstraat. The index bundle and multiparameter bifurcation for discrete dynamical systems. Discrete and Continuous Dynamical Systems, 2017, 37 (11) : 5603-5629. doi: 10.3934/dcds.2017243

[9]

Uriel Kaufmann, Humberto Ramos Quoirin, Kenichiro Umezu. A curve of positive solutions for an indefinite sublinear Dirichlet problem. Discrete and Continuous Dynamical Systems, 2020, 40 (2) : 817-845. doi: 10.3934/dcds.2020063

[10]

C. Davini, F. Jourdan. Approximations of degree zero in the Poisson problem. Communications on Pure and Applied Analysis, 2005, 4 (2) : 267-281. doi: 10.3934/cpaa.2005.4.267

[11]

Rama Ayoub, Aziz Hamdouni, Dina Razafindralandy. A new Hodge operator in discrete exterior calculus. Application to fluid mechanics. Communications on Pure and Applied Analysis, 2021, 20 (6) : 2155-2185. doi: 10.3934/cpaa.2021062

[12]

Jacky Cresson, Fernando Jiménez, Sina Ober-Blöbaum. Continuous and discrete Noether's fractional conserved quantities for restricted calculus of variations. Journal of Geometric Mechanics, 2022, 14 (1) : 57-89. doi: 10.3934/jgm.2021012

[13]

Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, Sekung Hong. Speeding up regular elliptic curve scalar multiplication without precomputation. Advances in Mathematics of Communications, 2020, 14 (4) : 703-726. doi: 10.3934/amc.2020090

[14]

Pradeep Boggarapu, Luz Roncal, Sundaram Thangavelu. On extension problem, trace Hardy and Hardy's inequalities for some fractional Laplacians. Communications on Pure and Applied Analysis, 2019, 18 (5) : 2575-2605. doi: 10.3934/cpaa.2019116

[15]

Madhurima Mukhopadhyay, Palash Sarkar, Shashank Singh, Emmanuel Thomé. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications, 2022, 16 (3) : 449-464. doi: 10.3934/amc.2020119

[16]

Jochen Brüning, Franz W. Kamber, Ken Richardson. The equivariant index theorem for transversally elliptic operators and the basic index theorem for Riemannian foliations. Electronic Research Announcements, 2010, 17: 138-154. doi: 10.3934/era.2010.17.138

[17]

Kai-Seng Chou, Ying-Chuen Kwong. General initial data for a class of parabolic equations including the curve shortening problem. Discrete and Continuous Dynamical Systems, 2020, 40 (5) : 2963-2986. doi: 10.3934/dcds.2020157

[18]

Philip Korman. Infinitely many solutions and Morse index for non-autonomous elliptic problems. Communications on Pure and Applied Analysis, 2020, 19 (1) : 31-46. doi: 10.3934/cpaa.2020003

[19]

Kung-Ching Chang, Zhi-Qiang Wang, Tan Zhang. On a new index theory and non semi-trivial solutions for elliptic systems. Discrete and Continuous Dynamical Systems, 2010, 28 (2) : 809-826. doi: 10.3934/dcds.2010.28.809

[20]

Zongming Guo, Zhongyuan Liu, Juncheng Wei, Feng Zhou. Bifurcations of some elliptic problems with a singular nonlinearity via Morse index. Communications on Pure and Applied Analysis, 2011, 10 (2) : 507-525. doi: 10.3934/cpaa.2011.10.507

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (105)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]