---
res:
  bibo_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.\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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Miguel
      foaf_name: Cueto Noval, Miguel
      foaf_surname: Cueto Noval
      foaf_workInfoHomepage: http://www.librecat.org/personId=ffc563a3-f6e0-11ea-865d-e3cce03d17cc
    orcid: 0000-0002-2505-4246
  - foaf_Person:
      foaf_givenName: Simon-Philipp
      foaf_name: Merz, Simon-Philipp
      foaf_surname: Merz
  - foaf_Person:
      foaf_givenName: Patrick
      foaf_name: Stählin, Patrick
      foaf_surname: Stählin
  - foaf_Person:
      foaf_givenName: Akin
      foaf_name: Ünal, Akin
      foaf_surname: Ünal
      foaf_workInfoHomepage: http://www.librecat.org/personId=f6b56fb6-dc63-11ee-9dbf-f6780863a85a
    orcid: 0000-0002-8929-0221
  bibo_doi: 10.1007/978-3-031-91095-1_14
  bibo_volume: 15606
  dct_date: 2025^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0302-9743
  - http://id.crossref.org/issn/1611-3349
  - http://id.crossref.org/issn/9783031910944
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: On the soundness of algebraic attacks against code-based assumptions@
...