Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing discrete logarithms in an interval

Authors: Steven D. Galbraith, John M. Pollard and Raminder S. Ruprai
Journal: Math. Comp. 82 (2013), 1181-1195
MSC (2010): Primary 11Y16, 68W20, 11T71
Published electronically: August 17, 2012
MathSciNet review: 3008854
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. D. Boneh, E.-J. Goh and K. Nissim, Evaluating 2-DNF Formulas on Ciphertexts, in J. Kilian (ed.), TCC 2005, Springer LNCS 3378 (2005) 325-341. MR 2168490 (2006i:94079)
  • 2. J. H. Cheon,
    Security Analysis of the Strong Diffie-Hellman Problem,
    in S. Vaudenay (ed.), EUROCRYPT 2006, Springer LNCS 4004 (2006) 1-11. MR 2423212 (2009d:94073)
  • 3. S. D. Galbraith and R. S. Ruprai, An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems, in M. Parker (ed.), Twelfth IMA International Conference on Cryptography and Coding, Cirencester, Springer LNCS 5921 (2009) 368-382. MR 2775634 (2012c:11263)
  • 4. S. D. Galbraith and R. S. Ruprai, Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval, in P. Q. Nguyen and D. Pointcheval (eds.), PKC 2010, Springer LNCS 6056 (2010) 368-383. MR 2660753
  • 5. S. D. Galbraith and M. Holmes,
    A non-uniform birthday problem with applications to discrete logarithms,
    to appear in Discrete Applied Mathematics (2012).
  • 6. P. Gaudry and E. Schost,
    A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm, in D. A. Buell (ed.), ANTS VI, Springer LNCS 3076 (2004) 208-222. MR 2137355 (2005m:11237)
  • 7. R. Gennaro,
    An Improved Pseudo-random Generator Based on Discrete Log,
    in M. Bellare (ed.), CRYPTO 2000, Springer LNCS 1880 (2000) 469-481. MR 1850061 (2002h:94055)
  • 8. K. Gopalakrishnan, N. Thériault, and C. Z. Yao,
    Solving Discrete Logarithms from Partial Knowledge of the Key,
    in K. Srinathan, C. P. Rangan, and M. Yung, (eds.), INDOCRYPT 2007, Springer LNCS 4859 (2007) 224-237. MR 2570258 (2010k:94038)
  • 9. D. Jao and K. Yoshida,
    Boneh-Boyen signatures and the Strong Diffie-Hellman problem,
    in H. Shacham and B. Waters (eds.), Pairing 2009, Springer LNCS 5671 (2009) 1-16. MR 2737074
  • 10. C. H. Lim and P. J. Lee,
    A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup,
    in B. S. Kaliski Jr. (ed.), CRYPTO 1997, Springer LNCS 1294 (1997) 249-263. MR 1630401 (99b:94036)
  • 11. R. Montenegro and P. Tetali, How long does it take to catch a wild kangaroo? STOC 2009, ACM (2009) 553-560.
  • 12. R. Montenegro,
    Remarks about random walks in the Gaudry-Schost algorithm,
    Emails, 4 January and 5 January 2011.
  • 13. S. Patel and G. Sundaram,
    An Efficient Discrete Log Pseudo Random Generator,
    in H. Krawczyk (ed.), CRYPTO 1998, Springer LNCS 1462 (1998) 304-317. MR 1670959
  • 14. S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inf. Theory, 24 (1978) 106-110. MR 0484737 (58:4617)
  • 15. J. M. Pollard,
    Monte Carlo methods for index computation mod $ p$,
    Mathematics of Computation, 32, No. 143 (1978) 918-924. MR 0491431 (58:10684)
  • 16. J. M. Pollard,
    Kangaroos, Monopoly and discrete logarithms,
    Journal of Cryptology, 13 (2000) 437-447. MR 1788514 (2001i:94059)
  • 17. R. S. Ruprai, Improvements to the Gaudry-Schost Algorithm for Multidimensional discrete logarithm problems and Applications, PhD thesis, Royal Holloway University of London, 2009.
  • 18. B. I. Selivanov,
    On waiting time in the scheme of random allocation of coloured particles,
    Discrete Math. Appl., 5, No. 1 (1995) 73-82. MR 1331936 (96d:60017)
  • 19. 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.
  • 20. 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.
  • 21. P. C. van Oorschot and M. J. Wiener,
    Parallel collision search with cryptanalytic applications,
    Journal of Cryptology, 12 (1999) 1-28. MR 1664774 (99i:94054)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 68W20, 11T71

Retrieve articles in all journals with MSC (2010): 11Y16, 68W20, 11T71

Additional Information

Steven D. Galbraith
Affiliation: Mathematics Department, The University of Auckland, Private Bag 92019, Auckland 1142, New Zealand

John M. Pollard
Affiliation: Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, Berkshire RG8 8EX, United Kingdom

Raminder S. Ruprai
Affiliation: Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX, United Kingdom

Keywords: Discrete logarithm problem (DLP), random walks
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
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society