Prime-order CDH ⇒ EDL signatures

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

Statement

In the EDL signature scheme the public key is $y=g^x$ in a group of prime order $p$. To sign $m$, the signer picks a random salt $r$, sets $h=H(m,r)\in \mathbb{G}$ and $z=h^x$, and attaches a Fiat–Shamir Chaum–Pedersen proof that ${\log }_{g}y={\log }_{h}z$. The scheme is EUF-CMA secure in the random-oracle model if CDH is hard in prime-order groups, with a tight reduction that needs no forking — GJ03.

Sketch

On input $(g^a,g^b)$ the reduction sets $y=g^a$. It answers each fresh query $H(m,r)$ with $(g^b{)}^t$ for a fresh $t\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, except at the salts it picks to sign, where it answers $g^t$, so that $z=y^t$ and the proof can be simulated. By soundness of the proof, a forgery has $z^{\ast }=H(m^{\ast },r^{\ast }{)}^a=g^{ab{t}^{\ast }}$, which gives $g^{ab}=(z^{\ast }{)}^{1/t^{\ast }}$; random salts make it unlikely that a signing salt collides with the forger’s earlier queries.

Notes

• The scheme had been proposed at least twice before without a security analysis; GJ03 give the first one, with the tight reduction — GJ03.
• The DDH-based Katz–Wang scheme signs faster and has shorter signatures, with a tight reduction to DDH (Prime-order DDH ⇒ Katz–Wang signatures) — KW03.