Title: 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.
