Dimensional e$\mathsf{ROS}$ion: Improving the $\mathsf{ROS}$ Attack with Decomposition in Higher Bases

Antoine Joux; Julian Loss; Giacomo Santato

Paper 2025/306

Dimensional e$\mathsf{ROS}$ion: Improving the $\mathsf{ROS}$ Attack with Decomposition in Higher Bases

Antoine Joux

, Helmholtz Center for Information Security

Julian Loss

, Helmholtz Center for Information Security

Giacomo Santato

, Helmholtz Center for Information Security, Saarland University

Abstract

We revisit the polynomial attack to the $\mathsf{ROS}$ problem modulo $p$ from [BLLOR22]. Our new algorithm achieves a polynomial time solution in dimension $\ell \gtrsim 0.725 \cdot \log_2 p$, extending the range of dimensions for which a polynomial attack is known beyond the previous bound of $\ell > \log_2p$. We also combine our new algorithm with Wagner's attack to improve the general $\mathsf{ROS}$ attack complexity for some of the dimensions where a polynomial solution is still not known. We implement our polynomial attack and break the one-more unforgeability of blind Schnorr signatures over 256-bit elliptic curves in a few seconds with 192 concurrent sessions.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: ROS problem ROS attack Schnorr signatures
Contact author(s): joux @ cispa de
loss @ cispa de
giacomo santato @ cispa de
History: 2025-02-21: approved; 2025-02-20: received; See all versions
Short URL: https://ia.cr/2025/306
License: CC BY

BibTeX

@misc{cryptoeprint:2025/306,
      author = {Antoine Joux and Julian Loss and Giacomo Santato},
      title = {Dimensional e$\mathsf{{ROS}}$ion: Improving the $\mathsf{{ROS}}$ Attack with Decomposition in Higher Bases},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/306},
      year = {2025},
      url = {https://eprint.iacr.org/2025/306}
}