Paper 2020/945

On the (in)security of ROS

Fabrice Benhamouda, Tancrède Lepoint, Julian Loss, Michele Orrù, and Mariana Raykova

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. Schemes for e-cash (such as Brands' signature) and anonymous credentials (such as Anonymous Credentials Light) inspired from the above are also affected.

Note: New examples and very specific scenarios where it's possible to attack some anonymous credential schemes.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
digital signaturescryptanalysis
Contact author(s)
fabrice benhamouda @ gmail com
crypto @ tancre de
marianar @ google com
michele orru @ ens fr
lossjulian @ gmail com
History
2022-02-23: last of 3 revisions
2020-07-31: received
See all versions
Short URL
https://ia.cr/2020/945
License
Creative Commons Attribution
CC BY

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},
      note = {\url{https://eprint.iacr.org/2020/945}},
      url = {https://eprint.iacr.org/2020/945}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.