×
Wang, Ping; Zhang, Fangguo

An efficient collision detection method for computing discrete logarithms with Pollard’s rho. (English) Zbl 1235.65161

J. Appl. Math. 2012, Article ID 635909, 15 p. (2012).
Summary: Pollard’s rho method and its parallelized variant are at present known as the best generic algorithms for computing discrete logarithms. However, when we compute discrete logarithms in cyclic groups of large orders using Pollard’s rho method, collision detection is always a high time and space consumer. In this paper, we present a new efficient collision detection algorithm for Pollard’s rho method. The new algorithm is more efficient than the previous distinguished point method and can be easily adapted to other applications. However, the new algorithm does not work with the parallelized rho method, but it can be parallelized with Pollard’s lambda method. Besides the theoretical analysis, we also compare the performances of the new algorithm with the distinguished point method in experiments with elliptic curve groups. The experiments show that the new algorithm can reduce the expected number of iterations before reaching a match from \(1.309 \sqrt{|G|}\) to \(1.295 \sqrt{|G|}\) under the same space requirements for the single rho method.

MSC:

65Y05 Parallel numerical computation
20-04 Software, source code, etc. for problems pertaining to group theory

Software:

SageMath
PDF BibTeX XML Cite
\textit{P. Wang} and \textit{F. Zhang}, J. Appl. Math. 2012, Article ID 635909, 15 p. (2012; Zbl 1235.65161)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644-654, 1976. · Zbl 0435.94018
[2] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469-472, 1985. · Zbl 0571.94014
[3] FIPS 186-2, “Digital signature standard,” Tech. Rep. 186-2, Federal Information Processing Standards Publication, 2000.
[4] C. P. Schnorr, “Efficient signature generation by smart cards,” Journal of Cryptology, vol. 4, no. 3, pp. 161-174, 1991. · Zbl 0743.68058
[5] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, no. 177, pp. 203-209, 1987. · Zbl 0622.94015
[6] V. Miller, “Use of elliptic curves in cryptography,” in Advances in Cryptology: Proceedings of Crypto’85, vol. 218 of LNCS, pp. 417-426, Springer, New York, NY, USA, 1986. · Zbl 0589.94005
[7] A. Menezes, P. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, Fla, USA, 1996. · Zbl 0868.94001
[8] J. M. Pollard, “Monte Carlo methods for index computation mod p,” Mathematics of Computation, vol. 32, no. 143, pp. 918-924, 1978. · Zbl 0382.10001
[9] R. Gallant, R. Lambert, and S. Vanstone, “Improving the parallelized Pollard lambda search on anomalous binary curves,” Mathematics of Computation, vol. 69, no. 232, pp. 1699-1705, 2000. · Zbl 1101.14325
[10] M. Wiener and R. Zuccherato, “Faster attacks on elliptic curve cryptosystems,” in Selected Areas in Cryptography’98, vol. 1556 of LNCS, pp. 190-200, Springer, Berlin, Germany, 1998. · Zbl 1025.94511
[11] P. van Oorschot and M. Wiener, “Parallel collision search with cryptanalytic applications,” Journal of Cryptology, vol. 12, no. 1, pp. 1-28, 1999. · Zbl 0992.94028
[12] R. P. Brent, “An improved Monte Carlo factorization algorithm,” BIT, vol. 20, no. 2, pp. 176-184, 1980. · Zbl 0439.65001
[13] G. Nivasch, “Cycle detection using a stack,” Information Processing Letters, vol. 90, no. 3, pp. 135-140, 2004. · Zbl 1178.68648
[14] J. J. Quisquater and J. P. Delescaille, “How easy is collision search? Application to DES,” in Proceedings of the Advances in Cryptology-Eurocrypt, vol. 434 of Lecture Notes in Computer Science, pp. 429-434, Springer, New York, NY, USA, 1989.
[15] J. J. Quisquater and J. P. Delescaille, “How easy is collision search. New results and applications to DES,” in Proceedings of the Advances in Cryptology-Crypto, vol. 435 of Lecture Notes in Computer Science, pp. 408-413, Springer, New York, NY, USA, 1989.
[16] M. E. Hellman, “A cryptanalytic time-memory trade-off,” IEEE Transactions on Information Theory, vol. 26, no. 4, pp. 401-406, 1980. · Zbl 0436.94016
[17] B. Harris, “Probability distributions related to random mappings,” Annals of Mathematical Statistics, vol. 31, pp. 1045-1062, 1960. · Zbl 0158.34905
[18] S. C. Pohlig and M. E. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance,” IEEE-Transactions on Information Theory, vol. 24, no. 1, pp. 106-110, 1978. · Zbl 0375.68023
[19] E. Teske, “Speeding up Pollard’s rho method for computing discrete logarithms,” in Algorithmic Number Theory Symposium (ANTS IV), vol. 1423 of LNCS, pp. 541-553, Springer, New York, NY, USA, 1998. · Zbl 1066.11513
[20] S. Bai and R. P. Brent, “On the efficiency of Pollard’s rho method for discrete logarithms,” in CATS 2008, J. Harland and P. Manyem, Eds., pp. 125-131, Australian Computer Society, 2008.
[21] C.-P. Schnorr and H. W. Lenstra Jr., “A Monte Carlo factoring algorithm with linear storage,” Mathematics of Computation, vol. 43, no. 167, pp. 289-311, 1984. · Zbl 0559.10004
[22] E. Teske, “A space efficient algorithm for group structure computation,” Mathematics of Computation, vol. 67, no. 224, pp. 1637-1663, 1998. · Zbl 0965.11050
[23] D. V. Bailey, L. Batina, D. J. Bernstein, et al., “Breaking ECC2K-130,” Tech. Rep. 2009/541, Cryptology ePrint Archive, 2009.
[24] J. M. Pollard, “A Monte Carlo method for factorization,” BIT, vol. 15, no. 3, pp. 331-335, 1975. · Zbl 0312.10006
[25] D. E. Knuth, The Art of Computer Programming, vol. 2, Addison-Wesley, Reading, Mass, USA, 3rd edition, 1997. · Zbl 0895.68054
[26] R. P. Brent, “Parallel algorithms for integer factorisation,” in Number Theory and Cryptography, J. H. Loxton, Ed., vol. 154 of London Mathematical Society Lecture Note Series, pp. 26-37, Cambridge University, Cambridge, UK, 1990. · Zbl 0709.11074
[27] “SAGE: an open source mathematics software,” http://www.sagemath.org/.
[28] D. E. Knuth, The Art of Computer Programming, vol. 3, Addison-Wesley, Reading, Mass, USA, 2nd edition, 1981. · Zbl 0895.68054
[29] E. Teske, “On random walks for Pollard’s rho method,” Mathematics of Computation, vol. 70, no. 234, pp. 809-825, 2001. · Zbl 1029.11071
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.