Geodesic
On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism
Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 2, pp. 45-57 
M. V. Nikolaev. On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism. Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 2, pp. 45-57. http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a5/
@article{MVK_2015_6_2_a5,
     author = {M. V. Nikolaev},
     title = {On the complexity of two-dimensional discrete logarithm problem in a~finite cyclic group with efficient automorphism},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {45--57},
     year = {2015},
     volume = {6},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a5/}
}
TY  - JOUR
AU  - M. V. Nikolaev
TI  - On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism
JO  - Matematičeskie voprosy kriptografii
PY  - 2015
SP  - 45
EP  - 57
VL  - 6
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a5/
LA  - en
ID  - MVK_2015_6_2_a5
ER  - 
%0 Journal Article
%A M. V. Nikolaev
%T On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism
%J Matematičeskie voprosy kriptografii
%D 2015
%P 45-57
%V 6
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a5/
%G en
%F MVK_2015_6_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

Two-dimensional discrete logarithm problem in a finite additive group $G$ consists in solving the equation $Q=n_1P_1+n_2P_2$ with respect to $n_1$, $n_2$ for specified $P_1,P_2,Q\in G$, $0$ such that there exists solution with $|n_1|\le N_1$, $|n_2|\le N_2$. In 2004, Gaudry and Schost proposed an algorithm to solve this problem with average complexity $(c+o(1))\sqrt N$ of group operations in $G$ where $c\approx2.43$, $N=4N_1N_2$, $N\to\infty$. In 2009, Galbraith and Ruprai improved this algorithm to obtain $c\approx2.36$. We show that the constant $c$ may be reduced if the group $G$ has an automorphism computable faster than the group operation.

[1] Galbraith S. D., Holmes M., “A non-uniform birthday problem with applications to discrete logarithms”, Discrete Applied Mathematics, 160:10–11 (2012), 1547–1560 ; http://eprint.iacr.org/2010/616 | DOI | MR | Zbl

[2] Galbraith S. D., Ruprai R. S., “An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems”, Cryptography and Coding, 12th IMA International Conference, Lect. Notes Comput. Sci., 5921, ed. Parker M. G., Springer, 2009, 368–382 | MR | Zbl

[3] Galbraith S. D., Ruprai R. S., “Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval”, Public Key Cryptography – PKC 2010, Lect. Notes Comput. Sci., 6056, Springer, 2010, 368–383 ; http://eprint.iacr.org/2010/615 | MR | Zbl

[4] Gaudry P., Schost E., “A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm”, Proceedings of Algorithm Number Theory Symposium – ANTS VI, Lect. Notes Comput. Sci., 3076, Springer-Verlag, 2004, 208–222 | MR | Zbl

[5] Liu W., Improved algorithms for the 2-dimensional discrete logarithm problem with equivalence classes, MSc Thesis, University of Auckland, 2010 http://www.math.auckland.ac.nz/~sgal018/Wei-Liu-MSc.pdf

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

[7] Nikolaev M. V., Matyukhin D. V., “On the complexity of the two-dimensional problem of computing a discrete logarithm in a finite cyclic group with effective automorphism of order 6”, Discrete Math. Appl., 23:3–4 (2013), 313–325 | DOI | MR | Zbl

[8] Gallant R., Lambert R., Vanstone S., “Faster point multiplication on elliptic curves with efficient endomorphisms”, CRYPTO'01, Proc. 21st Ann. Int. Crypt. Conf. Advances in Cryptology, Lect. Notes Comput. Sci., 2139, ed. Kilian J., 2001, 190–200 | MR | Zbl

[9] Duursma I. M., Gaudry P., Morain F., “Speeding up the discrete log computation on curves with automorphisms”, ASIACRYPT'99, Lect. Notes Comput. Sci., 1716, eds. K.-Y. Lam, E. Okamoto, C. Xing, Springer, Heidelberg, 1999, 103–121 | MR | Zbl