Paper 2025/306 Original: eprint.iacr.org/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_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.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2025-02-20: last updated
- 2025-02-20: published
- Short URL
- https://ia.cr/2025/306
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/306,
author = {Antoine Joux and Julian Loss and Giacomo Santato},
title = {Dimensional e$\mathsf{ROS}$ion: Improving the $\mathsf{ROS}$ Attack with Decomposition in Higher Bases},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/306},
year = {2025},
url = {https://eprint.iacr.org/2025/306}
}