$q$-Strong Diffie-Hellman assumption

Given the power sequence $(g,g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^q})$ in a bilinear group with secret $\tau$, no efficient adversary can output a pair $(c,g^{1/(\tau +c)})$ with $c\in {\mathbb{Z}}_p\setminus \{-\tau \}$.

Assumption

The assumption concerns a bilinear group generator $\mathsf{GrGen}$, which on input $1^{\lambda }$ outputs $(\mathbb{G},{\mathbb{G}}_T,p,g,e)$: cyclic groups $\mathbb{G}$ and ${\mathbb{G}}_T$ of prime order $p$, a generator $g$ of $\mathbb{G}$, and an efficiently computable non-degenerate bilinear pairing $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{q\text{-sdh}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG, \GG_T, p, g, e) \gets \GrGen(1^\secpar)$
\State $\tau \getsr \ZZ_p^{*}$
\State $(c, h) \gets \calA(1^\secpar, \GG, \GG_T, p, g, e, g^{\tau}, g^{\tau^{2}}, \ldots, g^{\tau^{q}})$
\Return $[c \in \ZZ_p \setminus \{-\tau\} \wedge h = g^{1/(\tau + c)}]$
\end{algorithmic}
\end{algorithm}

$q$-SDH is hard for $\mathsf{GrGen}$ if for every polynomial $q=q(\lambda )$ and all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{q\text{-sdh}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{q\text{-sdh}}(\lambda )=1\right]$$

is negligible.

The assumption is from BB04a, stated there for a pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$ between two source groups; the form above, with ${\mathbb{G}}_1={\mathbb{G}}_2$, is the one KZG10 use. An instance for $q$ yields one for every $q^{\prime }\le q$ by dropping powers, so hardness for a larger $q$ is the stronger assumption — folklore.

Participates in

Builds on $q$-Strong Diffie-Hellman assumption

• Bilinear pairing + q-SDH ⇒ DS (Boneh–Boyen)
• Bilinear pairing + q-SDH ⇒ PCS