This is a potential security issue, you are being redirected to https://csrc.nist.gov.
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.
Security and Privacy: cryptography