# zbMATH — the first resource for mathematics

Security analysis of the strong Diffie-Hellman problem. (English) Zbl 1129.94017
Vaudenay, Serge (ed.), Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 – June 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34546-9/pbk). Lecture Notes in Computer Science 4004, 1-11 (2006).
Summary: Let $$g$$ be an element of prime order $$p$$ in an abelian group and $$\alpha\in {{\mathbb Z}}_p$$. We show that if $$g, g^{\alpha }$$, and $$g^{\alpha^d}$$ are given for a positive divisor $$d$$ of $$p-1$$, we can compute the secret $$\alpha$$ in $$O(\log p \cdot (\sqrt{p/d}+\sqrt d))$$ group operations using $$O(\max\{\sqrt{p/d},\sqrt d\})$$ memory. If $$g^{\alpha^i} (i=0,1,2,\dots, d)$$ are provided for a positive divisor $$d$$ of $$p+1, \alpha$$ can be computed in $$O(\log p \cdot (\sqrt{p/d}+d))$$ group operations using $$O(\max\{\sqrt{p/d},\sqrt d\})$$ memory. This implies that the strong Diffie-Hellman problem and its related problems have computational complexity reduced by $$O(\sqrt d)$$ from that of the discrete logarithm problem for such primes.
Further we apply this algorithm to the schemes based on the Diffie-Hellman problem on an abelian group of prime order $$p$$. As a result, we reduce the complexity of recovering the secret key from $$O(\sqrt p)$$ to $$O(\sqrt{p/d})$$ for Boldyreva’s blind signature and the original ElGamal scheme when $$p-1$$ (resp. $$p+1)$$ has a divisor $$d \leq p^{1/2}$$ (resp. $$d \leq p^{1/3})$$ and $$d$$ signature or decryption queries are allowed.
For the entire collection see [Zbl 1108.94002].

##### MSC:
 94A60 Cryptography 94A62 Authentication, digital signatures and secret sharing
MIRACL
Full Text:
##### References:
 [1] Abdalla, M., Bellare, M., Rogaway, P.: DHAES: An encryption scheme based on Diffie-Hellman problem. IEEE P1363a Submission (1998), available at: http://grouper.ieee.org/groups/1363/addendum.html [2] Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004) · Zbl 1122.94355 · doi:10.1007/978-3-540-24676-3_14 [3] Boneh, D., Boyen, X.: Short Signatures Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004) · Zbl 1122.94354 · doi:10.1007/978-3-540-24676-3_4 [4] Boneh, D., Boyen, X., Goh, E.: Hierarchical Identity Based Encryption with Constant Size Ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440–456. Springer, Heidelberg (2005) · Zbl 1137.94340 · doi:10.1007/11426639_26 [5] Boneh, D., Boyen, X., Shacham, H.: Short Group Signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004) · Zbl 1104.94044 · doi:10.1007/978-3-540-28628-8_3 [6] Burmester, M., Desmedt, Y.: A Secure and Efficient Conference Key Distribution System (Extended Abstract). In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 275–286. Springer, Heidelberg (1995) · Zbl 0879.94021 · doi:10.1007/BFb0053443 [7] Boneh, D., Gentry, C., Waters, B.: Collution Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 258–275. Springer, Heidelberg (2005) · Zbl 1145.94434 · doi:10.1007/11535218_16 [8] Boneh, D., Lynn, B., Shacham, H.: Short Signatures from the Weil Pairing. ASIACRYPT 2001 17(4), 297–319 (2004); Extended abstract in proceedings of Asiacrypt 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001) · Zbl 1070.94010 [9] den Boer, B.: Diffie-Hellman is as Strong as Discrete Log for Certain Primes. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 530–539. Springer, Heidelberg (1990) · Zbl 0719.94012 · doi:10.1007/0-387-34799-2_38 [10] Boldyreva, A.: Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2002) · Zbl 1033.94552 · doi:10.1007/3-540-36288-6_3 [11] Dodis, Y., Yampolskiy, A.: A Verifiable Random Function with Short Proofs and Keys. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 416–431. Springer, Heidelberg (2005) · Zbl 1081.94521 · doi:10.1007/978-3-540-30580-4_28 [12] Elgamal, T.: A Public Key Cryptosystem and a Signature Scheme based on Discrete Logarithms. IEEE Transactions on Information Theory 31(4), 469–472 (1985) · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074 [13] Gordon, J.: Strong Primes are Easy to Find. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 216–223. Springer, Heidelberg (1985) · Zbl 0596.94016 · doi:10.1007/3-540-39757-4_19 [14] Koblitz, N., Menezes, A.: Pairing-based Cryptography at High Security Levels. In: IMA Conference of Cryptography and Coding 2005, pp. 13–36 (2005) · Zbl 1122.94038 · doi:10.1007/11586821_2 [15] Scott, M.: Multiprecision Integer and Rational Arithmetic C/C++ Library, available at: http://indigo.ie/ mscott/ [16] Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996) · Zbl 0868.94001 · doi:10.1201/9781439821916 [17] Mitsunari, S., Sakai, R., Kasahara, M.: A New Traitor Tracing. IEICE Trans. Fundamentals E85-A(2), 481–484 (2002) [18] Maurer, U., Wolf, S.: The Relationship Between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms. SIAM J. Comput. 28(5), 1689–1721 (1999) · Zbl 1053.94014 · doi:10.1137/S0097539796302749 [19] Recommended Elliptic Curves for Federal Government Use (1999), available at: http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.pdf [20] Pollard, J.: Monte Carlo Methods for Index Computation ( $$\bmod p$$ ). Mathematics of Computation 32, 918–924 (1978) · Zbl 0382.10001 [21] Shoup, V.: Lower bounds for Discrete Logarithms and Related Problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997) · doi:10.1007/3-540-69053-0_18 [22] Teske, E.: Speeding up Pollard’s Rho Method for Computing Discrete Logarithms. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 541–554. Springer, Heidelberg (1998) · Zbl 1066.11513 · doi:10.1007/BFb0054891
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.