Paper 2020/945 Original: eprint.iacr.org/2020/945 ↗
On the (in)security of ROS
Abstract
We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem in polynomial time for l > log p dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension l with best complexity known so far. When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto--Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe-Okamoto, and conditional blind signatures such as ZGP17.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2024-02-01: last updated
- 2020-07-31: published
- Short URL
- https://ia.cr/2020/945
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2020/945,
author = {Fabrice Benhamouda and Tancrède Lepoint and Julian Loss and Michele Orrù and Mariana Raykova},
title = {On the (in)security of ROS},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/945},
year = {2020},
url = {https://eprint.iacr.org/2020/945}
}