International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 31 July 2020

Fabrice Benhamouda, Tancrède Lepoint, Michele Orrù, Mariana Raykova
ePrint Report ePrint Report
We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem in polynomial time for large enough dimensions $\ell$. The algorithm implies polynomial-time attacks against blind signatures such as Schnorr and Okamoto--Schnorr blind signatures, threshold signatures such as the one from GJKR (when concurrent executions are allowed), and multisignatures such as CoSI and the two-round version of MuSig.

Additional news items may be found on the IACR news page.