Type 3 pairing ⇒ DS (Pointcheval–Sanders)

Free reduction · generic group model · PS16

Statement

Let $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$ be a Type 3 pairing of prime order $p$ and $\tilde{g}$ a generator of ${\mathbb{G}}_2$. Pointcheval–Sanders signatures on $m=(m_1,\dots ,m_r)\in {\mathbb{Z}}_p^r$ have $\mathsf{sk}=(x,y_1,\dots ,y_r)$ and $\mathsf{vk}=(\tilde{g},\tilde{X}={\tilde{g}}^x,{\tilde{Y}}_1={\tilde{g}}^{y_1},\dots ,{\tilde{Y}}_r={\tilde{g}}^{y_r})$. $\mathsf{Sign}$ outputs $\sigma =(h,h^{x+{\sum }_j{y}_j{m}_j})$ for $h\stackrel{\$}{\leftarrow }{\mathbb{G}}_1\setminus \{1\}$, and $\mathsf{Vrfy}$ accepts iff ${\sigma }_1\ne 1$ and $e({\sigma }_1,\tilde{X}{\prod }_j{\tilde{Y}}_j^{m_j})=e({\sigma }_2,\tilde{g})$. The scheme is EUF-CMA against adversaries that are generic in the bilinear group, without random oracles — PS16.

Notes

• Efficiency: a signature is two elements of ${\mathbb{G}}_1$ whatever $r$, and verification costs two pairings. Signatures re-randomize publicly as $({\sigma }_1^t,{\sigma }_2^t)$ — PS16.
• The scheme needs a Type 3 pairing: with an efficiently computable $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1$, the pair $(\psi (\tilde{g}),\psi (\tilde{X}){\prod }_j\psi ({\tilde{Y}}_j{)}^{m_j})$ verifies on every message — standard.
• PS16 prove EUF-CMA from an interactive assumption that holds in the generic group model, and that assumption, like the LRSW assumption behind Camenisch–Lysyanskaya signatures, essentially states EUF-CMA security; a slight modification of the scheme is secure under simple variants of the SDH assumption — PS18.