Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


On the (in)security of ROS

September 7, 2022


Michele Orrù - UC Berkeley



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 BenhamoudaTancrède LepointJulian Loss, and Mariana Raykova.

Suggested reading:

Presented at

Crypto Reading Club talk on 2022-Sep-07

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created August 29, 2022, Updated March 22, 2023