New Random Walk Technique and Collision
Detection Algorithm to Improve the Pollard
RHO Attack of Solving Discrete Logarithm
Problem on Elliptic Curves

CH.Suneetha; P.Sirisha; D.Sravana Kumar; KM sandeep

doi:https://doi.org/10.14445/22315373/IJMTT-V56P542

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 56 | Number 5 | Year 2018 | Article Id. IJMTT-V56P542 | DOI : https://doi.org/10.14445/22315373/IJMTT-V56P542

New Random Walk Technique and Collision Detection Algorithm to Improve the Pollard RHO Attack of Solving Discrete Logarithm Problem on Elliptic Curves

CH.Suneetha, P.Sirisha, D.Sravana Kumar, KM sandeep

Abstract

- Elliptic curve cryptography is a revolutionary in the history of public key cryptography that is protected by a hard problem Elliptic Curve Discrete Logarithm Problem (ECDLP). A wide research has been done on cryptanalysis of ECDLP. In 1978 Pollard developed an algorithm with a “Monte-Carlo” method for solving ECDLP called Pollard Rho attack which is the quickest algorithm. Since then the algorithm was modified to increase the efficiency of Pollard Rho algorithm in relatively short time to find the insecurity of the elliptic curve cryptosystem. The present paper designs a new random walk technique and collision detection algorithm to improve the performance of Pollard Rho algorithm.

Keywords

Pollard Rho Algorithm, Random walk, Collision Detection

References

[1] Koblitz N., “Elliptic curve cryptosystems, mathematics of computation”, Vol. 48, No. 177, pp. 203-209, January 1987.
[2] Miller V., “Uses of elliptic curves in cryptography”. In advances in Cryptography (CRYPTO 1985), Springer LNCS, 1985, vol. 218, pp 417-4 26.
[3] Maurer U., A. Menzes and E. Teske, “Analysis of GHS weil decent attack on the ECDLP over characteristic two fields of composite degree”. LMS journal of computation and Mathematics, 5:127-174, 2002.
[4] Washington, Lawrence C., “Elliptic Curves: Number theory and cryptography”, Chapman and Hall, Boca Raton, FL, 2nd. Ed., 2008.
[5] Lamb Nicholos, “An Investigation into Pollard Rho method for attacking Elliptic curve cryptosystems”, 2002, http://www.cs.ualberta
[6] Arron Blumenfeld, “Discrete logarithms on Elliptic curves”, 2011
[7] Ping Wang and Fangguo Zhang,” An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho”, Journal of Applied MathematicsVolume 2012 (2012), Article ID 635909, 15 pages.
[8] Ammar Ali Neamah,”New Collisions to Improve Pollard’s Rho Method of Solving the Discrete Logarithm Problem on Elliptic Curves” Journal of Computer Science, Volume 11, Issue 9.
[9] Masaya Yasuda, Tetsuya Izu, Takeshi Shimoyama and Jun Kogure,” On random walks of Pollard’s rho method for the ECDLP on Koblitz curves”, Journal of Math-for-Industry, Vol. 3 (2011B-3),
[10] Jung HeeCheon, Jin Hong, and Minkyu Kim,” Speeding Up the Pollard Rho Method on Prime Fields”.
[11] Paul C. van Oorschot and Michael J. Wiener.” Parallel Collision Search with Application to Hash Functions and Discrete Logarithms”.
[12] Mandy Zandra Seet, “ELLIPTIC CURVE CRYPTOGRAPHY Improving the Pollard-Rho Algorithm”, https://www.maths.unsw.edu.au/sites/default/files/mandyseetthesis.pdf
[13] Teske, E., “On random walks for Pollard’s RHO Method”. Mathem. Comput., 70: 809-825, 2001.
[14] Anjan K Koundinya, Harish G, Srinath NK et.al, Parallelization of Pollard’s Rho algorithm, proceeding of CCSEIT 2012 published in ACM-ICPS, pp. 43 -47, Oct 2012.
[15] Anjan K Koundinya, Harish G et.al, “performance analysis of parallel Pollard’s Rho factoring algorithm”, International Journal of Computer Science & Information Technology (IJCSIT) Vol 5, No 2, April 2013
[16] Kim, J. H., Montenegro, R. & Tetali, P. (2007), “A near optimal bound for Pollard’s rho to solve discrete log”, IEEE Proc. of the Foundations of Computer Science (FOCS), 2007, Providence, RI, to appear.
[17] D. J. Bernstein and T. Lange. “Analysis and optimization of elliptic-curve single scalar multiplication in Finite Fields and Applications”, volume 461 of Contemporary Mathematics Series, pages 1-19, 2008.
[18] F. Kuhn and R. Struik “Random walks revisited: Extensions of Pollard’s rho algorithm for computing multiple discrete logarithms”. Selected areas in cryptography SAC 2001 (LNCS 2259) [468]212-229 2001.
[19] Menzes A., and Vanstone S. “Hand book of applied cryptography”, The CRC-Press series of Discrete Mathematics and its Applications CRC-Press,1997.
[20] Miyaji , Nakabayashi and Takano “Elliptic curves with low embedding degree”, Journal of Cryptology, 2006, Volume 19, Number 4, Pages 553-562.

Citation :

CH.Suneetha, P.Sirisha, D.Sravana Kumar, KM sandeep, "New Random Walk Technique and Collision Detection Algorithm to Improve the Pollard RHO Attack of Solving Discrete Logarithm Problem on Elliptic Curves," International Journal of Mathematics Trends and Technology (IJMTT), vol. 56, no. 5, pp. 307-319, 2018. Crossref, https://doi.org/10.14445/22315373/IJMTT-V56P542