Paper 2026/992

Suppressing Hidden Extension-Field Linearity in Rank-Metric Cryptography via Structural Incompatibility

Abstract

A prominent line of rank-metric code-based cryptography has long relied on highly structured algebraic code families, such as Gabidulin codes, for their optimal rank-distance properties and efficient decoding. However, this structure exposes algebraic invariants, most notably extension-field linearity and Frobenius invariance, that enable powerful polynomial-time distinguishers and effective key-recovery attacks. In this work, we revisit this structural tension from a new perspective. Rather than relying solely on masking, we identify a simple yet fundamental structural incompatibility that rules out the direct extension-field linear representation on which these attacks rely. Building on this insight, we introduce Enhanced Gabidulin Matrix Subcodes (EnGMS), a family of masked matrix codes obtained from K'-dimensional Fq-subcodes of expanded Gabidulin codes. When m does not divide K', where m is the extension degree, this dimension mismatch is not merely a randomization heuristic. It deterministically rules out hidden Fq^m-linear expansion structure, a key algebraic prerequisite for the relevant attacks in [5, 43]. Using a generic transform, EnGMS-based constructions yield IND-CCA2-secure public-key encryption schemes and key encapsulation mechanisms, while retaining deterministic decoding and zero decryption failure. At standard security levels, our schemes achieve very compact ciphertexts with moderate public-key sizes, demonstrating that provable structural guarantees can coexist with competitive size efficiency.

Note: An earlier version of this work was submitted to CRYPTO 2026, with the final submitted version uploaded on February 9, 2026, before the submission deadline.