On the insecurity of ROS (Delivered in English)
- LecturerDr. Michele Orrù (Centre national de la recherche scientifique (CNRS)in Paris, France)
Host: Bo-Yin Yang - Time2025-03-07 (Fri.) 14:00 ~ 16:00
- LocationAuditorium 101 at IIS new Building
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).
The ROS assumption (Random inhomogeneities in an Overdetermined Solvable system of linear equations) is a simple cryptographic assumption that talks about the hardness of a hash function whose image is in a finite field.
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 ℓ > log p dimensions. Our algorithm leads to practical attacks against a number of constructions proposed in the literature.
The ROS assumption (Random inhomogeneities in an Overdetermined Solvable system of linear equations) is a simple cryptographic assumption that talks about the hardness of a hash function whose image is in a finite field.
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 ℓ > log p dimensions. Our algorithm leads to practical attacks against a number of constructions proposed in the literature.