International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Antoine Joux , CISPA Helmholtz Center for Information Security
Julian Loss , CISPA Helmholtz Center for Information Security
Giacomo Santato , CISPA Helmholtz Center for Information Security, Saarland University
Download:
Search ePrint
Search Google
Conference: TCC 2025
Abstract: We revisit the polynomial attack to the $\mathsf{{ROS}}$ problem modulo $p$ from \cite{JC:BLLOR22}. Our new algorithm achieves a polynomial time solution in dimension $\ell \gtrsim 0.726 \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 a range of 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.
BibTeX
@inproceedings{tcc-2025-36196,
  title={Dimensional e$\mathsf{{ROS}}$ion: Improving the $\mathsf{{ROS}}$ Attack with Decomposition in Higher Bases},
  publisher={Springer-Verlag},
  author={Antoine Joux and Julian Loss and Giacomo Santato},
  year=2025
}