On the insecurity of ROS (以英文演講)
- 講者Michele Orrù 博士 (Centre national de la recherche scientifique (CNRS)in Paris, France)
邀請人：楊柏因 - 時間2025-03-07 (Fri.) 14:00 ~ 16:00
- 地點新館101會議室
摘要
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.