International Association
for Cryptologic Research

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.