## 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

## Additional Information

**Steven D. Galbraith**- Affiliation: Mathematics Department, The University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
- Email: S.Galbraith@math.auckland.ac.nz
**John M. Pollard**- Affiliation: Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, Berkshire RG8 8EX, United Kingdom
- Email: jmptidcott@googlemail.com
**Raminder S. Ruprai**- Affiliation: Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX, United Kingdom
- Email: raminder@email.com
- Received by editor(s): December 1, 2010
- Received by editor(s) in revised form: October 9, 2011
- Published electronically: August 17, 2012
- Additional Notes: This work was supported by EPSRC grant EP/D069904/1
- © Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**82**(2013), 1181-1195 - MSC (2010): Primary 11Y16, 68W20, 11T71
- DOI: https://doi.org/10.1090/S0025-5718-2012-02641-X
- MathSciNet review: 3008854