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 a challenge space $C\subseteq {\mathbb{Z}}_p$ with $1/|C|$ negligible, 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 in the group — 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 (OMDL ⇒ Schnorr identification under concurrent attack) — BP02.
• If DLOG is 2-moment hard, meaning that every algorithm’s success probability is bounded in terms of the second moment of its running time, as in the generic group model, then every $t$-time passive impersonator succeeds with probability at most $(t^2/p{)}^{2/3}$, against $(t^2/p{)}^{1/2}$ from earlier proofs — RS21.