Identification scheme

A protocol in which a prover holding a secret key convinces a verifier holding the matching public key of its identity, canonically as a three-message commit-challenge-response sigma protocol such as Schnorr’s proof of knowledge of a discrete logarithm.

TODO: syntax and security definition.

Variations

Schnorr identification protocol

For $h=g^x$ 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$, and replies $z=r+ex\mathrm{mod}p$; the verifier accepts iff $g^z=a{h}^e$. The protocol is special sound and perfectly honest-verifier zero-knowledge — Sch91.

Participates in

Builds on Identification scheme

• Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir) (via Schnorr identification protocol)
• ID ⇒ DS
• ID ⇒ OWF

Produces Identification scheme

• DLOG ⇒ Schnorr identification protocol (via Schnorr identification protocol)