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, (1979), 55. doi: 10.1109/SFCS.1979.2. Google Scholar

[2]

L. M. Adleman, The function field sieve,, in Algorithmic Number Theory (ANTS I), (1994), 108. doi: 10.1007/3-540-58691-1_48. Google Scholar

[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), (1994), 28. doi: 10.1007/3-540-58691-1_39. Google Scholar

[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, (2006). Google Scholar

[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. doi: 10.1142/9789812793430_0010. Google Scholar

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

[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, (2011), 128. doi: 10.1007/978-3-642-19379-8_8. Google Scholar

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

[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. doi: 10.1504/IJACT.2012.045590. Google Scholar

[10]

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

[11]

C. Bouvier, The filtering step of discrete logarithm and integer factorization algorithms,, Available at , (2012). Google Scholar

[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), (2014), 221. doi: 10.1007/978-3-642-54631-0_13. Google Scholar

[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), (8441), 1. doi: 10.1007/978-3-642-55220-5_1. Google Scholar

[14]

E. Cesena, Trace Zero Varieties in Pairing-based Cryptography,, PhD thesis, (2010). Google Scholar

[15]

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

[16]

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

[17]

C. Diem, An index calculus algorithm for plane curves of small degree,, in Algorithmic Number Theory (ANTS VII) (eds. F. Hess, (4076), 543. doi: 10.1007/11792086_38. Google Scholar

[18]

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

[19]

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

[20]

C. Diem and S. Kochinke, Computing discrete logarithms with special linear systems,, Available at , (2013). Google Scholar

[21]

C. Diem and J. Scholten, An attack on a trace-zero cryptosystem,, Available at , (). Google Scholar

[22]

C. Diem and J. Scholten, Cover attacks - A report for the AREHCC project,, Available at , (2003). Google Scholar

[23]

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

[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), (1997), 176. doi: 10.1145/258726.258776. Google Scholar

[25]

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

[26]

A. Enge, Computing discrete logarithms in curves over finite fields,, in Finite Fields Appl. (eds. G. L. Mullen, (2008), 119. doi: 10.1090/conm/461/08988. Google Scholar

[27]

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

[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), (4515), 379. doi: 10.1007/978-3-540-72540-4_22. Google Scholar

[29]

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

[30]

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

[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), (2002), 75. doi: 10.1145/780506.780516. Google Scholar

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

[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, 27 (2014), 595. doi: 10.1007/s00145-013-9158-5. Google Scholar

[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. doi: 10.1006/jsco.1993.1051. Google Scholar

[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), (7237), 27. doi: 10.1007/978-3-642-29011-4_4. Google Scholar

[36]

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

[37]

G. Frey, Applications of arithmetical geometry to cryptographic constructions,, in Proceedings of the 5th International Conference on Finite Fields and Applications, (2001), 128. Google Scholar

[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. doi: 10.1007/s00145-010-9065-y. Google Scholar

[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), (1746), 191. doi: 10.1007/3-540-46665-7_23. Google Scholar

[40]

S. D. Galbraith and B. A. Smith, Discrete logarithms in generalized Jacobians,, Available at , (2006). Google Scholar

[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), (2139), 190. doi: 10.1007/3-540-44647-8_11. Google Scholar

[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), (1807), 19. doi: 10.1007/3-540-45539-6_2. Google Scholar

[43]

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

[44]

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

[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. doi: 10.1090/S0025-5718-06-01900-4. Google Scholar

[46]

J. Gerhard and J. von zur Gathen, Modern Computer Algebra,, Cambridge University Press, (1999). Google Scholar

[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), (8043), 109. doi: 10.1007/978-3-642-40084-1_7. Google Scholar

[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, (2013), 136. doi: 10.1007/978-3-662-43414-7_7. Google Scholar

[49]

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

[50]

E. Gorla, Torus-based cryptography,, in Encyclopedia of Cryptography (eds. S. Jajodia and H. v. Tilborg), (2011), 1306. Google Scholar

[51]

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

[52]

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

[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, (2010). Google Scholar

[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), (3621), 66. doi: 10.1007/11535218_5. Google Scholar

[55]

H. Jeljeli, Accelerating iterative SpMV for discrete logarithm problem using GPUs,, Arithmetic of Finite Fields, (9061), 25. doi: 10.1007/978-3-319-16277-5_2. Google Scholar

[56]

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

[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), (7881), 177. doi: 10.1007/978-3-642-38348-9_11. Google Scholar

[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, (2013), 355. doi: 10.1007/978-3-662-43414-7_18. Google Scholar

[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), (2369), 431. doi: 10.1007/3-540-45455-1_34. Google Scholar

[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. doi: 10.1090/S0025-5718-02-01482-5. Google Scholar

[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), (4004), 254. doi: 10.1007/11761679_16. Google Scholar

[62]

A. Joux and V. Vitse, A variant of the F4 algorithm,, in Topics in cryptology CT-RSA 2011, (2011), 356. doi: 10.1007/978-3-642-19074-2_23. Google Scholar

[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, 26 (2013), 119. doi: 10.1007/s00145-011-9116-z. Google Scholar

[64]

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

[65]

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1,, Springer, (2000). doi: 10.1007/978-3-540-70628-1. Google Scholar

[66]

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2,, Springer, (2005). doi: 10.1007/3-540-28296-3. Google Scholar

[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), (1990), 109. doi: 10.1007/3-540-38424-3_8. Google Scholar

[68]

T. Lange, Efficient Arithmetic on Hyperelliptic Curves,, PhD thesis, (2001). Google Scholar

[69]

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

[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, (6197), 285. doi: 10.1007/978-3-642-14518-6_23. Google Scholar

[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), (7658), 451. doi: 10.1007/978-3-642-34961-4_28. Google Scholar

[72]

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

[73]

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

[74]

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

[75]

I. Semaev, Summation polynomials of the discrete logarithm problem on elliptic curves,, Available at , (2004). Google Scholar

[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, (8260), 94. doi: 10.1007/978-3-642-42001-6_7. Google Scholar

[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), (2894), 75. doi: 10.1007/978-3-540-40061-5_5. Google Scholar

[78]

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

[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. doi: 10.1090/S0025-5718-2013-02748-2. Google Scholar

[80]

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

[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, (3269), 401. doi: 10.1007/978-3-540-30191-2_31. Google Scholar

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, (1979), 55. doi: 10.1109/SFCS.1979.2. Google Scholar

[2]

L. M. Adleman, The function field sieve,, in Algorithmic Number Theory (ANTS I), (1994), 108. doi: 10.1007/3-540-58691-1_48. Google Scholar

[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), (1994), 28. doi: 10.1007/3-540-58691-1_39. Google Scholar

[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, (2006). Google Scholar

[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. doi: 10.1142/9789812793430_0010. Google Scholar

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

[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, (2011), 128. doi: 10.1007/978-3-642-19379-8_8. Google Scholar

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

[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. doi: 10.1504/IJACT.2012.045590. Google Scholar

[10]

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

[11]

C. Bouvier, The filtering step of discrete logarithm and integer factorization algorithms,, Available at , (2012). Google Scholar

[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), (2014), 221. doi: 10.1007/978-3-642-54631-0_13. Google Scholar

[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), (8441), 1. doi: 10.1007/978-3-642-55220-5_1. Google Scholar

[14]

E. Cesena, Trace Zero Varieties in Pairing-based Cryptography,, PhD thesis, (2010). Google Scholar

[15]

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

[16]

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

[17]

C. Diem, An index calculus algorithm for plane curves of small degree,, in Algorithmic Number Theory (ANTS VII) (eds. F. Hess, (4076), 543. doi: 10.1007/11792086_38. Google Scholar

[18]

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

[19]

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

[20]

C. Diem and S. Kochinke, Computing discrete logarithms with special linear systems,, Available at , (2013). Google Scholar

[21]

C. Diem and J. Scholten, An attack on a trace-zero cryptosystem,, Available at , (). Google Scholar

[22]

C. Diem and J. Scholten, Cover attacks - A report for the AREHCC project,, Available at , (2003). Google Scholar

[23]

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

[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), (1997), 176. doi: 10.1145/258726.258776. Google Scholar

[25]

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

[26]

A. Enge, Computing discrete logarithms in curves over finite fields,, in Finite Fields Appl. (eds. G. L. Mullen, (2008), 119. doi: 10.1090/conm/461/08988. Google Scholar

[27]

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

[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), (4515), 379. doi: 10.1007/978-3-540-72540-4_22. Google Scholar

[29]

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

[30]

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

[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), (2002), 75. doi: 10.1145/780506.780516. Google Scholar

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

[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, 27 (2014), 595. doi: 10.1007/s00145-013-9158-5. Google Scholar

[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. doi: 10.1006/jsco.1993.1051. Google Scholar

[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), (7237), 27. doi: 10.1007/978-3-642-29011-4_4. Google Scholar

[36]

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

[37]

G. Frey, Applications of arithmetical geometry to cryptographic constructions,, in Proceedings of the 5th International Conference on Finite Fields and Applications, (2001), 128. Google Scholar

[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. doi: 10.1007/s00145-010-9065-y. Google Scholar

[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), (1746), 191. doi: 10.1007/3-540-46665-7_23. Google Scholar

[40]

S. D. Galbraith and B. A. Smith, Discrete logarithms in generalized Jacobians,, Available at , (2006). Google Scholar

[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), (2139), 190. doi: 10.1007/3-540-44647-8_11. Google Scholar

[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), (1807), 19. doi: 10.1007/3-540-45539-6_2. Google Scholar

[43]

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

[44]

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

[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. doi: 10.1090/S0025-5718-06-01900-4. Google Scholar

[46]

J. Gerhard and J. von zur Gathen, Modern Computer Algebra,, Cambridge University Press, (1999). Google Scholar

[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), (8043), 109. doi: 10.1007/978-3-642-40084-1_7. Google Scholar

[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, (2013), 136. doi: 10.1007/978-3-662-43414-7_7. Google Scholar

[49]

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

[50]

E. Gorla, Torus-based cryptography,, in Encyclopedia of Cryptography (eds. S. Jajodia and H. v. Tilborg), (2011), 1306. Google Scholar

[51]

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

[52]

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

[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, (2010). Google Scholar

[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), (3621), 66. doi: 10.1007/11535218_5. Google Scholar

[55]

H. Jeljeli, Accelerating iterative SpMV for discrete logarithm problem using GPUs,, Arithmetic of Finite Fields, (9061), 25. doi: 10.1007/978-3-319-16277-5_2. Google Scholar

[56]

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

[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), (7881), 177. doi: 10.1007/978-3-642-38348-9_11. Google Scholar

[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, (2013), 355. doi: 10.1007/978-3-662-43414-7_18. Google Scholar

[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), (2369), 431. doi: 10.1007/3-540-45455-1_34. Google Scholar

[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. doi: 10.1090/S0025-5718-02-01482-5. Google Scholar

[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), (4004), 254. doi: 10.1007/11761679_16. Google Scholar

[62]

A. Joux and V. Vitse, A variant of the F4 algorithm,, in Topics in cryptology CT-RSA 2011, (2011), 356. doi: 10.1007/978-3-642-19074-2_23. Google Scholar

[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, 26 (2013), 119. doi: 10.1007/s00145-011-9116-z. Google Scholar

[64]

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

[65]

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1,, Springer, (2000). doi: 10.1007/978-3-540-70628-1. Google Scholar

[66]

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2,, Springer, (2005). doi: 10.1007/3-540-28296-3. Google Scholar

[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), (1990), 109. doi: 10.1007/3-540-38424-3_8. Google Scholar

[68]

T. Lange, Efficient Arithmetic on Hyperelliptic Curves,, PhD thesis, (2001). Google Scholar

[69]

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

[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, (6197), 285. doi: 10.1007/978-3-642-14518-6_23. Google Scholar

[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), (7658), 451. doi: 10.1007/978-3-642-34961-4_28. Google Scholar

[72]

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

[73]

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

[74]

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

[75]

I. Semaev, Summation polynomials of the discrete logarithm problem on elliptic curves,, Available at , (2004). Google Scholar

[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, (8260), 94. doi: 10.1007/978-3-642-42001-6_7. Google Scholar

[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), (2894), 75. doi: 10.1007/978-3-540-40061-5_5. Google Scholar

[78]

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

[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. doi: 10.1090/S0025-5718-2013-02748-2. Google Scholar

[80]

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

[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, (3269), 401. doi: 10.1007/978-3-540-30191-2_31. Google Scholar

[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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 2017, 37 (11) : 5603-5629. doi: 10.3934/dcds.2017243

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Katsutoshi Shinohara. On the index problem of $C^1$-generic wild homoclinic classes in dimension three. Discrete & Continuous Dynamical Systems - A, 2011, 31 (3) : 913-940. doi: 10.3934/dcds.2011.31.913

[16]

Khadijah Sharaf. A perturbation result for a critical elliptic equation with zero Dirichlet boundary condition. Discrete & Continuous Dynamical Systems - A, 2017, 37 (3) : 1691-1706. doi: 10.3934/dcds.2017070

[17]

Meiyue Jiang, Juncheng Wei. $2\pi$-Periodic self-similar solutions for the anisotropic affine curve shortening problem II. Discrete & Continuous Dynamical Systems - A, 2016, 36 (2) : 785-803. doi: 10.3934/dcds.2016.36.785

[18]

Nikos Katzourakis. Nonuniqueness in vector-valued calculus of variations in $L^\infty$ and some Linear elliptic systems. Communications on Pure & Applied Analysis, 2015, 14 (1) : 313-327. doi: 10.3934/cpaa.2015.14.313

[19]

Nikos Katzourakis. Corrigendum to the paper: Nonuniqueness in Vector-Valued Calculus of Variations in $ L^\infty $ and some Linear Elliptic Systems. Communications on Pure & Applied Analysis, 2019, 18 (4) : 2197-2198. doi: 10.3934/cpaa.2019098

[20]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]