DLOG ⇒ Okamoto identification protocol

Fully-black-box reduction · standard model · Oka92 · security loss: impersonation advantage $\epsilon$ yields DLOG advantage at least $(1-1/p)(\epsilon -1/|C|{)}^2$

Statement

The Okamoto identification protocol works with independent generators $g_1,g_2$ of a group of prime order $p$ and public key $X=g_1^{x_1}{g}_2^{x_2}$. The prover sends $A=g_1^{r_1}{g}_2^{r_2}$, receives $e\stackrel{\$}{\leftarrow }C$ from a challenge space $C\subseteq {\mathbb{Z}}_p$ with $1/|C|$ negligible, and replies $z_j=r_j+e{x}_j\mathrm{mod}p$; the verifier accepts iff $g_1^{z_1}{g}_2^{z_2}=A{X}^e$. The protocol is secure against impersonation under active attack if DLOG is hard in the group — Oka92.

Sketch

Given $g_2=g_1^w$, the reduction picks its own key $(x_1,x_2)$ and answers the active phase as the honest prover. It rewinds the impersonation phase to two accepting transcripts with a common $A$, which give a representation $(x_1^{\prime },x_2^{\prime })$ of $X$. The protocol is perfectly witness-indistinguishable, so $(x_1^{\prime },x_2^{\prime })\ne (x_1,x_2)$ with probability $1-1/p$, and then $w=(x_1-x_1^{\prime })/(x_2^{\prime }-x_2)\mathrm{mod}p$ — standard.

Notes

• An impersonator with advantage $\epsilon$ yields the two transcripts with probability at least $(\epsilon -1/|C|{)}^2$ by the Reset Lemma of BP02, so the reduction solves DLOG with probability at least $(1-1/p)(\epsilon -1/|C|{)}^2$ — standard.
• Unlike the Schnorr protocol, whose active and concurrent security is proved under OMDL (OMDL ⇒ Schnorr identification under concurrent attack) — BP02, active security of the Okamoto protocol needs only DLOG, because the reduction holds a valid secret key and answers prover sessions honestly — Oka92.
• The blind version of its Fiat–Shamir transform is one-more unforgeable under DLOG for logarithmically many signer sessions (DLOG ⇒ Blind Okamoto–Schnorr signatures) — PS00.