Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

• URL: http://arxiv.org/abs/2608.03328v1
• Date: Tue, 04 Aug 2026 08:38:48 GMT
• Title: Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Enhanced Gabidulin Matrix Codes (EGMC), introduced by Aragon, Couvreur, Dyseryn, Gaborit, and Vincotte at Asiacrypt 2024, were designed to hide the algebraic structure of Gabidulin matrix codes while enabling very compact McEliece- and Niederreiter-type encryption schemes, with ciphertexts as small as $65$ bytes at the claimed 128-bit security level. Their security relies on the assumption that a masked EGMC code is hard to distinguish from a random matrix code. We show that this enhanced construction leaves enough structure for an equivalent code of the secret key to be recovered. Unlike previous cryptanalysis, our attack combines combinatorial and algebraic techniques to recover a Gabidulin-equivalent compressed code. This code can then be extended to a full-length equivalent secret key in polynomial time. As a result, the attack provides both a distinguisher and a key-recovery attack against the EGMC encryption schemes. The attack breaks all 16 proposed EGMC parameter sets by large margins. For example, for the claimed 128-bit parameter set $(2,17,37,4,0)$, it reduces the security level from 186 bits to 35 bits. In our implementation, the equivalent secret key is recovered in less than 10 minutes.

Related papers

• High Memory Masked Convolutional Codes for PQC [0.0]
  This paper presents a novel post-quantum cryptosystem based on high-memory masked convolutional codes.<n>It supports arbitrary plaintext lengths with linear-time decryption and uniform per-bit computational cost.<n>The scheme achieves cryptanalytic margins exceeding those of the classic McEliece system by factors greater than 2100.
  arXiv  Detail & Related papers  (2025-10-17T10:39:20Z)
• Compile-Time Fully Homomorphic Encryption of Vectors: Eliminating Online Encryption via Algebraic Basis Synthesis [1.3824176915623292]
  ciphertexts are constructed from precomputed encrypted basis vectors combined with a runtime-scaled encryption of zero.<n>We formalize the method as a randomized $mathbbZ_t$- module morphism and prove that it satisfies IND-CPA security under standard assumptions.<n>Unlike prior designs that require a pool of random encryptions of zero, our construction achieves equivalent security using a single zero ciphertext multiplied by a fresh scalar at runtime.
  arXiv  Detail & Related papers  (2025-05-19T00:05:18Z)
• 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)
• Anamorphic Cryptography using Baby-Step Giant-Step Recovery [0.46040036610482665]
  This paper outlines the implementation of Anamorphic Cryptography using ECC (Elliptic Curve Cryptography)<n>It outlines how the secret message sent to Alice is hidden within the random nonce value, which is used within the encryption process.<n>It also shows that the BSGS (Baby-step Giant-step) variant significantly outperforms unoptimised elliptic curve methods.
  arXiv  Detail & Related papers  (2025-04-21T12:53:32Z)
• CipherGuard: Compiler-aided Mitigation against Ciphertext Side-channel Attacks [26.849878609957386]
  CipherGuard is a compiler-based mitigation tool to counteract ciphertext side channels with high efficiency and security guarantees.<n>In its most efficient strategy, CipherGuard incurs an average performance overhead of only 1.41X, with a maximum of 1.95X.
  arXiv  Detail & Related papers  (2025-02-19T03:22:36Z)
• Cryptanalysis on Lightweight Verifiable Homomorphic Encryption [8.478323897416617]
  Verifiable Homomorphic Encryption (VHE) is a cryptographic technique that integrates Homomorphic Encryption (HE) with Verifiable Computation (VC)<n>It serves as a crucial technology for ensuring both privacy and integrity in outsourced computation.<n>This paper presents efficient attacks that exploit the homomorphic properties of encryption schemes.
  arXiv  Detail & Related papers  (2025-02-18T08:13:10Z)
• 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)
• CodeChameleon: Personalized Encryption Framework for Jailbreaking Large Language Models [49.60006012946767]
  We propose CodeChameleon, a novel jailbreak framework based on personalized encryption tactics. We conduct extensive experiments on 7 Large Language Models, achieving state-of-the-art average Attack Success Rate (ASR) Remarkably, our method achieves an 86.6% ASR on GPT-4-1106.
  arXiv  Detail & Related papers  (2024-02-26T16:35:59Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• 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)
• Recovering AES Keys with a Deep Cold Boot Attack [91.22679787578438]
  Cold boot attacks inspect the corrupted random access memory soon after the power has been shut down. In this work, we combine a novel cryptographic variant of a deep error correcting code technique with a modified SAT solver scheme to apply the attack on AES keys. Our results show that our methods outperform the state of the art attack methods by a very large margin.
  arXiv  Detail & Related papers  (2021-06-09T07:57:01Z)

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.