We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem in polynomial time for $\ell > \log p$ dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension $\ell$ with best complexity known so far. When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto–Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe–Okamoto, and conditional blind signatures such as ZGP17.
This is joint work with Fabrice Benhamouda, Tancrède Lepoint, Julian Loss, Mariana Raykova.
Michele is a postdoc at UC Berkeley under the supervision of Alessandro Chiesa.
Prior to that, he was a PhD student at École Normale Supérieure, under the supervision of Georg Fuchsbauer. He is interested in the intersection between authentication and anonymity.
In the past, he contributed to Python, Debian, and Tor.