Type 1 pairing + CDH ⇒ Waters signatures

Fully-black-box reduction · standard model · Wat05 · security loss: factor $O(n{q}_S)$ for $n$-bit messages and $q_S$ signing queries

Statement

Let $(\mathbb{G},{\mathbb{G}}_T,p,g,e)$ be a symmetric bilinear group in whose group $\mathbb{G}$ CDH is hard. The Waters signature scheme for $n$-bit messages has $\mathsf{vk}=(g,g_1=g^{\alpha },g_2,u^{\prime },u_1,\dots ,u_n)$ with $\alpha \stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and $g_2,u^{\prime },u_i\stackrel{\$}{\leftarrow }\mathbb{G}$, and $\mathsf{sk}=g_2^{\alpha }$. Write $U(m)=u^{\prime }{\prod }_{i:m_i=1}{u}_i$. $\mathsf{Sign}(\mathsf{sk},m)$ picks $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and outputs $\sigma =({\sigma }_1,{\sigma }_2)=(g_2^{\alpha }\cdot U(m{)}^r,g^r)$, and $\mathsf{Vrfy}(\mathsf{vk},m,\sigma )$ accepts iff $e({\sigma }_1,g)=e(g_1,g_2)\cdot e(U(m),{\sigma }_2)$. The scheme is EUF-CMA in the standard model: every efficient forger yields an efficient CDH solver — Wat05.

Sketch

Given $(g,g^a,g^b)$, the reduction sets $g_1=g^a$ and $g_2=g^b$, and chooses $u^{\prime },u_i$ so that $U(m)=g_2^{F(m)}{g}^{J(m)}$ for functions $F,J$ it knows, with $F(m)\not\equiv 0\mathrm{mod}p$ on every queried message and $F(m^{\ast })\equiv 0$ on the forgery’s message with probability $\Omega (1/(n{q}_S))$. It answers a query with $F(m)\not\equiv 0$ by $\sigma =(g_1^{-J(m)/F(m)}U(m{)}^{r^{\prime }},g_1^{-1/F(m)}{g}^{r^{\prime }})$, a real signature with $r=r^{\prime }-a/F(m)$. A forgery on $m^{\ast }$ with $F(m^{\ast })\equiv 0$ gives $g^{ab}={\sigma }_1/{\sigma }_2^{J(m^{\ast })}$.

Notes

• The reduction loses a factor $O(n{q}_S)$ — HJK12. Recasting $U$ as a programmable hash function improves the loss to $O(\sqrt{n}{q}_S)$ — HK08. A variant that encodes messages so that any two encodings are far apart in Hamming distance is EUF-CMA under CDH with loss $O(q_S)$ — HJK12.
• Signatures re-randomize publicly as $({\sigma }_{1}U(m{)}^t,{\sigma }_2{g}^t)$, so the scheme is not SUF-CMA — standard. Every simple reduction of EUF-CMA security to a non-interactive hardness assumption, one that runs the forger only as straight-line instances one after another — MP18 — loses a factor $\Omega (q_S)$, unless the assumption is false, so the $O(q_S)$ loss of the Hamming-distance variant is optimal up to a constant factor among simple reductions (barrier) — HJK12.
• Efficiency: a signature is two elements of $\mathbb{G}$ and the verification key $n+4$, and verification costs two pairings once $e(g_1,g_2)$ is precomputed — Wat05.
• Messages of arbitrary length can be hashed to $n$ bits with a collision-resistant hash function before signing — standard.
• A different analysis of Waters signatures has the simulator predict a prefix of the message the forger will sign — HW09.
• The same hash $U$ gives the Waters IBE under decisional BDH (DBDH ⇒ IBE (Waters, standard model)) — Wat05.