Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 6056))

Included in the following conference series:

Abstract

The Pollard kangaroo method solves the discrete logarithm problem (DLP) in an interval of sizeN with heuristic average case expected running time approximately\(2 \sqrt{N}\) group operations. It is well-known that the Pollard rho method can be sped-up by using equivalence classes (such as orbits of points under an efficiently computed group homomorphism), but such ideas have not been used for the DLP in an interval. Indeed, it seems impossible to implement the standard kangaroo method with equivalence classes.

The main result of the paper is to give an algorithm, building on work of Gaudry and Schost, to solve the DLP in an interval of sizeN with heuristic average case expected running time of close to\(1.36\sqrt{N}\) group operations for groups with fast inversion. In practice the algorithm is not quite this fast, due to the usual problems with pseudorandom walks such as fruitless cycles. In addition, we present experimental results.

Similar content being viewed by others

Keywords

References

  1. Boneh, D., Goh, E.J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)

    Google Scholar 

  2. Bos, J.W., Kleinjung, T., Lenstra, A.K.: On the use of the negation map in the Pollard Rho method. (preprint, 2010)

    Google Scholar 

  3. Cheon, J.H.: Security Analysis of the Strong Diffie-Hellman Problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 1–11. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  4. Cofman, E.G., Flajolet, P., Flatto, L., Hofri, M.: The Maximum of a Random Walk and its Application to Rectangle Packing. Technical report, INRIA (1997)

    Google Scholar 

  5. Cohen, H., Frey, G.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. In: Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton (2005)

    Google Scholar 

  6. Duursma, I.M., Gaudry, P., Morain, F.: Speeding up the discrete log computation on curves with automorphisms. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 103–121. Springer, Heidelberg (1999)

    Google Scholar 

  7. Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 518–535. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  8. Galbraith, S.D., Ruprai, R.S.: An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems. In: Parker, M.G. (ed.) IMACC 2009. LNCS, vol. 5921, pp. 368–382. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  9. Galbraith, S.D., Pollard, J.M., Ruprai, R.S.: Improving kangaroo and Gaudry-Schost methods for solving the DLP in an interval (in preparation) (2010)

    Google Scholar 

  10. Galbraith, S.D., Holmes, M.: A non-uniform birthday problem with applications to discrete logarithms (in preparation) (2010)

    Google Scholar 

  11. Gallant, R., Lambert, R., Vanstone, S.: Improving the Parallelized Pollard Lambda Search on Binary Anomalous Curves. Mathematics of Computation 69, 1699–1705 (2000)

    Article MATH MathSciNet  Google Scholar 

  12. Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  13. Gaudry, P., Harley, R.: Counting Points on Hyperelliptic Curves over Finite Fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 313–332. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  14. Gaudry, P., Schost, E.: A low-memory parallel version of Matsuo, Chao and Tsujii’s algorithm. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 208–222. Springer, Heidelberg (2004)

    Google Scholar 

  15. Gennaro, R.: An Improved Pseudo-random Generator Based on Discrete Log. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 469–481. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  16. Gopalakrishnan, K., Thériault, N., Yao, C.Z.: Solving Discrete Logarithms from Partial Knowledge of the Key. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 224–237. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  17. Jao, D., Yoshida, K.: Boneh-Boyen signatures and the Strong Diffie-Hellman problem. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 1–16. Springer, Heidelberg (2009)

    Google Scholar 

  18. Lim, C.H., Lee, P.J.: A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 249–263. Springer, Heidelberg (1997)

    Google Scholar 

  19. Montenegro, R., Tetali, P.: How long does it take to catch a wild kangaroo? In: 41st ACM Symposium on Theory of Computing (2009)

    Google Scholar 

  20. Nishimura, K., Sibuya, M.: Probability to meet in the middle. Journal of Cryptology 2, 13–22 (1990)

    Article MATH MathSciNet  Google Scholar 

  21. van Oorschot, P.C., Wiener, M.J.: On Diffie-Hellman Key Agreement with Short Exponents. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 332–343. Springer, Heidelberg (1996)

    Google Scholar 

  22. van Oorschot, P.C., Wiener, M.J.: Parallel collision Search with Cryptanalytic Applications. Journal of Cryptology 12, 1–28 (1999)

    Article MATH  Google Scholar 

  23. Patel, S., Sundaram, G.: An Efficient Discrete Log Pseudo Random Generator. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 304–317. Springer, Heidelberg (1998)

    Google Scholar 

  24. Pollard, J.M.: Monte Carlo Methods for Index Computation modp. Mathematics of Computation 32(143), 918–924 (1978)

    Article MATH MathSciNet  Google Scholar 

  25. Pollard, J.M.: Three kangaroos are better than two! Private Communication (2009)

    Google Scholar 

  26. Pollard, J.M.: Kangaroos, Monopoly and Discrete Logarithms. Journal of Cryptology 13, 437–447 (2000)

    Article MATH MathSciNet  Google Scholar 

  27. Ruprai, R.S.: An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems and applications. PhD Thesis, Royal Holloway, University of London (2010)

    Google Scholar 

  28. Selivanov, B.I.: On waiting time in the scheme of random allocation of coloured particles. Discrete Math. Appl. 5(1), 73–82 (1995)

    Article MATH MathSciNet  Google Scholar 

  29. Wiener, M.J., Zuccerato, R.J.: Faster Attacks on Elliptic Curve Cryptosystems. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 190–200. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematics Department, Auckland University, Auckland, New Zealand

    Steven D. Galbraith

  2. Mathematics Department, Royal Holloway University of London, Egham, Surrey, TW20 0EX, UK

    Raminder S. Ruprai

Authors
  1. Steven D. Galbraith

    You can also search for this author inPubMed Google Scholar

  2. Raminder S. Ruprai

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Département d’Informatique, École Normale Supérieure, 45 rue d’Ulm, 75230, Paris Cedex 05, France

    Phong Q. Nguyen  & David Pointcheval  & 

Rights and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Galbraith, S.D., Ruprai, R.S. (2010). Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval. In: Nguyen, P.Q., Pointcheval, D. (eds) Public Key Cryptography – PKC 2010. PKC 2010. Lecture Notes in Computer Science, vol 6056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13013-7_22

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp