Dimensional eROSion: Improving the ROS Attack with Decomposition in Higher Bases

Summary

e revisit the polynomial attack to the ROS problem modulo p from [6]. Our new algorithm achieves a polynomial time solution in dimension ℓ ≳ 0.725 · log2 p, extending the range of dimensions for which a polynomial attack is known beyond the previous bound of ℓ > log2 p. We also combine our new algorithm with Wagner’s attack to improve the general 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.