On the Soundness of Algebraic Attacks Against Code-Based Assumptions
OPEN ACCESS
Loading...
Author / Producer
Date
2025
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study recent algebraic attacks (Briaud-Øygarden EC’23) on the Regular Syndrome Decoding (RSD) problem and the assumptions underlying the correctness of their attacks’ complexity estimates. By relating these assumptions to interesting algebraic-combinatorial problems, we prove that they do not hold in full generality. However, we show that they are (asymptotically) true for most parameter sets, supporting the soundness of algebraic attacks on RSD. Further, we prove—without any heuristics or assumptions—that RSD can be broken in polynomial time whenever the number of error blocks times the square of the size of error blocks is larger than 2 times the square of the dimension of the code.
Additionally, we use our methodology to attack a variant of the Learning With Errors problem where each error term lies in a fixed set of constant size. We prove that this problem can be broken in polynomial time, given a sufficient number of samples. This result improves on the seminal work by Arora and Ge (ICALP’11), as the attack’s time complexity is independent of the LWE modulus.
Permanent link
Publication status
published
External links
Book title
Advances in Cryptology – EUROCRYPT 2025
Journal / series
Volume
15606
Pages / Article No.
385 - 415
Publisher
Springer
Event
44th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2025)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Cryptography
Organisational unit
09653 - Paterson, Kenneth / Paterson, Kenneth