Welcome to the resource topic for 2025/306
Title:
Dimensional e$\mathsf{ROS}ion: Improving the \mathsf{ROS}$ Attack with Decomposition in Higher Bases
Authors: Antoine Joux, Julian Loss, Giacomo Santato
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.
ePrint: https://eprint.iacr.org/2025/306
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .