The Tangent Space Attack

• URL: http://arxiv.org/abs/2505.10184v1
• Date: Thu, 15 May 2025 11:30:46 GMT
• Title: The Tangent Space Attack
• Authors: Axel Lemoine,
• Abstract summary: We propose a new method for retrieving the structure of a generic alternant code given an arbitrary generator matrix.<n>We then discuss how this challenges the security of the McEliece cryptosystem instantiated with this family of codes.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a new method for retrieving the algebraic structure of a generic alternant code given an arbitrary generator matrix, provided certain conditions are met. We then discuss how this challenges the security of the McEliece cryptosystem instantiated with this family of codes. The central object of our work is the quadratic hull related to a linear code, defined as the intersection of all quadrics passing through the columns of a given generator or parity-check matrix, where the columns are considered as points in the affine or projective space. The geometric properties of this object reveal important information about the internal algebraic structure of the code. This is particularly evident in the case of generalized Reed-Solomon codes, whose quadratic hull is deeply linked to a well-known algebraic variety called the rational normal curve. By utilizing the concept of Weil restriction of affine varieties, we demonstrate that the quadratic hull of a generic dual alternant code inherits many interesting features from the rational normal curve, on account of the fact that alternant codes are subfield-subcodes of generalized Reed-Solomon codes. If the rate of the generic alternant code is sufficiently high, this allows us to construct a polynomial-time algorithm for retrieving the underlying generalized Reed-Solomon code from which the alternant code is defined, which leads to an efficient key-recovery attack against the McEliece cryptosystem when instantiated with this class of codes. Finally, we discuss the generalization of this approach to Algebraic-Geometry codes and Goppa codes.

Related papers

• Bases of Riemann-Roch spaces associated with arbitrary elliptic curve divisors and their application in constructing various elliptic Codes families [0.0]
  We establish the feasibility and provide exact algorithms for constructing bases of Riemann--Roch spaces corresponding to arbitrary divisors on elliptic curves.<n>We derive bases for quasi-cyclic elliptic codes and their subfield subcodes as well as for the class of Goppa-like elliptic codes.
  arXiv  Detail & Related papers  (2025-08-06T11:34:05Z)
• CodeRAG: Supportive Code Retrieval on Bigraph for Real-World Code Generation [69.684886175768]
  Large language models (LLMs) have shown promising performance in automated code generation.<n>In this paper, we propose CodeRAG, a retrieval-augmented code generation framework.<n> Experiments show that CodeRAG achieves significant improvements compared to no RAG scenarios.
  arXiv  Detail & Related papers  (2025-04-14T09:51:23Z)
• Classical and quantum Coxeter codes: Extending the Reed-Muller family [59.90381090395222]
  We introduce a class of binary linear codes that generalizes the Reed-Muller family by replacing the group $mathbbZm$ with an arbitrary finite Coxeter group.<n>We also construct quantum CSS codes arising from the Coxeter codes, which admit logical operators outside of the Clifford group.
  arXiv  Detail & Related papers  (2025-02-20T17:16:28Z)
• Puncturing Quantum Stabilizer Codes [28.796017729194713]
  We generalize the puncturing procedure to allow more freedom in the choice of which coded states are kept and which are removed.<n>We present several ways to utilize this for the search of codes with good or even optimal parameters.
  arXiv  Detail & Related papers  (2024-10-23T10:31:34Z)
• Geometric structure and transversal logic of quantum Reed-Muller codes [51.11215560140181]
  In this paper, we aim to characterize the gates of quantum Reed-Muller (RM) codes by exploiting the well-studied properties of their classical counterparts. A set of stabilizer generators for a RM code can be described via $X$ and $Z$ operators acting on subcubes of particular dimensions.
  arXiv  Detail & Related papers  (2024-10-10T04:07:24Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Comments as Natural Logic Pivots: Improve Code Generation via Comment Perspective [85.48043537327258]
  We propose MANGO (comMents As Natural loGic pivOts), including a comment contrastive training strategy and a corresponding logical comment decoding strategy. Results indicate that MANGO significantly improves the code pass rate based on the strong baselines. The robustness of the logical comment decoding strategy is notably higher than the Chain-of-thoughts prompting.
  arXiv  Detail & Related papers  (2024-04-11T08:30:46Z)
• Maximally Extendable Sheaf Codes [5.439020425819001]
  We study sheaf codes, a type of linear codes with a fixed hierarchical collection of local codes. We introduce a new property of a sheaf code, called maximalibility, which ensures that within class of codes on the same coded space, we encounter as few obstructions as possible.
  arXiv  Detail & Related papers  (2024-03-06T12:20:49Z)
• Linear Codes for Hyperdimensional Computing [9.7902367664742]
  We show that random linear codes offer a rich subcode structure that can be used to form key-value stores. We show that under the framework we develop, random linear codes admit simple recovery algorithms to factor (either bundled or bound) compositional representations.
  arXiv  Detail & Related papers  (2024-03-05T19:18:44Z)
• On the matrix code of quadratic relationships for a Goppa code [0.0]
  We build upon the algebraical modeling introduced in citeCMT23 to derive a structural attack on Goppa codes. Our method can break in just a few seconds some recent challenges about key-recovery attacks on the McEliece cryptosystem.
  arXiv  Detail & Related papers  (2023-10-31T14:35:07Z)
• Quantum spherical codes [55.33545082776197]
  We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions.
  arXiv  Detail & Related papers  (2023-02-22T19:00:11Z)
• KO codes: Inventing Nonlinear Encoding and Decoding for Reliable Wireless Communication via Deep-learning [76.5589486928387]
  Landmark codes underpin reliable physical layer communication, e.g., Reed-Muller, BCH, Convolution, Turbo, LDPC and Polar codes. In this paper, we construct KO codes, a computationaly efficient family of deep-learning driven (encoder, decoder) pairs. KO codes beat state-of-the-art Reed-Muller and Polar codes, under the low-complexity successive cancellation decoding.
  arXiv  Detail & Related papers  (2021-08-29T21:08:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.