Computing discrete logarithms in an interval

Galbraith, Steven; Pollard, John; Ruprai, Raminder

doi:10.1090/S0025-5718-2012-02641-X

Computing discrete logarithms in an interval
HTML articles powered by AMS MathViewer

by Steven D. Galbraith, John M. Pollard and Raminder S. Ruprai PDF

Math. Comp. 82 (2013), 1181-1195 Request permission

Abstract:

The discrete logarithm problem in an interval of size $N$ in a group $G$ is: Given $g, h \in G$ and an integer $N$ to find an integer $0 \le n \le N$, if it exists, such that $h = g^n$. Previously the best low-storage algorithm to solve this problem was the van Oorschot and Wiener version of the Pollard kangaroo method. The heuristic average case running time of this method is $(2 + o(1)) \sqrt {N}$ group operations.

We present two new low-storage algorithms for the discrete logarithm problem in an interval of size $N$. The first algorithm is based on the Pollard kangaroo method, but uses 4 kangaroos instead of the usual two. We explain why this algorithm has heuristic average case expected running time of $(1.715 + o(1)) \sqrt {N}$ group operations. The second algorithm is based on the Gaudry-Schost algorithm and the ideas of our first algorithm. We explain why this algorithm has heuristic average case expected running time of $(1.661 + o(1)) \sqrt {N}$ group operations. We give experimental results that show that the methods do work close to that predicted by the theoretical analysis.

References

Dan Boneh, Eu-Jin Goh, and Kobbi Nissim, Evaluating 2-DNF formulas on ciphertexts, Theory of cryptography, Lecture Notes in Comput. Sci., vol. 3378, Springer, Berlin, 2005, pp. 325–341. MR 2168490, DOI 10.1007/978-3-540-30576-7_{1}8
Jung Hee Cheon, Security analysis of the strong Diffie-Hellman problem, Advances in cryptology—EUROCRYPT 2006, Lecture Notes in Comput. Sci., vol. 4004, Springer, Berlin, 2006, pp. 1–11. MR 2423212, DOI 10.1007/11761679_{1}
Steven Galbraith and Raminder S. Ruprai, An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems, Cryptography and coding, Lecture Notes in Comput. Sci., vol. 5921, Springer, Berlin, 2009, pp. 368–382. MR 2775634, DOI 10.1007/978-3-642-10868-6_{2}2
Steven D. Galbraith and Raminder S. Ruprai, Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval, Public key cryptography—PKC 2010, Lecture Notes in Comput. Sci., vol. 6056, Springer, Berlin, 2010, pp. 368–383. MR 2660753, DOI 10.1007/978-3-642-13013-7_{2}2
S. D. Galbraith and M. Holmes, A non-uniform birthday problem with applications to discrete logarithms, to appear in Discrete Applied Mathematics (2012).
Pierrick Gaudry and Éric Schost, A low-memory parallel version of Matsuo, Chao, and Tsujii’s algorithm, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 208–222. MR 2137355, DOI 10.1007/978-3-540-24847-7_{1}5
Rosario Gennaro, An improved pseudo-random generator based on discrete log, Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 1880, Springer, Berlin, 2000, pp. 469–481. MR 1850061, DOI 10.1007/3-540-44598-6_{2}9
K. Gopalakrishnan, Nicolas Thériault, and Chui Zhi Yao, Solving discrete logarithms from partial knowledge of the key, Progress in cryptology—INDOCRYPT 2007, Lecture Notes in Comput. Sci., vol. 4859, Springer, Berlin, 2007, pp. 224–237. MR 2570258, DOI 10.1007/978-3-540-77026-8_{1}7
David Jao and Kayo Yoshida, Boneh-Boyen signatures and the strong Diffie-Hellman problem, Pairing-based cryptography—Pairing 2009, Lecture Notes in Comput. Sci., vol. 5671, Springer, Berlin, 2009, pp. 1–16. MR 2737074, DOI 10.1007/978-3-642-03298-1_{1}
Chae Hoon Lim and Pil Joong Lee, A key recovery attack on discrete log-based schemes using a prime order subgroup, Advances in cryptology—CRYPTO ’97 (Santa Barbara, CA, 1997) Lecture Notes in Comput. Sci., vol. 1294, Springer, Berlin, 1997, pp. 249–263. MR 1630401, DOI 10.1007/BFb0052240
R. Montenegro and P. Tetali, How long does it take to catch a wild kangaroo? STOC 2009, ACM (2009) 553–560.
R. Montenegro, Remarks about random walks in the Gaudry-Schost algorithm, Emails, 4 January and 5 January 2011.
Sarvar Patel and Ganapathy S. Sundaram, An efficient discrete log pseudo-random generator, Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998) Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 304–317. MR 1670959, DOI 10.1007/BFb0055737
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
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. M. Pollard, Kangaroos, Monopoly and discrete logarithms, J. Cryptology 13 (2000), no. 4, 437–447. MR 1788514, DOI 10.1007/s001450010010
R. S. Ruprai, Improvements to the Gaudry-Schost Algorithm for Multidimensional discrete logarithm problems and Applications, PhD thesis, Royal Holloway University of London, 2009.
B. I. Selivanov, On the waiting time in a scheme for the random allocation of colored particles, Diskret. Mat. 7 (1995), no. 1, 134–144 (Russian, with Russian summary); English transl., Discrete Math. Appl. 5 (1995), no. 1, 73–82. MR 1331936, DOI 10.1515/dma.1995.5.1.73
P. C. van Oorschot and M. J. Wiener, Parallel collision search with application to hash functions and discrete logarithms, In ACM Conference on Computer and Communications Security, (1994) 210–218.
P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman Key Agreement with Short Exponents, in U. M. Maurer (ed.), EUROCRYPT 1996, Springer LNCS 1070 (1996) 332–343.
Paul C. van Oorschot and Michael J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology 12 (1999), no. 1, 1–28. MR 1664774, DOI 10.1007/PL00003816