Paper 2025/306

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

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 }_{2}p$. We also combine our new algorithm with Wagner's attack to improve the general $$ 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.