# Definition of the strong Diffie Hellman problem

I am looking for the definition of the strong Diffie Hellmann problem. However, I can only find definitions for the $$\ell$$ or $$q$$-strong Diffie Hellmann.

Is it possible that the strong Diffie Hellman problem is also called the $$\ell$$ or $$q$$-strong Diffie Hellmann problem?

According to this paper (page 6), the $$q$$-Strong Diffie-Hellman problem (or just Strong Diffie-Hellman problem in short) is the following one: In a bilinear context $$(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T)$$.

Let $$g_1$$ and $$g_2$$ be public generators of $$\mathbb{G}_1$$, and $$\mathbb{G}_2$$.

The adversary receives: $$\left(g^{x^i}_1\right)^q_{i=0}$$ and $$g_2, g_2^x$$, with $$x$$ a random secret scalar, and should output a pair $$\left(c, g^{\frac{1}{x+c}}\right)$$ with $$c$$ a scalar of his choice.

• 2K, congratulations. Now your edits are free :) Mar 16, 2022 at 16:08
• Thanks for your answer and source! Mar 16, 2022 at 19:10
• The link for the pdf doesn't work. Do you have an alternative link or the title/author of the papers? Jan 18 at 0:13
• @user93353 I've changed the link Jan 18 at 10:23
• Thank you ..... Jan 18 at 11:07

Yes, the $$\ell$$ or $$q$$ is related to the parametrization, since the basic idea is to give you a number of known values and ask you to compute a related quantity and consider the hardness of this problem. For example, a Eurocrypt 2006 paper by Cheon available here states:

Given $$g$$ and $$g^{\alpha^i}$$ in an abelian group $$G$$ for $$i=1,2,\ldots,\ell$$ compute $$g^{\alpha^{\ell+1}}.$$ Here $$\alpha \in \mathbb{Z}_p.$$

It was first introduced by Boneh and Boyen to construct a short signature scheme, that is provably secure in the standard model (without random oracles).

• Can you give a source about your definition? Mar 16, 2022 at 15:04
• Thank you for your answer! Mar 16, 2022 at 16:48