Prime-order DDH ⇒ Katz–Wang signatures

Fully-black-box reduction · random oracle model · KW03 · security loss: tight

Statement

The Katz–Wang signature scheme has public key $(g,h,y_1=g^x,y_2=h^x)$ in a group of prime order $p$, and a signature on $m$ is a Fiat–Shamir proof that $(g,h,y_1,y_2)$ is a Diffie–Hellman tuple: $(c,s)$ with $c=H(\mathsf{pk},g^r,h^r,m)$ and $s=r+cx\mathrm{mod}p$. The scheme is EUF-CMA secure in the random-oracle model if DDH is hard in prime-order groups, with a tight reduction — KW03.

Sketch

Given a tuple $(g,h,y_1,y_2)$, the distinguisher uses it as the public key, answers signing queries with the HVZK simulator by programming $H$, and outputs “Diffie–Hellman” iff the forgery verifies. On a Diffie–Hellman tuple the simulation is perfect up to programming collisions. On a random tuple a valid signature is a proof of a false statement, which the soundness of the Chaum–Pedersen proof bounds by about $q_H/p$ for $q_H$ hash queries.

Notes

• Compared with the CDH-based EDL scheme (Prime-order CDH ⇒ EDL signatures) — GJ03, signing is about 33% faster and signatures are about 75% shorter — KW03.
• GJKW07 is the joint journal version of KW03 and GJ03.