Cryptology ePrint Archive: Report 2020/945

On the (in)security of ROS

Fabrice Benhamouda and Tancrède Lepoint and 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 large enough dimensions $\ell$. The algorithm implies polynomial-time attacks against blind signatures such as Schnorr and Okamoto--Schnorr blind signatures, threshold signatures such as the one from GJKR (when concurrent executions are allowed), and multisignatures such as CoSI and the two-round version of MuSig.

Category / Keywords: cryptographic protocols / ROS, Blind Schnorr, Cryptanalysis

Date: received 31 Jul 2020

Contact author: fabrice benhamouda at gmail com,tancrede@google com,marianar@google com,michele orru@ens fr

Available format(s): PDF | BibTeX Citation

Version: 20200731:202605 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]