No fully-black-box reduction from bounded-round assumptions to Schnorr identification under concurrent attack
Statement
If a Turing reduction, which uses the adversary only as an oracle, proves the Schnorr identification protocol sequentially witness hiding from an intractability assumption whose possibly unbounded challenger interacts with the adversary in an a priori fixed polynomial number of rounds (bounded-round assumptions), then the assumption is false — Pas11. The theorem rules out such reductions for every constant-round, sequentially witness-hiding, special-sound protocol for a unique-witness relation, and the Schnorr protocol is one. Security against impersonation under concurrent attack implies sequential witness hiding, since an adversary that computes the witness after sequential sessions can then run the honest prover — standard; so such reductions to it are ruled out too.
Notes
- Under OMDL, which is not a bounded-round assumption, the protocol is secure under concurrent attack (OMDL ⇒ Schnorr identification under concurrent attack) — BP02.
- Security against passive impersonation holds under DLOG, a 2-round assumption (DLOG ⇒ Schnorr identification protocol) — Sch91.