Advances in Mathematics of Communications (AMC)

Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm
Pages: 453 - 469, Issue 3, August 2017

doi:10.3934/amc.2017038      Abstract        References        Full text (931.0K)           Related Articles

Steven D. Galbraith - Mathematics Department, The University of Auckland, Private Bag 92019 Auckland 1142, New Zealand (email)
Ping Wang - College of Information Engineering, Shenzhen University, Shenzhen 518060, China (email)
Fangguo Zhang - School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China (email)

1 D. J. Bernstein and T. Lange, Computing small discrete logarithms faster, in INDOCRYPT 2012 (eds. S.D. Galbraith et al), Springer, 2012, 317-338.
2 D. J. Bernstein and T. Lange, Two grumpy giants and a baby, in Proc. 10th Algor. Number Theory Symp. (eds. E.W. Howe et al), 2013, 87-111.       
3 D. J. Bernstein, T. Lange and P. Schwabe, On the correct use of the negation map in the Pollard rho method, in PKC 2011 (eds. D. Catalano et al), Springer, 2011, 128-146.       
4 D. Boneh, E. Goh and K. Nissim, Evaluating 2-DNF formulas on ciphertexts, in Theory of Cryptography-TCC 2005 (ed. J. Kilian), Springer, 2005, 325-341.       
5 M. Chateauneuf, A. C. H. Ling and D. R. Stinson, Slope packings and coverings, and generic algorithms for the discrete logarithm problem, J. Combin. Des., 11 (2003), 36-50.       
6 K. Fong, D. Hankerson, J. Lopez and A. Menezes, Field inversion and point halving revisited, IEEE Trans. Comp., 53 (2004), 1047-1059.
7 S. D. Galbraith, J. M. Pollard and R. S. Ruprai, Computing discrete logarithms in an interval, Math. Comp., 82 (2013), 1181-1195.       
8 S. D. Galbraith and R. S. Ruprai, Using equivalence classes to speed up the discrete logarithm problem in a short interval, in PKC 2010 (eds. P. Nguyen et al), Springer, 2010, 368-383.       
9 R. Gallant, R. Lambert and S. Vanstone, Improving the parallelized Pollard lambda search on binary anomalous curves, Math. Comp., 69 (1999), 1699-1705.       
10 P. Gaudry and E. Schost, A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm, in ANTS VI (ed. D.A. Buell), Springer, 2004, 208-222.       
11 R. Granger, D. Page and M. Stam, On small characteristic algebraic tori in pairing-based cryptography, LMS J. Comp. Math., 9 (2006), 64-85.       
12 R. Henry, K. Henry and I. Goldberg, Making a nymbler Nymble using VERBS, in PETS 2010 (eds. M.J. Atallah), Springer, 2010, 111-129.
13 N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209.       
14 V. Miller, Use of elliptic curves in cryptography, in Crypto '85 (ed. H.C. Williams), Springer, 1986, 417-426.       
15 P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp., 48 (1987) 243-264.       
16 V. I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm, Math. Notes, 55 (1994), 165-172.       
17 J. M. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., 32 (1978), 918-924.       
18 J. Pollard, Kangaroos, Monopoly and discrete logarithms, J. Crypt., 13 (2000), 437-447.       
19 D. Shanks, Five number-theoretic algorithms, in Proc. 2nd Manitoba Conf. Numer. Math., Winnipeg, 1973, 51-70.       
20 P. van Oorschot and M. Wiener, Parallel collision search with cryptanalytic applications, J. Crypt., 12 (1999), 1-28.       
21 P. Wang and F. Zhang, Computing elliptic curve discrete logarithms with the negation map, Inf. Sci., 195 (2012) 277-286.       
22 P. Wang and F. Zhang, Improving the parallelized Pollard rho method for computing elliptic curve discrete logarithms, in 4th Int. Conf. Emerging Intell. Data Web Techn. (EIDWT-2013), 2013.
23 M. Wiener and R. Zuccherato, Faster attacks on elliptic curve cryptosystems, in Selected Areas in Cryptography '98 (eds. S.E. Tavares et al), Springer, 1998, 190-120.       

Go to top