On the (in)security of ROS

Abstract:

Schnorr's (blind) signatures, proposed more than 30 years ago, have been the foundation for dozens of cryptographic protocols of today, such as multisignatures, threshold signatures, zero-knowledge protocols, e-cash, and electronic voting systems. Most of these protocols, when concurrent executions are allowed, hinge on a cryptographic assumption called ROS, whose hardness was already debated by Schnorr himself (Schnorr'01).

In this talk, 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. Our algorithm leads to practical attacks against a number of constructions proposed in the literature.

Joint work with Fabrice Benhamouda, Tancrède Lepoint, Julian Loss, and Mariana Raykova.

Suggested reading: https://ia.cr/2020/945.