No algebraic reduction from OMDL to two-round MuSig

Conditional · assuming one-more Discrete Logarithm · DEF+19

Statement

If OMDL is hard, no algebraic reduction proves two-round MuSig secure under DLOG or under OMDL. The same holds for the two-round Schnorr multi-signatures of Bagherzandi–Cheon–Jarecki and of Ma–Weng–Li–Deng, and for CoSi — DEF+19. DEF+19 also exhibit flaws in the published security proofs of these schemes, CoSi never having been proved secure, and give practical sub-exponential attacks on all of them — DEF+19.

Notes

• An algebraic reduction from DLOG composes with the reduction of OMDL ⇒ Prime-order DLOG into an algebraic reduction from OMDL, so the DLOG case follows from the OMDL case — folklore.
• The two-round scheme mBCJ of DEF+19 is secure under DLOG in the random-oracle model — DEF+19. The three-round MuSig is secure under DLOG (DLOG ⇒ MuSig) — MPSW19, and the two-round MuSig2 under OMDL (OMDL ⇒ MuSig2) — NRS21.
• With more than $\log p$ concurrent sessions, solving the ROS problem forges two-round MuSig and CoSi signatures in polynomial time — BLLOR21.