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.

[2]

L. M. Adleman, The function field sieve,, in Algorithmic Number Theory (ANTS I), (1994), 108. 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), (1994), 28. 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, (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. 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.

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

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

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

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

[11]

C. Bouvier, The filtering step of discrete logarithm and integer factorization algorithms,, Available at , (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), (2014), 221. 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), (8441), 1. doi: 10.1007/978-3-642-55220-5_1.

[14]

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

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

[16]

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

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

[18]

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

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

[20]

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

[21]

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

[22]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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, (2001), 128.

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

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

[40]

S. D. Galbraith and B. A. Smith, Discrete logarithms in generalized Jacobians,, Available at , (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), (2139), 190. 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), (1807), 19. 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. 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. 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. doi: 10.1090/S0025-5718-06-01900-4.

[46]

J. Gerhard and J. von zur Gathen, Modern Computer Algebra,, Cambridge University Press, (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), (8043), 109. 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, (2013), 136. 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. doi: 10.1137/0406010.

[50]

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

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

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

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

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

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

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

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

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

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

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

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

[65]

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

[66]

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2,, Springer, (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), (1990), 109. doi: 10.1007/3-540-38424-3_8.

[68]

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

[69]

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

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

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

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

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

[74]

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

[75]

I. Semaev, Summation polynomials of the discrete logarithm problem on elliptic curves,, Available at , (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, (8260), 94. 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), (2894), 75. 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), (1988), 125. 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. 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. 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, (3269), 401. 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, (1979), 55. doi: 10.1109/SFCS.1979.2.

[2]

L. M. Adleman, The function field sieve,, in Algorithmic Number Theory (ANTS I), (1994), 108. 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), (1994), 28. 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, (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. 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.

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

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

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

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

[11]

C. Bouvier, The filtering step of discrete logarithm and integer factorization algorithms,, Available at , (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), (2014), 221. 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), (8441), 1. doi: 10.1007/978-3-642-55220-5_1.

[14]

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

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

[16]

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

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

[18]

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

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

[20]

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

[21]

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

[22]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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, (2001), 128.

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

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

[40]

S. D. Galbraith and B. A. Smith, Discrete logarithms in generalized Jacobians,, Available at , (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), (2139), 190. 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), (1807), 19. 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. 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. 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. doi: 10.1090/S0025-5718-06-01900-4.

[46]

J. Gerhard and J. von zur Gathen, Modern Computer Algebra,, Cambridge University Press, (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), (8043), 109. 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, (2013), 136. 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. doi: 10.1137/0406010.

[50]

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

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

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

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

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

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

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

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

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

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

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

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

[65]

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

[66]

M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2,, Springer, (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), (1990), 109. doi: 10.1007/3-540-38424-3_8.

[68]

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

[69]

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

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

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

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

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

[74]

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

[75]

I. Semaev, Summation polynomials of the discrete logarithm problem on elliptic curves,, Available at , (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, (8260), 94. 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), (2894), 75. 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), (1988), 125. 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. 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. 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, (3269), 401. 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 & 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]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

Jayadev S. Athreya, Gregory A. Margulis. Logarithm laws for unipotent flows, Ⅱ. Journal of Modern Dynamics, 2017, 11: 1-16. doi: 10.3934/jmd.2017001

[17]

J. S. Athreya, Anish Ghosh, Amritanshu Prasad. Ultrametric logarithm laws I. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 337-348. doi: 10.3934/dcdss.2009.2.337

[18]

Chihurn Kim, Dong Han Kim. On the law of logarithm of the recurrence time. Discrete & Continuous Dynamical Systems - A, 2004, 10 (3) : 581-587. doi: 10.3934/dcds.2004.10.581

[19]

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

[20]

Isaac A. García, Claudia Valls. The three-dimensional center problem for the zero-Hopf singularity. Discrete & Continuous Dynamical Systems - A, 2016, 36 (4) : 2027-2046. doi: 10.3934/dcds.2016.36.2027

2016 Impact Factor: 0.8

Metrics

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

Other articles
by authors

[Back to Top]