Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 6197))
Included in the following conference series:
1544Accesses
Abstract
The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. As a result, fruitless cycles can be resolved, but the best speedup we managed to achieve is by a factor of only 1.29. Although this is less than the speedup factor of\(\sqrt 2\) generally reported in the literature, it is supported by practical evidence.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC (2006)
Bailey, D.V., et al.: Breaking ECC2K-130. In: Cryptology ePrint Archive, Report 2009/541 (2009),http://eprint.iacr.org/
Bos, J.W., Kaihara, M.E., Montgomery, P.L.: Pollard rho on the PlayStation 3. In: Workshop record of SHARCS 2009, pp. 35–50 (2009),http://www.hyperelliptic.org/tanja/SHARCS/record2.pdf
Brent, R.P., Pollard, J.M.: Factorization of the eighth Fermat number. Math. Comp. 36(154), 627–630 (1981)
Certicom. Certicom ECC Challenge (1997),http://www.certicom.com/images/pdfs/cert_ecc_challenge.pdf
Certicom. Press release: Certicom announces elliptic curve cryptosystem (ECC) challenge winner (2002),http://www.certicom.com/index.php/2002-press-releases/38-2002-press-releases/340-notre-dame-mathematician-solves-eccp-109-encryption-key-problem-issued-in-1997
Duursma, I.M., Gaudry, P., Morain, F.: Speeding up the discrete log computation on curves with automorphisms. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 103–121. Springer, Heidelberg (1999)
Escott, A.E., Sager, J.C., Selkirk, A.P.L., Tsapakidis, D.: Attacking elliptic curve cryptosystems using the parallel Pollard rho method. CryptoBytes Technical Newsletter 4(2), 15–19 (1999),ftp.rsasecurity.com/pub/cryptobytes/crypto4n2.pdf
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Improving the parallelized Pollard lambda search on anomalous binary curves. Math. Comp. 69(232), 1699–1705 (2000)
Harley, R.: Elliptic curve discrete logarithms project,http://pauillac.inria.fr/~harley/
Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48, 203–209 (1987)
Koblitz, N.: CM-curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992)
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comp. 48, 243–264 (1987)
Pollard, J.M.: Monte Carlo methods for index computation (modp). Math. Comp. 32, 918–924 (1978)
Teske, E.: On random walks for Pollard’s rho method. Math. Comp. 70(234), 809–825 (2001)
van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. Journal of Cryptology 12(1), 1–28 (1999)
Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 190–200. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland
Joppe W. Bos, Thorsten Kleinjung & Arjen K. Lenstra
- Joppe W. Bos
You can also search for this author inPubMed Google Scholar
- Thorsten Kleinjung
You can also search for this author inPubMed Google Scholar
- Arjen K. Lenstra
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
LIP/ENS-Lyon, 46, allée d’Italie, 69364, Lyon, Cedex 07, France
Guillaume Hanrot
Laboratoire d’Informatique (CNRS/UMR 7650), École polytechnique, 91128, Palaiseau Cedex, France
François Morain
INRIA Nancy, project CARAMEL, 615 rue du jardin botanique, 54602, Villers-lès-Nancy Cedex,, France
Emmanuel Thomé
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bos, J.W., Kleinjung, T., Lenstra, A.K. (2010). On the Use of the Negation Map in the Pollard Rho Method. In: Hanrot, G., Morain, F., Thomé, E. (eds) Algorithmic Number Theory. ANTS 2010. Lecture Notes in Computer Science, vol 6197. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14518-6_9
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-14517-9
Online ISBN:978-3-642-14518-6
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative