Type 1 pairing + LRSW ⇒ DS (Camenisch–Lysyanskaya)

Fully-black-box reduction · standard model · CL04 · security loss: tight: a forger is an LRSW adversary with the same advantage

Statement

Let $(\mathbb{G},{\mathbb{G}}_T,p,g,e)$ be a symmetric bilinear group in which the LRSW assumption holds. Camenisch–Lysyanskaya Scheme A signs messages $m\in {\mathbb{Z}}_p\setminus \{0\}$. It has $\mathsf{sk}=(x,y)\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p^2$ and $\mathsf{vk}=(X,Y)=(g^x,g^y)$; $\mathsf{Sign}(\mathsf{sk},m)$ picks $a\stackrel{\$}{\leftarrow }\mathbb{G}$ and outputs $\sigma =(a,b,c)=(a,a^y,a^{x+mxy})$, and $\mathsf{Vrfy}(\mathsf{vk},m,\sigma )$ accepts iff $a\ne 1$, $e(a,Y)=e(g,b)$ and $e(X,a)\cdot e(X,b{)}^m=e(g,c)$. The scheme is EUF-CMA in the standard model — CL04. CL04 also sign blocks of messages and committed messages, with efficient protocols for proving knowledge of a signature — CL04.

Sketch

Signing is the LRSW oracle. By non-degeneracy of $e$, a triple that verifies on $m$ satisfies $b=a^y$ and $c=a^{x+mxy}$, so a forgery on an unqueried $m\ne 0$ is an LRSW solution; the reduction forwards the signing queries to its oracle and outputs the forgery.

Notes

• Efficiency: a Scheme A signature is three elements of $\mathbb{G}$ — CL04.
• A variant of CL signatures is secure under static assumptions — GLOW12. A slight modification of CL signatures is secure under simple variants of the SDH assumption — PS18.
• LRSW holds for generic algorithms in groups without a pairing (GGM ⇒ LRSW) — LRSW99.