Computing Interval Discrete Logarithm Problem with Restricted Jump Method

• Autorzy: Qi Bin , Ma Jie , Lv Kewei

Identyfikatory

DOI

10.3233/FI-2020-1986

• Języki publikacji: EN

Abstrakty

EN

The interval discrete logarithm problem(IDLP) is to find a solution n such that gⁿ = h in a finite cyclic group G = 〈g 〉, where h ∈ G and n belongs to a given interval. To accelerate solving IDLP, a restricted jump method is given to speed up Pollard’s kangaroo algorithm in this paper. Since the Pollard’ kangaroo-like method need to compute the intermediate value during every iteration, the restricted jump method gives another way to reuse the intermediate value so that each iteration is speeded up at least 10 times. Actually, there are some variants of kangaroo method pre-compute the intermediate value and reuse the pre-computed value in each iteration. Different from the pre-compute method that reuse the pre-computed value, the restricted jump method reuse the value naturally arised in pervious iteration, so that the improved algorithm not only avoids precomputation, but also speeds up the efficiency of each iteration. So only two or three large integer multiplications are needed in each iteration of the restricted jump method. And the average large integer multiplication times is (1.633 + o (1))√N in restricted jump method, which is verified in the experiment.

Słowa kluczowe

EN

interval discrete logarithm algorithm; IDLP; pollards kangaroo algorithm; jumping distance set; coverage rate

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 2
• Strony: 189--201
• Opis fizyczny: Bibliogr. 19 poz., tab.

Twórcy

autor

Qi Bin

• State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China

autor

Ma Jie

• State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China

autor

Lv Kewei

• State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China

Bibliografia

• [1] Boneh D, Goh E, Nissim K. Evaluating 2-DNF formulas on ciphertexts. In: Theory of Cryptography Conference. Springer, 2005 pp. 325-341. doi:10.1007/978-3-540-30576-7_18.
• [2] Fowler A, Galbraith S. Kangaroo Methods for Solving the Interval Discrete Logarithm Problem 2015. arXiv preprint arXiv:1501.07019.
• [3] Gopalakrishnan K, Thériault N, Yao CZ. Solving discrete logarithms from partial knowledge of the key. In: International Conference on Cryptology in India. Springer, 2007 pp. 224-237. doi:10.1007/978-3-540-77026-8_17.
• [4] Lange T, Van Vredendaal C, Wakker M. Kangaroos in side-channel attacks. In: International Conference on Smart Card Research and Advanced Applications. Springer, 2014 pp. 104-121. ID:c1c4c98f98c7ca3cb1b1f4208b95e8b8.
• [5] Lim CH, Lee PJ. A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Annual International Cryptology Conference. Springer, 1997 pp. 249-263.
• [6] Patel S, Sundaram GS. An efficient discrete log pseudo random generator. In: Annual International Cryptology Conference. Springer, 1998 pp. 304-317.
• [7] Van Oorschot PC, Wiener MJ. On Diffie-Hellman key agreement with short exponents. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 1996 pp. 332-343.
• [8] Gennaro R. An improved pseudo-random generator based on discrete log. In: Annual International Cryptology Conference. Springer, 2000 pp. 469-481. doi:10.1007/s00145-004-0215-y.
• [9] Cheon JH. Security analysis of the strong Diffie-Hellman problem. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2006 pp. 1-11. doi:10.1007/11761679_1.
• [10] Jao D, Yoshida K. Boneh-Boyen signatures and the strong Diffie-Hellman problem. In: International Conference on Pairing-Based Cryptography. Springer, 2009 pp. 1-16. doi:10.1007/978-3-642-03298-1_1.
• [11] Galbraith S, Pollard J, Ruprai R. Computing discrete logarithms in an interval. Math. Comp, 2013. 82(282):1181-1195. doi:10.1090/S0025-5718-2012-02641-X.
• [12] Galbraith SD, Ruprai RS. Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval. In: International Workshop on Public Key Cryptography. Springer, 2010 pp. 368-383. doi:10.1007/978-3-642-13013-7_22.
• [13] Qi B, Ma J, Lv K. Using Equivalent Class to Solve Interval Discrete Logarithm Problem. In: International Conference on Information and Communications Security. Springer, 2019 pp. 397-412. doi:10.1007/978-3-642-13013-7_22.
• [14] Shanks D. Class number, a theory of factorization, and genera. In: Proc. of Symp. Math. Soc., volume 20. 1971 pp. 41-440. doi:10.1090/pspum/020/0316385.
• [15] Pollard JM. Monte Carlo methods for index computation (mod p). Math. Comp., 1978. 32(143):918-924.
• [16] Pollard JM. Kangaroos, monopoly and discrete logarithms. J. Cryptology, 2000. 13(4):437-447. doi:10.1007/s001450010010.
• [17] Cheon JH, Hong J, Kim M. Speeding up the Pollard rho method on prime fields. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2008 pp.471-488. doi:10.1007/978-3-540-89255-7_29.
• [18] Wang Y, Lv K. Improved method on the discrete logarithm problem in an interval. J. Cryptolo. Res., 2015. 2(6):570-582. doi:10.13868/j.cnki.jcr.000103.
• [19] Gallagher P. Digital signature standard (DSS). Federal Information Processing Standards Publications, 2013. pp. 186-3.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).