An Attack on High Rate McEliece Cryptosystems Using Generalized Reed Solomon Codes with Weight $2$ Mask

• URL: http://arxiv.org/abs/2607.25027v1
• Date: Mon, 27 Jul 2026 19:39:04 GMT
• Title: An Attack on High Rate McEliece Cryptosystems Using Generalized Reed Solomon Codes with Weight $2$ Mask
• Abstract summary: We provide distinguishers for the public codes appearing in McEliece cryptosystems.<n>We give a framework to turn a good enough distinguisher into a key-recovery attack.
• Score: 1.529342790344802
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code. There have been successful attacks on some of those schemes with row and column weight between $1$ and $1 + R$, where $R$ is the rate of the code. The case of weight two and larger has been left open in these works. Subsequently, several authors proposed schemes with weight exactly two and with even higher weight. We provide distinguishers for the public codes appearing in these cryptosystems in the high rate regime. In addition, we give a framework to turn a good enough distinguisher into a key-recovery attack. In the case where the matrix $M$ has row and column weight $2$, we can successfully attack the scheme in the high rate regime using a cube code distinguisher.

Related papers

• Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes [0.0]
  Enhanced Gabidulin Matrix Codes (EGMC) were introduced by Aragon, Couvreur, Dyseryn, Gaborit, and Vincotte at Asia 2024.<n>Their security relies on the assumption that a masked EGMC code is hard to distinguish from a random matrix code.<n>We show that this construction leaves enough structure for an equivalent code of the secret key to be recovered.
  arXiv  Detail & Related papers  (2026-08-04T08:38:48Z)
• Breaking the bicycle frame: Coset-based quantum LDPC codes [65.96089068176079]
  Generalizing the construction of two-block group algebra (2BGA) codes, we introduce a family of two-block quantum LDPC codes.<n>We identify several new quantum LDPC codes, including weight-6 codes with parameters $[48,8,6]]$, $[96,8,10]]$, and $[224,12,16]]$.<n>Our codes, when decoded using BP-OSD, perform competitively with BB codes, achieving thresholds of $approx0.65%$ for the weight-6 family and $approx0.35%$ for the weight-8 family.
  arXiv  Detail & Related papers  (2026-06-15T20:20:57Z)
• Quantum Private Distributed Matrix Multiplication With Degree Tables [46.17112353277822]
  We show how quantum resources can be used to increase the rate of private distributed matrix multiplication.<n>In the high-privacy regime, the state-of-the-art classical code is called the gap additive secure (GASP) code.<n>We develop a new family of codes that can work in the quantum setting.
  arXiv  Detail & Related papers  (2025-11-28T18:02:11Z)
• Bilinear Compressive Security [4.3725047448751235]
  We study a rather idealized known attack for recovering $Q$ from repeated observations of $y$'s for different, known $x_k$.<n>Our main result for BCS states that under a weak symmetry condition on the filter $h$, recovering $Q$ will require extensive sampling from transmissions of $Omegaleft(maxleft(n,(n/s)2right)$ messages $x_k$ if they are $s$-sparse.
  arXiv  Detail & Related papers  (2025-10-17T07:32:25Z)
• MIRANDA: short signatures from a leakage-free full-domain-hash scheme [10.228787876075266]
  We present $mathsfMiranda$, the first family of full-domain-hash signatures based on matrix codes.<n>Our trapdoor is very simple and generic: if we propose it with matrix codes, it can actually be instantiated in many other ways.
  arXiv  Detail & Related papers  (2025-10-08T19:24:24Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound [44.154181086513574]
  We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ frackn = frac13 $. We demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs.
  arXiv  Detail & Related papers  (2024-10-05T11:56:15Z)
• Lattice-Based Vulnerabilities in Lee Metric Post-Quantum Cryptosystems [3.277820036565198]
  Post-quantum cryptography has gained attention due to the need for secure cryptographic systems in the face of quantum computing. We consider a generic Lee metric based McEliece type cryptosystem and evaluate its security against lattice-based attacks.
  arXiv  Detail & Related papers  (2024-09-24T12:21:33Z)
• MinRank Gabidulin encryption scheme on matrix codes [6.471199354529622]
  We propose a generalization of the McEliece scheme and the Niederreiter frame to matrix codes and the MinRank problem. Our new approach permits to achieve better trade-off between ciphertexts and public key than the classical McEliece scheme.
  arXiv  Detail & Related papers  (2024-05-26T12:04:01Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Morphing quantum codes [77.34726150561087]
  We morph the 15-qubit Reed-Muller code to obtain the smallest known stabilizer code with a fault-tolerant logical $T$ gate. We construct a family of hybrid color-toric codes by morphing the color code.
  arXiv  Detail & Related papers  (2021-12-02T17:43:00Z)

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.