Definition of the strong Diffie Hellman problem

Question

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?

Answer 1

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.

Answer 2

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).