DLOG ⇒ Blind Okamoto–Schnorr signatures

Fully-black-box reduction · random oracle model · PS00

Statement

In the random-oracle model, blind Okamoto–Schnorr signatures are one-more unforgeable if DLOG is hard in the prime-order group, for a number of signer interactions logarithmic in the security parameter, even when the interactions run in parallel: no efficient adversary outputs valid signatures on $\ell +1$ distinct messages after $\ell$ interactions with the signer — PS00.

Notes

• The concrete bound says nothing for 4 parallel interactions in elliptic-curve groups of order $2^{200}$; covering such attacks needs the hardness of the ROS problem — Sch01.
• A transformation of the scheme gives security against polynomially many sequential signer interactions — Poi98.
• With more than $\log p$ concurrent sessions, outside the theorem’s regime, solving ROS forges blind Okamoto–Schnorr signatures in polynomial time — BLLOR21.