---
OA_place: repository
OA_type: green
_id: '19712'
abstract:
- lang: eng
  text: "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.\r\nAdditionally, 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."
acknowledgement: We thank Pierre Briaud and Morten Øygarden for helpful discussions
  on algebraic attacks on RSD, and the EC reviewers for helpful comments.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Miguel
  full_name: Cueto Noval, Miguel
  id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
  last_name: Cueto Noval
  orcid: 0000-0002-2505-4246
- first_name: Simon-Philipp
  full_name: Merz, Simon-Philipp
  last_name: Merz
- first_name: Patrick
  full_name: Stählin, Patrick
  last_name: Stählin
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
citation:
  ama: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. On the soundness of algebraic
    attacks against code-based assumptions. In: <i>44th Annual International Conference
    on the Theory and Applications of Cryptographic Techniques</i>. Vol 15606. Springer
    Nature; 2025:385-415. doi:<a href="https://doi.org/10.1007/978-3-031-91095-1_14">10.1007/978-3-031-91095-1_14</a>'
  apa: 'Cueto Noval, M., Merz, S.-P., Stählin, P., &#38; Ünal, A. (2025). On the soundness
    of algebraic attacks against code-based assumptions. In <i>44th Annual International
    Conference on the Theory and Applications of Cryptographic Techniques</i> (Vol.
    15606, pp. 385–415). Madrid, Spain: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-91095-1_14">https://doi.org/10.1007/978-3-031-91095-1_14</a>'
  chicago: Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal.
    “On the Soundness of Algebraic Attacks against Code-Based Assumptions.” In <i>44th
    Annual International Conference on the Theory and Applications of Cryptographic
    Techniques</i>, 15606:385–415. Springer Nature, 2025. <a href="https://doi.org/10.1007/978-3-031-91095-1_14">https://doi.org/10.1007/978-3-031-91095-1_14</a>.
  ieee: M. Cueto Noval, S.-P. Merz, P. Stählin, and A. Ünal, “On the soundness of algebraic
    attacks against code-based assumptions,” in <i>44th Annual International Conference
    on the Theory and Applications of Cryptographic Techniques</i>, Madrid, Spain,
    2025, vol. 15606, pp. 385–415.
  ista: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. 2025. On the soundness of algebraic
    attacks against code-based assumptions. 44th Annual International Conference on
    the Theory and Applications of Cryptographic Techniques. EUROCRYPT: International
    Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol.
    15606, 385–415.'
  mla: Cueto Noval, Miguel, et al. “On the Soundness of Algebraic Attacks against
    Code-Based Assumptions.” <i>44th Annual International Conference on the Theory
    and Applications of Cryptographic Techniques</i>, vol. 15606, Springer Nature,
    2025, pp. 385–415, doi:<a href="https://doi.org/10.1007/978-3-031-91095-1_14">10.1007/978-3-031-91095-1_14</a>.
  short: M. Cueto Noval, S.-P. Merz, P. Stählin, A. Ünal, in:, 44th Annual International
    Conference on the Theory and Applications of Cryptographic Techniques, Springer
    Nature, 2025, pp. 385–415.
conference:
  end_date: 2025-05-08
  location: Madrid, Spain
  name: 'EUROCRYPT: International Conference on the Theory and Applications of Cryptographic
    Techniques'
  start_date: 2025-05-04
corr_author: '1'
date_created: 2025-05-19T14:15:01Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2025-05-28T06:12:39Z
day: '28'
department:
- _id: KrPi
doi: 10.1007/978-3-031-91095-1_14
intvolume: '     15606'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.research-collection.ethz.ch/handle/20.500.11850/732894
month: '04'
oa: 1
oa_version: Submitted Version
page: 385-415
publication: 44th Annual International Conference on the Theory and Applications of
  Cryptographic Techniques
publication_identifier:
  eisbn:
  - '9783031910951'
  eissn:
  - 1611-3349
  isbn:
  - '9783031910944'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the soundness of algebraic attacks against code-based assumptions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15606
year: '2025'
...