OMDL ⇒ Schnorr identification under concurrent attack

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

Statement

The Schnorr identification protocol is secure against impersonation under active and concurrent attack if OMDL is hard for the prime-order group generator. In such an attack the adversary first runs arbitrarily many interleaved sessions, acting as the verifier, with honest provers holding $x={\log }_{g}X$, and then tries to make an honest verifier accept. For every efficient impersonator with advantage $\epsilon$ there is an efficient OMDL adversary with advantage at least $(\epsilon -1/|C|{)}^2$, where $C$ is the challenge space — BP02.

Sketch

The reduction takes $X$ and the session commitments $R_1,\dots ,R_n$ from the OMDL challenges, and answers each session challenge $e_i$ with $z_i={\log }_g(R_i{X}^{e_i})$ from the DL oracle. It then rewinds the impersonation phase to get two accepting transcripts with a common commitment (Reset Lemma), which give $x={\log }_{g}X$, and outputs ${\log }_g{R}_i=z_i-e_{i}x$ for every $i$: $n+1$ logarithms from $n$ oracle queries.

Notes

• Under plain DLOG, the protocol is secure against passive impersonation (DLOG ⇒ Schnorr identification protocol) — Sch91.
• No Turing reduction proves the protocol secure under concurrent attack from an assumption with an a priori bounded number of rounds unless that assumption is false (barrier) — Pas11.
• The Okamoto identification protocol is secure against active impersonation under plain DLOG (DLOG ⇒ Okamoto identification protocol) — Oka92.