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

Fully-black-box reduction · standard model · BB04a · security loss: tight up to a factor 2: for $q_S<q$ signing queries the forger’s success probability is at most twice the $q$-SDH advantage plus $O(q_S/p)$

Statement

Let $(\mathbb{G},{\mathbb{G}}_T,p,g,e)$ be a bilinear group in which q-SDH is hard for every polynomial $q=q(\lambda )$. The Boneh–Boyen signature scheme with message space ${\mathbb{Z}}_p$ has $\mathsf{sk}=(x,y)\stackrel{\$}{\leftarrow }({\mathbb{Z}}_p^{\ast }{)}^2$ and $\mathsf{vk}=(g^x,g^y)$. $\mathsf{Sign}(\mathsf{sk},m)$ picks $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ with $x+m+yr\ne 0$ and outputs $(\sigma ,r)$ with $\sigma =g^{1/(x+m+yr)}$, and $\mathsf{Vrfy}(\mathsf{vk},m,(\sigma ,r))$ accepts iff $e(\sigma ,g^x{g}^m(g^y{)}^r)=e(g,g)$. The scheme is existentially unforgeable under adaptive chosen-message attack in the standard model, and a signature is one element of $\mathbb{G}$ and one element of ${\mathbb{Z}}_p$ — BB04a.

Notes

• The weak scheme with $\mathsf{vk}=g^x$ and $\sigma =g^{1/(x+m)}$ is existentially unforgeable under a weak chosen-message attack, in which the forger names its signing queries before it sees $\mathsf{vk}$ — BB04a.
• The journal version proves the full scheme strongly unforgeable under adaptive chosen-message attack — BB08.
• BB04a state the scheme and the assumption for a pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$ between two source groups, with $\sigma \in {\mathbb{G}}_1$ and $\mathsf{vk}\in {\mathbb{G}}_2^2$; the symmetric form above is the special case ${\mathbb{G}}_1={\mathbb{G}}_2$ — BB04a.