I'm having trouble finding the first paper that introduced the $q$-Strong Bilinear Diffie-Hellman ($q$-SBDH) assumption which, roughly speaking, is:

Let $\mathbb{G},\mathbb{G}_T$ be two groups of order $p$, with a bilinear map $e$ from $\mathbb{G}$ to $\mathbb{G}_T$. Let $s \stackrel{$}{\leftarrow} \mathbb{Z}^*_p$ be a trapdoor. Given $pp = \langle g, g^s, g^{s^2},..., g^{s^q} \rangle \in \mathbb{G}^{q+1}$, an adversary has negligible probability of finding $\langle c, e(g, g)^{\frac{1}{s+c}} \rangle$ for some $c \in \mathbb{Z_p} \setminus \{-s\}$.

Some papers seem to point to Dan Boneh's "Short signatures without random oracles and the SDH assumption in bilinear groups" (Journal of Cryptography, 2008). However, as far as I've read the paper, only $q$-SDH is defined there, not $q$-SBDH.

Any help would be appreciated!

  • $\begingroup$ The q-SDH assumption is about groups with a bilinear pairing. This is clearly stated in the cited article. $\endgroup$
    – user27950
    Sep 25, 2017 at 3:34
  • $\begingroup$ Eh, right. $q$-SDH and $q$-SBDH are assumptions in groups with pairings, but they are different assumptions. In $q$-SDH, it's hard to find $\langle c, g^{\frac{1}{s+c}} \rangle$, while in $q$-SBDH it's hard to find $\langle c, e(g,g)^{\frac{1}{s+c}} \rangle$. $\endgroup$ Sep 25, 2017 at 4:14
  • $\begingroup$ Ok, maybe this one: eprint.iacr.org/2004/172.pdf $\endgroup$
    – user27950
    Sep 25, 2017 at 4:34
  • $\begingroup$ Thanks! Where exactly? They define $q$-BDHI which asks the adversary to find $e(g,g)^{\frac{1}{x}}$, which is different. $\endgroup$ Sep 27, 2017 at 19:07

1 Answer 1


After some more investigation, the earliest paper I could find that introduces $q$-Strong Bilinear Diffie-Hellman was Reducing Trust in the PKG in Identity Based Cryptosystems by Vipul Goyal in CRYPTO 2007.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.