OMDL + ROS ⇒ Blind Schnorr signatures

Algebraic group model + random oracle model · FPS20

Statement

In the algebraic group model, with the hash modeled as a random oracle, blind Schnorr signatures are one-more unforgeable against $\ell$ concurrent signing sessions if OMDL is hard in the group and the $\ell$-ROS problem over ${\mathbb{Z}}_p$ is hard; so if OMDL and ROS ($\ell$-ROS for every polynomial $\ell$) are hard, the scheme is one-more unforgeable against polynomially many concurrent sessions — FPS20. The earlier argument of Sch01 is informal and in the generic group model with a random oracle — FPS20.

Notes

• ROS is not hard: $\ell$-ROS is solvable in polynomial time for $\ell >\log p$, and blind Schnorr signatures are then forgeable with $\ell$ concurrent sessions; combined with the generalized-birthday algorithm of Wag02, the same attack gives sub-exponential algorithms for smaller $\ell$ — BLLOR21. The theorem therefore has content only for $\ell \le \log p$ sessions.
• The clause variant of blind Schnorr signatures changes only the signing protocol and leaves signatures unchanged; its security proof rests on a problem related to ROS that appears much harder — FPS20.
• With blind Okamoto–Schnorr signatures, one-more unforgeability for logarithmically many sessions holds under plain DLOG in the random-oracle model (DLOG ⇒ Blind Okamoto–Schnorr signatures) — PS00.