Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs

Kim, Minkyu; Cheon, Jung Hee; Lee, In-Sok

doi:10.1090/S0025-5718-2014-02813-5

Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs
HTML articles powered by AMS MathViewer

by Minkyu Kim, Jung Hee Cheon and In-Sok Lee PDF

Math. Comp. 83 (2014), 1993-2004 Request permission

Abstract:

We investigate a recently proposed algorithm solving the strong discrete logarithm problem with auxiliary inputs, and show that this algorithm in general is not more efficient than ordinary discrete-logarithm-solving algorithms such as Pollard’s rho method, by analyzing a lower bound on the sum of digits of integers.

References

Dan Boneh and Xavier Boyen, Efficient selective-ID secure identity-based encryption without random oracles, Advances in cryptology—EUROCRYPT 2004, Lecture Notes in Comput. Sci., vol. 3027, Springer, Berlin, 2004, pp. 223–238. MR 2153175, DOI 10.1007/978-3-540-24676-3_{1}4
Dan Boneh and Xavier Boyen, Short signatures without random oracles and the SDH assumption in bilinear groups, J. Cryptology 21 (2008), no. 2, 149–177. MR 2386625, DOI 10.1007/s00145-007-9005-7
D. Boneh, X. Boyen, and E. Goh, Hierarchical identity based encryption without constant size ciphertext, in Proceedings of Eurocrypt 2005, LNCS 3494, pp. 440-456, 2005.
Dan Boneh, Xavier Boyen, and Hovav Shacham, Short group signatures, Advances in cryptology—CRYPTO 2004, Lecture Notes in Comput. Sci., vol. 3152, Springer, Berlin, 2004, pp. 41–55. MR 2147494, DOI 10.1007/978-3-540-28628-8_{3}
D. R. L. Brown and R. P. Gallant, The static Diffie-Hellman problem, Cryptology ePrint Archive, Report no. 2004/306, 2004. Available from http://eprint.iacr.org/2004/306.
Dan Boneh, Craig Gentry, and Brent Waters, Collusion resistant broadcast encryption with short ciphertexts and private keys, Advances in cryptology—CRYPTO 2005, Lecture Notes in Comput. Sci., vol. 3621, Springer, Berlin, 2005, pp. 258–275. MR 2237311, DOI 10.1007/11535218_{1}6
Xavier Boyen, The uber-assumption family: a unified complexity framework for bilinear groups, Pairing-based cryptography—Pairing 2008, Lecture Notes in Comput. Sci., vol. 5209, Springer, Berlin, 2008, pp. 39–56. MR 2733903, DOI 10.1007/978-3-540-85538-5_{3}
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}
Jung Hee Cheon, Discrete logarithm problems with auxiliary inputs, J. Cryptology 23 (2010), no. 3, 457–476. MR 2643686, DOI 10.1007/s00145-009-9047-0
Bert den Boer, Diffie-Hellman is as strong as discrete log for certain primes, Advances in cryptology—CRYPTO ’88 (Santa Barbara, CA, 1988) Lecture Notes in Comput. Sci., vol. 403, Springer, Berlin, 1990, pp. 530–539. MR 1046405, DOI 10.1007/0-387-34799-2_{3}8
Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654. MR 437208, DOI 10.1109/tit.1976.1055638
Florian Hess, Pairing lattices, Pairing-based cryptography—Pairing 2008, Lecture Notes in Comput. Sci., vol. 5209, Springer, Berlin, 2008, pp. 18–38. MR 2733902, DOI 10.1007/978-3-540-85538-5_{2}
A. A. Karatsuba and Y. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics Doklady, Vol. 7, pp. 595–596, 1963.
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
Ueli M. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Advances in cryptology—CRYPTO ’94 (Santa Barbara, CA, 1994) Lecture Notes in Comput. Sci., vol. 839, Springer, Berlin, 1994, pp. 271–281. MR 1316411, DOI 10.1007/3-540-48658-5_{2}6
Ueli M. Maurer and Stefan Wolf, The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms, SIAM J. Comput. 28 (1999), no. 5, 1689–1721. MR 1694168, DOI 10.1137/S0097539796302749
H. Minkowski, Geometrie der Zahlen, Leipzig und Berlin, Druck und Verlag von B. G. Teubner, 1910.
S. Mitsunari, R. Sakai, and M. Kasahara, A new traitor tracing, IEICE Trans. Fundamentals, Vol. E58-A, No. 2, pp. 481-484, 2002.
Trygve Nagell, Introduction to number theory, 2nd ed., Chelsea Publishing Co., New York, 1964. MR 0174513
Tatsuaki Okamoto, Efficient blind and partially blind signatures without random oracles, Theory of cryptography, Lecture Notes in Comput. Sci., vol. 3876, Springer, Berlin, 2006, pp. 80–99. MR 2241667, DOI 10.1007/11681878_{5}
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
T. Satoh, On generalization of Cheon’s algorithms, Cryptology ePrint Archive, Report no. 2009/058, 2009. Available from http://eprint.iacr.org/2009/058.
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757