Geodesic
Modified Gaudry–Schost algorithm for the two-dimensional discrete logarithm problem
Matematičeskie voprosy kriptografii, Tome 11 (2020) no. 2, pp. 125-135 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the two-dimensional discrete logarithm problem for the subgroup $ G $ of a rational points group of an elliptic curve defined over a finite prime field that has an efficient automorphism of order 6 (for given $ P_1, P_2, Q \in G, 0 $ we have to find $ n_1, n_2 $ such that $ Q = n_1P_1 + n_2P_2, ~-N_1 \leq n_1 \leq N_1, -N_2 \leq n_2 \leq N_2 $). For this problem, modification of the Gaudry–Schost algorithm is suggested such that for any ${\varepsilon>0}$ there exists an algorithm with average complexity not exceeding $ {(1+ \varepsilon) 0.847\sqrt {N} + O _{\varepsilon} (N ^ {1/4}) }$ group operations for ${ N = 4N_1N_2, ~N \to \infty }$. 
@article{MVK_2020_11_2_a9,
     author = {M. V. Nikolaev},
     title = {Modified {Gaudry{\textendash}Schost} algorithm for the two-dimensional discrete logarithm problem},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {125--135},
     year = {2020},
     volume = {11},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a9/}
}
TY  - JOUR
AU  - M. V. Nikolaev
TI  - Modified Gaudry–Schost algorithm for the two-dimensional discrete logarithm problem
JO  - Matematičeskie voprosy kriptografii
PY  - 2020
SP  - 125
EP  - 135
VL  - 11
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a9/
LA  - en
ID  - MVK_2020_11_2_a9
ER  - 
%0 Journal Article
%A M. V. Nikolaev
%T Modified Gaudry–Schost algorithm for the two-dimensional discrete logarithm problem
%J Matematičeskie voprosy kriptografii
%D 2020
%P 125-135
%V 11
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a9/
%G en
%F MVK_2020_11_2_a9
M. V. Nikolaev. Modified Gaudry–Schost algorithm for the two-dimensional discrete logarithm problem. Matematičeskie voprosy kriptografii, Tome 11 (2020) no. 2, pp. 125-135. http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a9/

[1] Aranha D. F., Fouque P., Gérard B., Kammerer J., Tibouchi M., Zapalowicz J.-C., “GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce dias”, ASIACRYPT 2014, v. I, Lect. Notes Comput. Sci., 8873, 2014, 262–281 | DOI | MR | Zbl

[2] Blackburn S.R., Scott S., “The discrete logarithm problem for exponents of bounded height”, LMS J. Comput. and Math., 17 (2014), 148–156 | DOI | MR

[3] Bos J. W., Costello C., Hisil H., Lauter K., “High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition”, CHES 2013, Lect. Notes Comput. Sci., 8086, 2013, 331–348 | DOI

[4] Costello C., Hisil H., Smith B., “Faster Compact Diffie–Hellman: Endomorphisms on the $x$-line”, EUROCRYPT 2014, Lect. Notes Comput. Sci., 8441, 2014, 183–200 | DOI | MR | Zbl

[5] Duursma I. M., Gaudry P., Morain F., “Speeding up the discrete log computation on curves with automorphisms”, Lect. Notes Comput. Sci., 1716, 1999, 103–121 | DOI | MR | Zbl

[6] Galbraith S. D., Holmes M., “A non-uniform birthday problem with applications to discrete logarithms”, Discr. Appl. Math., 160:10-11 (2012), 1547–1560 | DOI | MR | Zbl

[7] Galbraith S. D., Ruprai R. S., “An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems”, IMACC 2009, Lect. Notes Comput. Sci., 5921, 2009, 368–382 | DOI | MR | Zbl

[8] Galbraith S. D., Ruprai R. S., “Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval”, PKC 2010, Lect. Notes Comput. Sci., 6056, 2010, 368–383 | DOI | MR | Zbl

[9] Gaudry P., Schost E., “A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm”, Lect. Notes Comput. Sci., 3076, 2004, 208–222 | DOI | MR | Zbl

[10] Gallant R., Lambert R., Vanstone S., “Faster point multiplication on elliptic curves with efficient endomorphisms”, CRYPTO 2001, Lect. Notes Comput. Sci., 2139, 2001, 190–200 | DOI | MR | Zbl

[11] Galbraith S. D., Lin X., Scott M., “Endomorphisms for faster elliptic curve cryptography on a large class of curves”, J. Cryptology, 24:3 (2011), 446–469 | DOI | MR | Zbl

[12] Liu W., Improved algorithms for the 2-dimensional discrete logarithm problem with equivalence classes, Master's thesis, Univ. of Auckland, 2010 http://www.math.auckland.ac.nz/s̃gal018/Wei-Liu-MSc.pdf

[13] Nikolaev M. V., “On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism”, Mathematicheskie Voprosy Kriptografii, 6:2 (2015), 45–57 | DOI | MR

[14] Wiener M. J., Zuccherato R. J., “Faster attacks on elliptic curve cryptosystems”, SAC 1998, Lect. Notes Comput. Sci., 1556, 1999, 190–200 | DOI | MR | Zbl