International Association for Cryptologic Research

International Association
for Cryptologic Research


On the (in)security of ROS

Fabrice Benhamouda , Algorand Foundation
Tancrède Lepoint , Google
Julian Loss , University of Maryland College Park USA
Michele Orrù , UC Berkeley
Mariana Raykova , Google
DOI: 10.1007/978-3-030-77870-5_2 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Award: Best Paper Award
Abstract: We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem mod p in polynomial time for $l > log p$ dimensions. Our algorithm can be combined with Wagner's attack, and leads to a sub-exponential solution for any dimension $l$ 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. Schemes for e-cash and anonymous credentials (such as Anonymous Credentials Light) inspired from the above are also affected.
  title={On the (in)security of ROS},
  author={Fabrice Benhamouda and Tancrède Lepoint and Julian Loss and Michele Orrù and Mariana Raykova},