Abstract
Let g be an element of prime order p in an abelian group, and let α∈ℤ p . We show that if g,g α, and \(g^{\alpha^{d}}\) are given for a positive divisor d of p−1, the secret key α can be computed deterministically in \(O(\sqrt{p/d}+\sqrt{d})\) exponentiations by using \(O(\max\{\sqrt{p/d},\sqrt{d}\})\) storage. If \(g^{\alpha^{i}}\) (i=0,1,2,…,2d) is given for a positive divisor d of p+1, α can be computed in \(O(\sqrt{p/d}+d)\) exponentiations by using \(O(\max\{\sqrt{p/d},\sqrt{d}\})\) storage. We also propose space-efficient but probabilistic algorithms for the same problem, which have the same computational complexities with the deterministic algorithm.
As applications of the proposed algorithms, we show that the strong Diffie–Hellman problem and related problems with public \(g^{\alpha},\ldots,g^{\alpha^{d}}\) have computational complexity up to \(O(\sqrt{d}/\log p)\) less than the generic algorithm complexity of the discrete logarithm problem when p−1 (resp. p+1) has a divisor d≤p 1/2 (resp. d≤p 1/3). Under the same conditions for d, the algorithm is also applicable to recovering the secret key in \(O(\sqrt{p/d}\cdot \log p)\) for Boldyreva’s blind signature scheme and the textbook ElGamal scheme when d signature or decryption queries are allowed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Abdalla, M. Bellare, P. Rogaway, DHAES: An encryption scheme based on Diffie–Hellman problem. IEEE P1363a Submission (1998). Available at http://grouper.ieee.org/groups/1363/addendum.html
E. Bach, Explicit bounds for primality testing and related problems. Math. Comput. 55, 355–380 (1990)
D. Boneh, X. Boyen, Efficient selective-ID secure identity-based encryption without random oracles, in Proceedings of Eurocrypt 2004, LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 223–238
D. Boneh, X. Boyen, Short signatures without random oracles, in Proceedings of Eurocrypt 2004, LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 56–73
D. Boneh, X. Boyen, Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(3), 149–177 (2008)
D. Boneh, A. Joux, P. Nguyen, Why textbook ElGamal and RSA encryption are insecure, in Proceedings of Asiacrypt 2000, LNCS, vol. 1976 (Springer, Berlin, 2000), pp. 30–43
D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Proceedings of Crypto 2004, LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 41–55
D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing. J. Cryptol. 17(4), 297–319 (2004). Extended abstract in proceedings of Asiacrypt 2001, LNCS, vol. 2248 (Springer, Berlin, 2001), pp. 514–532
D. Boneh, X. Boyen, E. Goh, Hierarchical identity based encryption with constant size ciphertext, in Proceedings of Eurocrypt 2005, LNCS, vol. 3494 (Springer, Berlin, 2005), pp. 440–456. A full paper is available in http://crypto.stanford.edu/~dabo/papers/shibe.pdf
D. Boneh, C. Gentry, B. Waters, Collution resistant broadcast encryption with short ciphertexts and private keys, in Proceedings of Crypto 2005, LNCS, vol. 3621 (Springer, Berlin, 2005), pp. 258–275
A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the Gap–Diffie–Hellman-group signature scheme, in Proceedings of Public Key Cryptography 2003, LNCS, vol. 2567 (Springer, Berlin, 2003), pp. 31–46
X. Boyen, The uber-assumption family—a unified complexity framework for bilinear groups, in Proceedings of Pairing 2008, LNCS, vol. 5209 (Springer, Berlin, 2008), pp. 39–56
D. Brown, R. Gallant, The static Diffie–Hellman problem. Available in http://eprint.iacr.org/2004/306
M. Burmester, Y. Desmedt, A secure and efficient conference key distribution system (Extended Abstract), in Proceedings of Eurocrypt 1994, LNCS, vol. 950 (Springer, Berlin, 1994), pp. 275–286
J. Cheon, Security analysis of the strong Diffie–Hellman problem, in Proceedings of Eurocrypt 2006, LNCS, vol. 4004 (Springer, Berlin, 2006), pp. 1–11
B. den Boer, Diffie–Hellman is as strong as discrete log for certain primes, in Proceedings of Crypto ’88, LNCS, vol. 403 (Springer, Berlin, 1989), pp. 530–539
Y. Dodis, A. Yampolskiy, A verifiable random function with short proofs and keys, in Proceedings of Public Key Cryptography 2005, LNCS, vol. 3386 (Springer, Berlin, 2005), pp. 416–431
T. Elgamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)
K. Ford, The distribution of integers with a divisor in a given interval. Ann. Math. (2008, to appear)
S. Galbraith, K. Paterson, N. Smart, Pairings for cryptographers. Discrete Appl. Math. 156(16), 3113–3121 (2008)
J. Gordon, Strong primes are easy to find, in Proceedings of Eurocrypt ’84 (Springer, Berlin, 1984), pp. 216–223
D. Jao, K. Yoshida, Boneh–Boyen signatures and the strong Diffie-Hellman problem, in Proceedings of Pairing (2009, to appear)
N. Koblitz, A. Menezes, Pairing-based cryptography at high security levels, in Proceedings of IMA Conference of Cryptography and Coding 2005, pp. 13–36
S. Kozaki, T. Kutsuma, K. Matsuo, Remarks on Cheon’s algorithms for pairing-related problems, in Proceedings of Pairing 2007, LNCS, vol. 4575 (Springer, Berlin, 2007), pp. 302–316
U. Maurer, S. Wolf, The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms. SIAM J. Comput. 28(5), 1689–1721 (1999)
A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 1996)
S. Mitsunari, R. Sakai, M. Kasahara, A new traitor tracing. IEICE Trans. Fundam. E85-A(2), 481–484 (2002)
V. Nechaev, Complexity of a deterministic algorithm for the discrete logarithm. Math. Zamet. 55, 91–101 (1994). English translation in Math. Notes 55(2), 165–172 (1994)
T. Okamoto, Efficient blind and partially blind signatures without random oracles, in Proceedings in TCC 2006, LNCS, vol. 3876 (Springer, Berlin, 2006), pp. 80–99
J. Pollard, Monte Carlo methods for index computation (mod p). Math. Comput. 32, 918–924 (1978)
J. Pollard, Kangaroos, monopoly and discrete logarithms. J. Cryptol. 13(4), 437–447 (2000)
Recommended Elliptic Curves for Federal Government Use, Available at http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.pdf, 1999
T. Satoh, On generalization of Cheon’s algorithms. Preprint, 2008
M. Scott, Multiprecision Integer and Rational Arithmetic C/C++ Library. Available at http://indigo.ie/~mscott/
V. Shoup, Searching for primitive roots in finite fields. Math. Comput. 58, 369–380 (1992)
V. Shoup, Lower bounds for discrete logarithms and related problems, in Proceedings of Eurocrypt ’97, LNCS, vol. 1233 (Springer, Berlin, 1997), pp. 256–66
V. Shoup, A Computational Introduction to Number Theory and Algebra (Cambridge University Press, Cambridge, 2005)
I. Shparlinski, On finding primitive roots in finite fields. Theor. Comput. Sci. 157, 273–275 (1996)
D. Sun, Elliptic curves with the minimized security loss of the strong Diffie–Hellman problem, Ph.D. Dissertation, Seoul National University, 2007. Available at http://library.snu.ac.kr/DetailView.jsp?uid=4&cid=2857710
G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory (Cambridge University Press, Cambridge, 1995)
E. Teske, Speeding up Pollard’s rho method for computing discrete logarithms, in Proceedings of Algorithmic Number Theory Symposium III, LNCS, vol. 1423 (Springer, Berlin, 1998), pp. 541–554
Y. Wang, On the least primitive root of a prime. Sci. Sin. 10(1), 1–14 (1961)
K. Yoshida, Boneh–Boyen signatures and the strong Diffie–Hellman problem, Master Thesis, University of Waterloo, 2009. Available at http://uwspace.uwaterloo.ca/handle/10012/4219
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Phong Q. Nguen
The preliminary version of this paper appeared in the Proceedings of Eurocrypt 2006, Lecture Notes in Computer Science 4004, Springer-Verlag [15].
Rights and permissions
About this article
Cite this article
Cheon, J.H. Discrete Logarithm Problems with Auxiliary Inputs. J Cryptol 23, 457–476 (2010). https://doi.org/10.1007/s00145-009-9047-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-009-9047-0