DLOG ⇒ Schnorr identification protocol

Fully-black-box reduction · standard model · Sch91 · security loss: DLOG success $\ge (\epsilon -1/|C|{)}^2$ for impersonation success $\epsilon$

Statement

The Schnorr identification protocol is a three-move sigma protocol for knowledge of $x={\log }_{g}h$ in a group of prime order $p$: the prover sends $a=g^r$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, receives a uniform challenge $e$ from the challenge space $C$, and replies $z=r+ex\mathrm{mod}p$; the verifier accepts iff $g^z=a{h}^e$. It is special sound and perfectly honest-verifier zero-knowledge unconditionally, and secure against impersonation under passive attack if DLOG is hard — Sch91.

Sketch

Rewinding an impersonator to two accepting transcripts $(a,e,z)$, $(a,e^{\prime },z^{\prime })$ with $e\ne e^{\prime }$ yields $x=(z-z^{\prime })/(e-e^{\prime })\mathrm{mod}p$; eavesdropped transcripts are simulated by sampling $z,e$ uniformly and setting $a=g^z{h}^{-e}$, which reproduces the honest distribution exactly.

Notes

• By the Reset Lemma, a passive impersonator with success probability $\epsilon$ yields a DLOG solver with success probability at least $(\epsilon -1/|C|{)}^2$ — BP02.
• Security against active and concurrent impersonation holds under the one-more discrete logarithm assumption — BP02.