Generic bilinear group model ⇒ asymmetric q-SDH

Free reduction · generic group model · BB08 · security loss: a generic algorithm that succeeds with constant probability makes $\Omega (\sqrt{p/q})$ group-operation and pairing queries, for $q=O(p^{1/3})$

Statement

In the generic bilinear group model, the asymmetric $q$-SDH problem is hard in groups of prime order $p$: every generic algorithm that, given $(g_1,g_1^{\tau },\dots ,g_1^{{\tau }^q},g_2,g_2^{\tau })$, outputs $(c,g_1^{1/(\tau +c)})$ with constant probability makes $\Omega (\sqrt{p/q})$ oracle queries, provided $q=O(p^{1/3})$ — BB08. The $q$-SDH assumption was introduced in BB04a.

Notes

• When $p-1$ has a divisor $d\le q$ with $d\approx p^{1/3}$, Cheon’s algorithm recovers $\tau$ from $g_1$, $g_1^{\tau }$ and $g_1^{{\tau }^d}$ with about $p^{1/3}$ group operations up to a logarithmic factor, which for $q\approx p^{1/3}$ meets the bound — Che06.