Improving the parallelized Pollard lambda search on anomalous binary curves. (English) Zbl 1101.14325
Summary: 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 \(\mathbb{F}_{2^m}\), the new approach speeds up the standard algorithm by a factor of \(\sqrt{2m}\).
MSC:
| 14Q05 | Computational aspects of algebraic curves |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
| 94A60 | Cryptography |
| 11Y16 | Number-theoretic algorithms; complexity |
References:
| [1] | The Certicom ECC Challenge, available from http://www.certicom.com/chal/,1997. |
| [2] | Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002 |
| [3] | 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. · Zbl 0780.14018 · doi:10.1007/3-540-46766-1_22 |
| [4] | P. van Oorschot and M. Wiener, “Parallel collision search with cryptanalytic applications”, to appear in Journal of Cryptology. · Zbl 0992.94028 |
| [6] | 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. · Zbl 1032.11062 |
| [7] | 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/. · Zbl 1066.11513 |
| [8] | M. Wiener and R. Zuccherato, “Faster attacks on elliptic curve cryptosystems”, preprint, 1998, available from http://grouper.ieee.org/groups/1363/contributions/attackEC.ps. · Zbl 1025.94511 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
