pith. sign in

arxiv: 2604.09292 · v1 · submitted 2026-04-10 · 💻 cs.CR · cs.IT· math.IT

Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS

\'Etienne Burle , Aleksei Udovenko This is my paper

Pith reviewed 2026-05-10 17:15 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT
keywords restricted syndrome decodingCROSS signaturepost-quantum cryptographyregular syndrome decodingclosest vector problemcode-based attackslattice attackscryptanalysis
0
0 comments X

The pith

Restricted syndrome decoding solutions correspond to low-norm structured vectors in new codes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that Restricted Syndrome Decoding, the problem at the core of the CROSS post-quantum signature scheme, can be solved by locating vectors with specific structure and small norm inside specially built codes. These codes are constructed so that valid restricted-error patterns appear directly as such vectors, both when measuring distance in the Hamming metric and in the Euclidean metric. The construction yields reductions of ResSD to Regular Syndrome Decoding on one side and to Closest Vector Problem plus lists of short or close vectors on the other. A reader would care because the reductions enlarge the set of known tools that could be used against schemes relying on ResSD and give concrete ways to relate its hardness to two mature families of problems.

Core claim

Solutions to Restricted Syndrome Decoding can be deduced from vectors of a particular structure and a small norm in newly constructed codes, in both Hamming and Euclidean metrics. This allows us to reduce Restricted Syndrome Decoding to both code-based problems such as Regular Syndrome Decoding and lattice-based problems such as the Closest Vector Problem and the List of Short/Close Vectors, increasing the attack surface and providing new insights into the security of ResSD. The authors evaluate the resulting attacks both theoretically and experimentally on reduced-parameter instances of CROSS.

What carries the argument

Newly constructed codes in which restricted-error solutions appear exactly as low-norm vectors of a designated structure.

If this is right

  • ResSD instances become directly attackable by existing Regular Syndrome Decoding algorithms.
  • Euclidean-metric reductions open the use of lattice-reduction and CVP solvers against the same problem.
  • Security analysis of CROSS must now consider hardness assumptions from both code-based and lattice-based settings.
  • Experimental attacks on reduced CROSS parameters can be scaled to estimate concrete security levels.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Hybrid attacks that alternate between the Hamming and Euclidean views might outperform single-paradigm methods.
  • The same code-construction technique could be tried on other restricted decoding variants appearing in post-quantum proposals.
  • Full-size CROSS parameter sets could be tested with the new reductions to check whether the theoretical links translate into practical breaks.

Load-bearing premise

The new codes must map low-norm structured vectors to valid restricted errors and vice versa without adding or hiding hardness.

What would settle it

A concrete low-norm structured vector in one of the constructed codes whose corresponding error pattern fails to produce the expected syndrome, or a valid ResSD solution that does not appear as such a vector.

read the original abstract

Restricted Syndrome Decoding (ResSD) is a variant of linear code decoding problem where each of the error's entries must belong to a fixed small set of values. This problem underlies the security of CROSS, a post-quantum signature scheme that is one of the Round 2 candidates of NIST's ongoing additional signatures call. We show that solutions to this problem can be deduced from vectors of a particular structure and a small norm in newly constructed codes, in both Hamming and Euclidean metrics. This allows us to reduce Restricted Syndrome Decoding to both code-based (Regular Syndrome Decoding) and lattice-based problems (Closest Vector Problem, List of Short/Close Vectors), increasing the attack surface and providing new insights into the security of ResSD. We evaluate our attacks on CROSS instances both theoretically and experimentally on reduced parameters.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents new models for Restricted Syndrome Decoding (ResSD) by constructing codes in which ResSD solutions correspond to structured vectors of small norm in both Hamming and Euclidean metrics. This enables reductions of ResSD to Regular Syndrome Decoding and to lattice problems such as the Closest Vector Problem and List of Short/Close Vectors. The work applies these reductions to analyze the security of the CROSS signature scheme, providing both theoretical insights and experimental results on reduced-parameter instances.

Significance. If the proposed code constructions and reductions hold, this paper makes a valuable contribution by expanding the cryptanalytic toolkit for ResSD-based schemes like CROSS. By linking code-based and lattice-based problems, it increases the attack surface and may help in better understanding the hardness assumptions underlying post-quantum signatures. The experimental evaluation on reduced parameters provides initial evidence, though scaling to full security levels would strengthen the impact.

major comments (2)
  1. [Section 3 (Code Constructions)] The preservation of the restricted error structure in the newly constructed codes is central to the reduction (as noted in the abstract and the weakest assumption). However, the mapping from low-norm vectors back to valid ResSD solutions needs a formal proof that no extraneous solutions are introduced; without this, the equivalence of the problems is not fully established.
  2. [Section 5 (Experimental Results)] The experiments use reduced parameters. It is unclear from the description how the observed attack efficiencies translate to the full parameter sets used in CROSS, and no concrete complexity estimates or success rates for the full instances are provided.
minor comments (2)
  1. [Abstract] The abstract mentions 'newly constructed codes' but does not specify if they are linear or the dimension/rate; adding a brief characterization would improve clarity.
  2. [Throughout] Notation for the metrics (Hamming vs Euclidean) should be consistently defined early on to avoid confusion in the reductions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and the opportunity to clarify and strengthen the manuscript. We address each major comment below and indicate the planned revisions.

read point-by-point responses

  1. Referee: [Section 3 (Code Constructions)] The preservation of the restricted error structure in the newly constructed codes is central to the reduction (as noted in the abstract and the weakest assumption). However, the mapping from low-norm vectors back to valid ResSD solutions needs a formal proof that no extraneous solutions are introduced; without this, the equivalence of the problems is not fully established.

    Authors: We agree that an explicit formal proof of the equivalence is required to confirm that the mapping introduces no extraneous solutions. In the revised manuscript we will augment Section 3 with a dedicated lemma and proof establishing that the constructed codes preserve the restricted error structure and that the correspondence between low-norm vectors and valid ResSD solutions is bijective in both the Hamming and Euclidean settings. The proof will explicitly show that every solution in the new code arises from a unique restricted error vector and vice versa. revision: yes

  2. Referee: [Section 5 (Experimental Results)] The experiments use reduced parameters. It is unclear from the description how the observed attack efficiencies translate to the full parameter sets used in CROSS, and no concrete complexity estimates or success rates for the full instances are provided.

    Authors: The reduced-parameter experiments were intended to demonstrate feasibility of the reductions. In the revision we will insert a new subsection that derives concrete complexity estimates for the full CROSS parameter sets by composing the observed efficiencies with the asymptotic costs of the Regular-SD and CVP oracles under the given reductions. We will also supply extrapolated success probabilities obtained by scaling the measured rates with the increase in dimension and weight. Full-scale experimental runs remain computationally infeasible at present, but the added analysis will make the security implications for the original parameters explicit. revision: partial

Circularity Check

0 steps flagged

No significant circularity; reductions are derived from explicit code constructions

full rationale

The paper presents reductions of Restricted Syndrome Decoding to Regular Syndrome Decoding and lattice problems (CVP, List of Short Vectors) by constructing new codes in which low-norm structured vectors correspond to valid ResSD solutions. This mapping is claimed to preserve the restricted error structure without introducing extra hardness. No equations or steps in the provided abstract or description reduce a claimed result to a fitted parameter, self-definition, or load-bearing self-citation. The central claim rests on the correctness of the code construction and the equivalence of the forward/reverse mappings, which are presented as independent derivations rather than tautological renamings or ansatzes imported from prior self-work. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that the newly constructed codes allow exact correspondence between ResSD solutions and structured low-norm vectors; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption The newly constructed codes preserve the restricted error structure for the reduction to hold.
    Necessary for the deduction of ResSD solutions from the vectors in the new codes.

pith-pipeline@v0.9.0 · 5434 in / 1325 out tokens · 56224 ms · 2026-05-10T17:15:19.722639+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

55 extracted references · 55 canonical work pages · 1 internal anchor

  1. [1]

    Aguilar-Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Persichetti, E., Z´ emor, G., Bos, J., Dion, A., Lacan, J., Robert, J.M., Veron, P.: HQC. Tech. rep., National Institute of Stan- dards and Technology (2022), available athttps://csrc.nist.gov/Projects/ post-quantum-cryptography/round-4-submissions

    work page 2022

  2. [2]

    Alagic, G., Bros, M., Ciadoux, P., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Silberg, H., Smith-Tone, D., Waller, N.a.: Status report on the first round of the additional digital signature schemes for the nist post-quantum cryptography standardization process. Tech...

    work page 2024

  3. [3]

    In: Ed Dawson, Serge Vaudenay (editors)

    Augot, D., Finiasz, M., Sendrier, N.: A family of fast syndrome based cryp- tographic hash functions. In: Ed Dawson, Serge Vaudenay (editors). Progress cryptology-Mycrypt First international conference on cryptology Malaysia, ISBN 978-3-540-28938-8. LNCS, vol. 3715, pp. 64–83. Springer, Kuala Lumpur, Malaysia (Sep 2005).https://doi.org/10.1007/11554868_6,...

    work page doi:10.1007/11554868_6 2005

  4. [4]

    Security Details

    Baldi, M., Barenghi, A., Battagliola, M., Bitzer, S., Gianvecchio, M., Karl, P., Man- ganiello, F., Pavoni, A., Pelosi, G., Pintore, F., Santini, P., Schupp, J., Signorini, E., Slaughter, F., Wachter-Zeh, A., Weger, V.: CROSS — Codes and Restricted Objects Signature Scheme. Security Details. Version 2.2 - July 31, 2025. Tech. rep. (2024)

    work page 2025

  5. [5]

    Baldi, M., Barenghi, A., Battagliola, M., Bitzer, S., Gianvecchio, M., Karl, P., Manganiello, F., Pavoni, A., Pelosi, G., Santini, P., Schupp, J., Signorini, E., Slaughter, F., Wachter-Zeh, A., Weger, V.: CROSS — Codes and Restricted Objects Signature Scheme. Tech. rep., National Institute of Standards and Technology (2024), available athttps://csrc.nist....

    work page 2024

  6. [6]

    Advances in Mathematics of Communications19(5), 1360– 1381 (2025).https://doi.org/10.3934/amc.2024058

    Baldi, M., Battaglioni, M., Chiaraluce, F., Horlemann, A.L., Persichetti, E., San- tini, P., Weger, V.: A new path to code-based signatures via identification schemes with restricted errors. Advances in Mathematics of Communications19(5), 1360– 1381 (2025).https://doi.org/10.3934/amc.2024058

    work page doi:10.3934/amc.2024058 2025

  7. [7]

    You are given a context below. Your task is to generate 15 diverse questions and answers based on this context:\n\n

    Baldi, M., Battaglioni, M., Chiaraluce, F., Horlemann-Trautmann, A.L., Per- sichetti, E., Santini, P., Weger, V.: A new path to code-based signatures via identi- fication schemes with restricted errors (2021).https://doi.org/10.48550/arXiv. 2008.06403

    work page internal anchor Pith review doi:10.48550/arxiv 2021

  8. [8]

    In: Tang, Q., Teague, V

    Baldi, M., Bitzer, S., Pavoni, A., Santini, P., Wachter-Zeh, A., Weger, V.: Zero knowledge protocols and signatures from the restricted syndrome decod- ing problem. In: Tang, Q., Teague, V. (eds.) PKC 2024, Part II. LNCS, vol. 14602, pp. 243–274. Springer, Cham (Apr 2024).https://doi.org/10.1007/ 978-3-031-57722-2_8

    work page 2024

  9. [9]

    In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 12th International Symposium, AAECC-12, Toulouse, France, June 23-27, 1997, Proceedings

    Barg, A.: Minimum distance decoding algorithms for linear codes. In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 12th International Symposium, AAECC-12, Toulouse, France, June 23-27, 1997, Proceedings. LNCS, vol. 1255, pp. 1–14. Springer (1997)

    work page 1997

  10. [10]

    5555/3666122.3667277

    Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neigh- bor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 30 27th SODA. pp. 10–24. ACM-SIAM (Jan 2016).https://doi.org/10.1137/1. 9781611974331.ch2

    work page doi:10.1137/1 2016

  11. [11]

    In: Advances in Cryptology - EUROCRYPT 2012

    Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in 2n/20: How 1+1 = 0 improves information set decoding. In: Advances in Cryptology - EUROCRYPT 2012. LNCS, Springer (2012)

    work page 2012

  12. [12]

    IEEE Trans

    Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory24(3), 384–386 (May 1978)

    work page 1978

  13. [13]

    In: Advances in Cryptology - CRYPTO 2011

    Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding. In: Advances in Cryptology - CRYPTO 2011. LNCS, vol. 6841, pp. 743– 760 (2011)

    work page 2011

  14. [14]

    CiC1(3), 33 (2024).https://doi.org/10.62056/a06cy7qiu

    Beullens, W., Briaud, P., Øygarden, M.: A security analysis of restricted syndrome decoding problems. CiC1(3), 33 (2024).https://doi.org/10.62056/a06cy7qiu

    work page doi:10.62056/a06cy7qiu 2024

  15. [15]

    In: IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, June 25-30, 2023

    Bitzer, S., Pavoni, A., Weger, V., Santini, P., Baldi, M., Wachter-Zeh, A.: Generic decoding of restricted errors. In: IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, June 25-30, 2023. pp. 246–

    work page 2023

  16. [16]

    IEEE (2023).https://doi.org/10.1109/ISIT54713.2023.10206983,https: //doi.org/10.1109/ISIT54713.2023.10206983

    work page doi:10.1109/isit54713.2023.10206983 2023

  17. [17]

    In: WCC Workshop on Coding and Cryptography (Sep 2017),http://wcc2017.suai.ru/Proceedings{_}WCC2017.zip

    Both, L., May, A.: Optimizing BJMM with Nearest Neighbors: Full Decoding in 22/21n and McEliece Security. In: WCC Workshop on Coding and Cryptography (Sep 2017),http://wcc2017.suai.ru/Proceedings{_}WCC2017.zip

    work page 2017

  18. [18]

    In: Lange, T., Steinwandt, R

    Both, L., May, A.: Decoding linear codes with high error rate and its impact for LPN security. In: Lange, T., Steinwandt, R. (eds.) Post-Quantum Cryptog- raphy 2018. LNCS, vol. 10786, pp. 25–46. Springer, Fort Lauderdale, FL, USA (Apr 2018).https://doi.org/10.1007/978-3-319-79063-3{_}2,https://doi. org/10.1007/978-3-319-79063-3{_}2

    work page doi:10.1007/978-3-319-79063-3 2018

  19. [19]

    In: Hazay, C., Stam, M

    Briaud, P., Øygarden, M.: A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 391–422. Springer, Cham (Apr 2023).https://doi.org/10.1007/978-3-031-30589-4_14

    work page doi:10.1007/978-3-031-30589-4_14 2023

  20. [20]

    In: Paterson, K.G., Stebila, D

    Bricout, R., Chailloux, A., Debris-Alazard, T., Lequesne, M.: Ternary syndrome decoding with large weight. In: Paterson, K.G., Stebila, D. (eds.) SAC 2019. LNCS, vol. 11959, pp. 437–466. Springer, Cham (Aug 2019).https://doi.org/10.1007/ 978-3-030-38471-5_18

    work page 2019

  21. [21]

    5281/zenodo.18230686,https://doi.org/10.5281/zenodo.18230686

    Burle, E., Udovenko, A.: Cross-paradigm models of restricted syndrome decoding with application to CROSS - supporting code (Jan 2026).https://doi.org/10. 5281/zenodo.18230686,https://doi.org/10.5281/zenodo.18230686

    work page doi:10.5281/zenodo.18230686 2026

  22. [22]

    In: Hazay, C., Stam, M

    Carozza, E., Couteau, G., Joux, A.: Short signatures from regular syndrome de- coding in the head. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 532–563. Springer, Cham (Apr 2023).https://doi.org/ 10.1007/978-3-031-30589-4_19

    work page doi:10.1007/978-3-031-30589-4_19 2023

  23. [23]

    In: Proc

    Debris-Alazard, T., Tillich, J.P.: Statistical decoding. In: Proc. IEEE Int. Sympo- sium Inf. Theory - ISIT 2017. pp. 1798–1802. Aachen, Germany (Jun 2017)

    work page 2017

  24. [24]

    In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V

    Ducas, L., Laarhoven, T., van Woerden, W.P.J.: The randomized slicer for CVPP: Sharper, faster, smaller, batchier. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part II. LNCS, vol. 12111, pp. 3–36. Springer, Cham (May 2020).https://doi.org/10.1007/978-3-030-45388-6_1

    work page doi:10.1007/978-3-030-45388-6_1 2020

  25. [25]

    In: Proc

    Dumer, I.: On minimum distance decoding of linear codes. In: Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory. pp. 50–52. Moscow (1991)

    work page 1991

  26. [26]

    In: Reyzin, L., Stebila, D

    Esser, A., Santini, P.: Not just regular decoding: Asymptotics and improve- ments of regular syndrome decoding attacks. In: Reyzin, L., Stebila, D. (eds.) 31 CRYPTO 2024, Part VI. LNCS, vol. 14925, pp. 183–217. Springer, Cham (Aug 2024).https://doi.org/10.1007/978-3-031-68391-6_6

    work page doi:10.1007/978-3-031-68391-6_6 2024

  27. [27]

    Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis,

    Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation44(170), 463–471 (1985),http://www.jstor.org/stable/2007966

    work page arXiv 1985

  28. [28]

    In: Matsui, M

    Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosys- tems. In: Matsui, M. (ed.) Advances in Cryptology - ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer (2009)

    work page 2009

  29. [29]

    Predicting lattice reduction,

    Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EU- ROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Berlin, Heidelberg (Apr 2008).https://doi.org/10.1007/978-3-540-78967-3_3

    work page doi:10.1007/978-3-540-78967-3_3 2008

  30. [30]

    In: Gilbert, H

    Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme prun- ing. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–

    work page 2010

  31. [31]

    Springer, Berlin, Heidelberg (May / Jun 2010).https://doi.org/10.1007/ 978-3-642-13190-5_13

    work page 2010

  32. [32]

    In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C

    Hanrot, G., Pujol, X., Stehl´ e, D.: Algorithms for the shortest and closest lattice vector problems. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) Coding and Cryptology. pp. 159–190. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

    work page 2011

  33. [33]

    In: Peyrin, T., Galbraith, S

    Hazay, C., Orsini, E., Scholl, P., Soria-Vazquez, E.: Concretely efficient large-scale MPC with active security (or, TinyKeys for TinyOT). In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 86–117. Springer, Cham (Dec 2018).https://doi.org/10.1007/978-3-030-03332-3_4

    work page doi:10.1007/978-3-030-03332-3_4 2018

  34. [34]

    Cryptology ePrint Archive, Report 2024/1495 (2024),https://eprint.iacr.org/2024/1495

    Horlemann, A.L., Khathuria, K., Newman, M., Sakzad, A., Cabello, C.V.: Lattice- based vulnerabilities in lee metric post-quantum cryptosystems. Cryptology ePrint Archive, Report 2024/1495 (2024),https://eprint.iacr.org/2024/1495

    work page 2024

  35. [35]

    H¨ ulsing, A., Bernstein, D.J., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S.L., Kampanakis, P., K¨ olbl, S., Lange, T., Lauridsen, M.M., Mendel, F., Nieder- hagen, R., Rechberger, C., Rijneveld, J., Schwabe, P., Aumasson, J.P., West- erbaan, B., Beullens, W.: SPHINCS +. Tech. rep., National Institute of Stan- dards and Technology (2022), availab...

    work page 2022

  36. [36]

    In: Honary, B

    Jabri, A.A.: A statistical decoding algorithm for general linear block codes. In: Honary, B. (ed.) Cryptography and coding. Proceedings of the 8 th IMA Interna- tional Conference. LNCS, vol. 2260, pp. 1–8. Springer, Cirencester, UK (Dec 2001)

    work page 2001

  37. [37]

    In: 15th ACM STOC

    Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: 15th ACM STOC. pp. 193–206. ACM Press (Apr 1983).https: //doi.org/10.1145/800061.808749

    work page doi:10.1145/800061.808749 1983

  38. [38]

    IACR Cryptol

    Kim, J., Lee, C.: Reduce and prange: Revisiting prange’s information set decoding for LPN and RSD. IACR Cryptol. ePrint Arch. p. 276 (2024),https://eprint. iacr.org/2024/276

    work page 2024

  39. [39]

    Lenstra, A., Lenstra, H., Lov´ asz, L.: Factoring polynomials with rational coeffi- cients. Math. ann261(4), 515–534 (1982)

    work page 1982

  40. [40]

    In: Joye, M., Leander, G

    Liu, H., Wang, X., Yang, K., Yu, Y.: The hardness of LPN over any integer ring and field for PCG applications. In: Joye, M., Leander, G. (eds.) EUROCRYPT 2024, Part VI. LNCS, vol. 14656, pp. 149–179. Springer, Cham (May 2024).https: //doi.org/10.1007/978-3-031-58751-1_6

    work page doi:10.1007/978-3-031-58751-1_6 2024

  41. [41]

    Lyubashevsky, V., Ducas, L., Kiltz, E., Lepoint, T., Schwabe, P., Seiler, G., Stehl´ e, D., Bai, S.: CRYSTALS-DILITHIUM. Tech. rep., National Institute of Stan- dards and Technology (2022), available athttps://csrc.nist.gov/Projects/ post-quantum-cryptography/selected-algorithms-2022 32

    work page 2022

  42. [42]

    In: Oswald, E., Fischlin, M

    May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer (2015)

    work page 2015

  43. [43]

    McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114–

    work page

  44. [44]

    Jet Propulsion Lab (1978), dSN Progress Report 44

    work page 1978

  45. [45]

    IRE Transactions on Information Theory8(5), 5–9 (1962).https://doi.org/10.1109/TIT.1962

    Prange, E.: The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory8(5), 5–9 (1962).https://doi.org/10.1109/TIT.1962. 1057777,http://dx.doi.org/10.1109/TIT.1962.1057777

    work page doi:10.1109/tit.1962 1962

  46. [46]

    Prest, T., Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: FALCON. Tech. rep., National Institute of Standards and Technology (2022), available athttps://csrc.nist. gov/Projects/post-quantum-cryptography/selected-algorithms-2022

    work page 2022

  47. [47]

    In: Srinathan, K., Rangan, C.P., Yung, M

    Saarinen, M.J.O.: Linearization attacks against syndrome based hashes. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) Progress in Cryptology - IN- DOCRYPT 2007. LNCS, vol. 4859, pp. 1–9. Springer (2007)

    work page 2007

  48. [48]

    Sage Developers, T.: SageMath, the Sage Mathematics Software System (Version 10.6) (2025),https://www.sagemath.org

    work page 2025

  49. [49]

    Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems,

    Schnorr, C.P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming66(1), 181–199 (Aug 1994).https://doi.org/10.1007/BF01581144,https://doi.org/10.1007/ BF01581144

    work page doi:10.1007/bf01581144 1994

  50. [50]

    In: Alt, H., Habib, M

    Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. pp. 145–156. Springer Berlin Heidelberg, Berlin, Heidelberg (2003)

    work page 2003

  51. [51]

    Schwabe, P., Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Seiler, G., Stehl´ e, D., Ding, J.: CRYSTALS-KYBER. Tech. rep., National Institute of Standards and Technology (2022), available athttps://csrc. nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

    work page 2022

  52. [52]

    In: Goldwasser, S

    Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factor- ing. In: Goldwasser, S. (ed.) FOCS. pp. 124–134 (1994)

    work page 1994

  53. [53]

    In: Cohen, G.D., Wolf- mann, J

    Stern, J.: A method for finding codewords of small weight. In: Cohen, G.D., Wolf- mann, J. (eds.) Coding Theory and Applications. LNCS, vol. 388, pp. 106–113. Springer (1988)

    work page 1988

  54. [54]

    development team, T.F.: fpylll, a Python wrapper for the fplll lattice reduction library, Version: 0.6.4 (2025),https://github.com/fplll/fpylll, available at https://github.com/fplll/fpylll

    work page 2025

  55. [55]

    IACR Cryptol

    Wang, T., Wang, A., Yang, K., Liu, H., Yu, Y., Zhang, J., Wang, X.: A hybrid algorithm for the regular syndrome decoding problem. IACR Cryptol. ePrint Arch. p. 1284 (2025),https://eprint.iacr.org/2025/1284 A Lattice enumeration methods In the following, we summarize a standard heuristic framework for solvingList- SVPandList-CVP, based on enumeration of la...

    work page 2025