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
Additional Information
- Minkyu Kim
- Affiliation: The Attached Institute of ETRI, P.O. Box 1, Yuseong, Daejeon, 305-600, Korea
- Email: mkkim@ensec.re.kr
- Jung Hee Cheon
- Affiliation: ISaC and Department of Mathematical Sciences, Seoul National University, Seoul 151-747, Korea
- Email: jhcheon@snu.ac.kr
- In-Sok Lee
- Affiliation: ISaC and Department of Mathematical Sciences, Seoul National University, Seoul 151-747, Korea
- Email: isll@snu.ac.kr
- Received by editor(s): February 14, 2012
- Received by editor(s) in revised form: November 1, 2012
- Published electronically: February 11, 2014
- Additional Notes: This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2012-0001243)
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 83 (2014), 1993-2004
- MSC (2010): Primary 68Q25; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-2014-02813-5
- MathSciNet review: 3194138