Improving the parallelized Pollard lambda search on anomalous binary curves
HTML articles powered by AMS MathViewer
- by Robert Gallant, Robert Lambert and Scott Vanstone PDF
- Math. Comp. 69 (2000), 1699-1705 Request permission
Abstract:
The best algorithm known for finding logarithms on an elliptic curve $(E)$ is the (parallelized) Pollard lambda collision search. We show how to apply a Pollard lambda search on a set of equivalence classes derived from $E$, which requires fewer iterations than the standard approach. In the case of anomalous binary curves over $F_{2^m}$, the new approach speeds up the standard algorithm by a factor of $\sqrt {2m}$.References
- The Certicom ECC Challenge, available from http://www.certicom.com/chal/, 1997.
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Neal Koblitz, CM-curves with good cryptographic properties, Advances in cryptology—CRYPTO ’91 (Santa Barbara, CA, 1991) Lecture Notes in Comput. Sci., vol. 576, Springer, Berlin, 1992, pp. 279–287. MR 1243654, DOI 10.1007/3-540-46766-1_{2}2
- P. van Oorschot and M. Wiener, “Parallel collision search with cryptanalytic applications", to appear in Journal of Cryptology.
- J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
- J. Solinas, “An improved algorithm for arithmetic on a family of elliptic curves", Advances in Cryptology—CRYPTO ’97, Lecture Notes in Computer Science, 1294 (1997), Springer-Verlag, 357–371.
- E. Teske, “Speeding up Pollard’s rho method for computing discrete logarithms", preprint, 1997, available from http://www.informatik.th-darmstadt.de/TI/Veroeffentlichung/TR/.
- M. Wiener and R. Zuccherato, “Faster attacks on elliptic curve cryptosystems", preprint, 1998, available from http://grouper.ieee.org/groups/1363/contributions/attackEC.ps.
Additional Information
- Robert Gallant
- Affiliation: Certicom Corp., 200 Matheson Blvd. W., Suite 103, Mississauga, Ontario, Canada L5R 3L7
- Email: rgallant@certicom.com
- Robert Lambert
- Affiliation: Certicom Corp., 200 Matheson Blvd. W., Suite 103, Mississauga, Ontario, Canada L5R 3L7
- Email: rlambert@certicom.com
- Scott Vanstone
- Affiliation: Certicom Corp., 200 Matheson Blvd. W., Suite 103, Mississauga, Ontario, Canada L5R 3L7
- Email: svanstone@certicom.com
- Received by editor(s): June 9, 1998
- Received by editor(s) in revised form: October 15, 1998
- Published electronically: May 19, 1999
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 69 (2000), 1699-1705
- MSC (1991): Primary 94A60, 14Q05, 14H52
- DOI: https://doi.org/10.1090/S0025-5718-99-01119-9
- MathSciNet review: 1651754