
-
Previous Article
The weight distributions of constacyclic codes
- AMC Home
- This Issue
-
Next Article
Integer-valued Alexis sequences with large zero correlation zone
Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm
1. | Mathematics Department, University of Auckland, New Zealand |
2. | College of Information Engineering, Shenzhen University, Shenzhen 518060, China |
3. | School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China |
The negation map can be used to speed up the computation of elliptic curve discrete logarithms using either the baby-step giant-step algorithm (BSGS) or Pollard rho. Montgomery's simultaneous modular inversion can also be used to speed up Pollard rho when running many walks in parallel. We generalize these ideas and exploit the fact that for any two elliptic curve points X and Y, we can efficiently get X-Y when we compute X+Y. We apply these ideas to speed up the baby-step giant-step algorithm. Compared to the previous methods, the new methods can achieve a significant speedup for computing elliptic curve discrete logarithms in small groups or small intervals.
Another contribution of our paper is to give an analysis of the average-case running time of Bernstein and Lange's "grumpy giants and a baby" algorithm, and also to consider this algorithm in the case of groups with efficient inversion.
Our conclusion is that, in the fully-optimised context, both the interleaved BSGS and grumpy-giants algorithms have superior average-case running time compared with Pollard rho. Furthermore, for the discrete logarithm problem in an interval, the interleaved BSGS algorithm is considerably faster than the Pollard kangaroo or Gaudry-Schost methods.
References:
[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.
doi: 10.1007/978-3-642-34931-7_19. |
[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.
doi: 10.2140/obs.2013.1.87. |
[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.
doi: 10.1007/978-3-642-19379-8_8. |
[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.
doi: 10.1007/978-3-540-30576-7_18. |
[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.
doi: 10.1002/jcd.10033. |
[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.
doi: 10.1090/S0025-5718-2012-02641-X. |
[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.
doi: 10.1007/978-3-642-13013-7_22. |
[9] |
R. Gallant, R. Lambert and S. Vanstone,
Improving the parallelized Pollard lambda search on binary anomalous curves, Math. Comp., 69 (1999), 1699-1705.
doi: 10.1090/S0025-5718-99-01119-9. |
[10] |
P. Gaudry and E. Schost, A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm, in ANTS Ⅵ (ed. D. A. Buell), Springer, 2004,208–222.
doi: 10.1007/978-3-540-24847-7_15. |
[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.
doi: 10.1112/S1461157000001194. |
[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.
doi: 10.2307/2007884. |
[14] |
V. Miller, Use of elliptic curves in cryptography, in Crypto '85 (ed. H. C. Williams), Springer,
1986,417–426.
doi: 10.1007/3-540-39799-X_31. |
[15] |
P. L. Montgomery,
Speeding the Pollard and elliptic curve methods of factorization, Math. Comp., 48 (1987), 243-264.
doi: 10.2307/2007888. |
[16] |
V. I. Nechaev,
Complexity of a determinate algorithm for the discrete logarithm, Math. Notes, 55 (1994), 165-172.
doi: 10.1007/BF02113297. |
[17] |
J. M. Pollard,
Monte Carlo methods for index computation (mod p), Math. Comp., 32 (1978), 918-924.
doi: 10.2307/2006496. |
[18] |
J. Pollard,
Kangaroos, Monopoly and discrete logarithms, J. Crypt., 13 (2000), 437-447.
doi: 10.1007/s001450010010. |
[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.
doi: 10.1007/PL00003816. |
[21] |
P. Wang and F. Zhang,
Computing elliptic curve discrete logarithms with the negation map, Inf. Sci., 195 (2012), 277-286.
doi: 10.1016/j.ins.2012.01.044. |
[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.
doi: 10.1109/EIDWT.2013.55. |
[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.
doi: 10.1007/3-540-48892-8_15. |
show all references
References:
[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.
doi: 10.1007/978-3-642-34931-7_19. |
[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.
doi: 10.2140/obs.2013.1.87. |
[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.
doi: 10.1007/978-3-642-19379-8_8. |
[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.
doi: 10.1007/978-3-540-30576-7_18. |
[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.
doi: 10.1002/jcd.10033. |
[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.
doi: 10.1090/S0025-5718-2012-02641-X. |
[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.
doi: 10.1007/978-3-642-13013-7_22. |
[9] |
R. Gallant, R. Lambert and S. Vanstone,
Improving the parallelized Pollard lambda search on binary anomalous curves, Math. Comp., 69 (1999), 1699-1705.
doi: 10.1090/S0025-5718-99-01119-9. |
[10] |
P. Gaudry and E. Schost, A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm, in ANTS Ⅵ (ed. D. A. Buell), Springer, 2004,208–222.
doi: 10.1007/978-3-540-24847-7_15. |
[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.
doi: 10.1112/S1461157000001194. |
[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.
doi: 10.2307/2007884. |
[14] |
V. Miller, Use of elliptic curves in cryptography, in Crypto '85 (ed. H. C. Williams), Springer,
1986,417–426.
doi: 10.1007/3-540-39799-X_31. |
[15] |
P. L. Montgomery,
Speeding the Pollard and elliptic curve methods of factorization, Math. Comp., 48 (1987), 243-264.
doi: 10.2307/2007888. |
[16] |
V. I. Nechaev,
Complexity of a determinate algorithm for the discrete logarithm, Math. Notes, 55 (1994), 165-172.
doi: 10.1007/BF02113297. |
[17] |
J. M. Pollard,
Monte Carlo methods for index computation (mod p), Math. Comp., 32 (1978), 918-924.
doi: 10.2307/2006496. |
[18] |
J. Pollard,
Kangaroos, Monopoly and discrete logarithms, J. Crypt., 13 (2000), 437-447.
doi: 10.1007/s001450010010. |
[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.
doi: 10.1007/PL00003816. |
[21] |
P. Wang and F. Zhang,
Computing elliptic curve discrete logarithms with the negation map, Inf. Sci., 195 (2012), 277-286.
doi: 10.1016/j.ins.2012.01.044. |
[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.
doi: 10.1109/EIDWT.2013.55. |
[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.
doi: 10.1007/3-540-48892-8_15. |


0 | 0.12 | 0.24 | 0.37 | 0.49 | 0.61 | 0.73 | 0.85 | 0.97 | |
3.00 | 3.00 | 3.00 | 2.99 | 2.79 | 2.30 | 1.77 | 1.35 | 1.06 |
0 | 0.12 | 0.24 | 0.37 | 0.49 | 0.61 | 0.73 | 0.85 | 0.97 | |
3.00 | 3.00 | 3.00 | 2.99 | 2.79 | 2.30 | 1.77 | 1.35 | 1.06 |
Bits | #Elliptic Curves | #DLPs per Curve | average value for c | standard deviation |
28 | 100 | 10000 | 1.2579 | 0.0083 |
29 | 100 | 10000 | 1.2533 | 0.0064 |
30 | 100 | 10000 | 1.2484 | 0.0062 |
31 | 100 | 10000 | 1.2517 | 0.0067 |
32 | 100 | 10000 | 1.2736 | 0.0054 |
Bits | #Elliptic Curves | #DLPs per Curve | average value for c | standard deviation |
28 | 100 | 10000 | 1.2579 | 0.0083 |
29 | 100 | 10000 | 1.2533 | 0.0064 |
30 | 100 | 10000 | 1.2484 | 0.0062 |
31 | 100 | 10000 | 1.2517 | 0.0067 |
32 | 100 | 10000 | 1.2736 | 0.0054 |
Algorithm | Average-case | Worst-case |
Textbook BSGS [19] | ||
Textbook BSGS optimised for average-case [18] | ||
Pollard interleaving BSGS [17] | ||
Grumpy giants [2] | ||
Pollard rho using distinguished points [20] | ||
Gaudry-Schost [7] | ||
BSGS with negation | ||
Pollard interleaving BSGS with negation | ||
Grumpy giants with negation | ||
Pollard rho using negation [3,21] | ||
Gaudry-Schost using negation [8] | ||
Interleaved BSGS with block computation | ||
Grumpy giants with block computation | ||
Pollard rho with Montgomery trick | ||
Gaudry-Schost with Montgomery trick |
Algorithm | Average-case | Worst-case |
Textbook BSGS [19] | ||
Textbook BSGS optimised for average-case [18] | ||
Pollard interleaving BSGS [17] | ||
Grumpy giants [2] | ||
Pollard rho using distinguished points [20] | ||
Gaudry-Schost [7] | ||
BSGS with negation | ||
Pollard interleaving BSGS with negation | ||
Grumpy giants with negation | ||
Pollard rho using negation [3,21] | ||
Gaudry-Schost using negation [8] | ||
Interleaved BSGS with block computation | ||
Grumpy giants with block computation | ||
Pollard rho with Montgomery trick | ||
Gaudry-Schost with Montgomery trick |
0 | 0.15 | 0.30 | 0.46 | 0.61 | 0.76 | 0.91 | |
6.00 | 5.76 | 5.47 | 4.10 | 2.56 | 1.72 | 1.20 |
0 | 0.15 | 0.30 | 0.46 | 0.61 | 0.76 | 0.91 | |
6.00 | 5.76 | 5.47 | 4.10 | 2.56 | 1.72 | 1.20 |
Bits | #Elliptic Curves | #DLPs per Curve | average value for c | standard deviation |
28 | 100 | 10000 | 0.8926 | 0.0077 |
29 | 100 | 10000 | 0.9053 | 0.0061 |
30 | 100 | 10000 | 0.8961 | 0.0073 |
31 | 100 | 10000 | 0.9048 | 0.0068 |
32 | 100 | 10000 | 0.9207 | 0.0065 |
Bits | #Elliptic Curves | #DLPs per Curve | average value for c | standard deviation |
28 | 100 | 10000 | 0.8926 | 0.0077 |
29 | 100 | 10000 | 0.9053 | 0.0061 |
30 | 100 | 10000 | 0.8961 | 0.0073 |
31 | 100 | 10000 | 0.9048 | 0.0068 |
32 | 100 | 10000 | 0.9207 | 0.0065 |
Bits | #Elliptic Curves | #DLPs per Curve | average value for |
28 | 100 | 10000 | 1.2867 |
29 | 100 | 10000 | 1.3002 |
30 | 100 | 10000 | 1.2926 |
31 | 100 | 10000 | 1.2944 |
32 | 100 | 10000 | 1.3150 |
Bits | #Elliptic Curves | #DLPs per Curve | average value for |
28 | 100 | 10000 | 1.2867 |
29 | 100 | 10000 | 1.3002 |
30 | 100 | 10000 | 1.2926 |
31 | 100 | 10000 | 1.2944 |
32 | 100 | 10000 | 1.3150 |
[1] |
Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial and Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543 |
[2] |
Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063 |
[3] |
Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601 |
[4] |
Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 |
[5] |
Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103 |
[6] |
Leonid Faybusovich, Cunlu Zhou. Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 445-467. doi: 10.3934/naco.2021017 |
[7] |
Xiaoyu Xing, Hailiang Yang. American type geometric step options. Journal of Industrial and Management Optimization, 2013, 9 (3) : 549-560. doi: 10.3934/jimo.2013.9.549 |
[8] |
Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131 |
[9] |
Delphine Boucher. A first step towards the skew duadic codes. Advances in Mathematics of Communications, 2018, 12 (3) : 553-577. doi: 10.3934/amc.2018033 |
[10] |
Jon Aaronson, Michael Bromberg, Nishant Chandgotia. Rational ergodicity of step function skew products. Journal of Modern Dynamics, 2018, 13: 1-42. doi: 10.3934/jmd.2018012 |
[11] |
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 |
[12] |
Andrew J. Steyer, Erik S. Van Vleck. Underlying one-step methods and nonautonomous stability of general linear methods. Discrete and Continuous Dynamical Systems - B, 2018, 23 (7) : 2859-2877. doi: 10.3934/dcdsb.2018108 |
[13] |
Peter E. Kloeden, Björn Schmalfuss. Lyapunov functions and attractors under variable time-step discretization. Discrete and Continuous Dynamical Systems, 1996, 2 (2) : 163-172. doi: 10.3934/dcds.1996.2.163 |
[14] |
Michael A. Saum, Tim Schulze. The role of processing speed in determining step patterns during directional epitaxy. Discrete and Continuous Dynamical Systems - B, 2009, 11 (2) : 443-457. doi: 10.3934/dcdsb.2009.11.443 |
[15] |
Lifeng Chen, Jifa Jiang. Stochastic epidemic models driven by stochastic algorithms with constant step. Discrete and Continuous Dynamical Systems - B, 2016, 21 (2) : 721-736. doi: 10.3934/dcdsb.2016.21.721 |
[16] |
Yoonsang Lee, Bjorn Engquist. Variable step size multiscale methods for stiff and highly oscillatory dynamical systems. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1079-1097. doi: 10.3934/dcds.2014.34.1079 |
[17] |
Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011 |
[18] |
Tingting Wu, Yufei Yang, Huichao Jing. Two-step methods for image zooming using duality strategies. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 209-225. doi: 10.3934/naco.2014.4.209 |
[19] |
Van Hieu Dang. An extension of hybrid method without extrapolation step to equilibrium problems. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1723-1741. doi: 10.3934/jimo.2017015 |
[20] |
Angelamaria Cardone, Dajana Conte, Beatrice Paternoster. Two-step collocation methods for fractional differential equations. Discrete and Continuous Dynamical Systems - B, 2018, 23 (7) : 2709-2725. doi: 10.3934/dcdsb.2018088 |
2021 Impact Factor: 1.015
Tools
Metrics
Other articles
by authors
[Back to Top]