Ilmu Komputer & AI editorial
Open AccessOA2026
Proximity Gaps for Gabidulin Codes and Applications
Rank-metric proximity gaps, tight bounds, and the first rank-metric polynomial commitment scheme
Songsong Li; Chaoping Xing; Chen Yuan; Ruiqi Zhuยท 2026ยท DOI 10.48550/arXiv.2609.09838
The core problem
Proximity gaps are a fundamental property underpinning the soundness of interactive oracle proofs of proximity (IOPPs) and polynomial commitment schemes (PCSs). For a linear code
, a -proximity gap with error means that for any affine line
, either all points on the line are -close to , or at most an fraction are. While proximity gaps for Hamming-metric codes are well understood, their rank-metric counterparts remain largely unexplored. This paper addresses this gap by studying proximity gaps for linear rank-metric codes and their cryptographic applications. The authors consider codes over the extension field
equipped with the rank metric, where the distance between two vectors is the rank of their difference as a matrix over
. The main contributions include: (1) a general proximity gap for any linear rank-metric code with and error where
; (2) an improved gap for Gabidulin codes up to with error ; (3) a tightness resu
Innovation
The paper presents several key results. First, for any linear rank-metric code over
, there exists a proximity gap for every with error at most , where
. Second, for Gabidulin codes, the gap is improved to with error . These bounds match those for general linear Hamming-metric codes and Reed-Solomon codes, respectively. Third, the bound is proven tight: there exists an infinite family of constant-rate Gabidulin codes and affine lines where a fraction of points are -close to the code, while is at least -far from it. Fourth, at , a counterexample establishes a lower bound on , showing that the error cannot be arbitrarily small. Finally, as applications, the authors construct an IOPP for interleaved Gabidulin codes by adapting the Ligero IOPP, and a -linearized polynomial commitment scheme by adapting the Ligero-based PCS. This is the first PCS framework based on rank-metric error-correcting codes. The results are significant for both coding theory and cryptography, providing
Proximity gaps are a fundamental property underpinning the soundness of interactive oracle proofs of proximity (IOPPs) and polynomial commitment schemes (PCSs). For a linear code
, a -proximity gap with error means that for any affine line
, either all points on the line are -close to , or at most an fraction are. While proximity gaps for Hamming-metric codes are well understood, their rank-metric counterparts remain largely unexplored. This paper addresses this gap by studying proximity gaps for linear rank-metric codes and their cryptographic applications. The authors consider codes over the extension field
equipped with the rank metric, where the distance between two vectors is the rank of their difference as a matrix over
. The main contributions include: (1) a general proximity gap for any linear rank-metric code with and error where
; (2) an improved gap for Gabidulin codes up to with error ; (3) a tightness result showing the bound is optimal; (4) a counterexample at establishing a lower bound on ; and (5) applications to IOPPs and PCSs, including the first PCS framework based on rank-metric error-correcting codes.
The authors employ a combination of algebraic and combinatorial techniques to analyze proximity gaps in rank-metric codes. For the general bound, they leverage the structure of linear rank-metric codes and properties of affine lines in the rank metric space. The proof for Gabidulin codes exploits their specific algebraic structure as -linearized polynomials. To establish tightness, they construct an infinite family of constant-rate Gabidulin codes and affine lines where a fraction of points are -close to the code, while is at least -far from it. This construction uses carefully chosen parameters and probabilistic arguments. The counterexample at is derived by analyzing the distribution of ranks of linear combinations of codewords and error vectors. For the applications, the authors adapt the Ligero IOPP for interleaved Reed-Solomon codes to the rank-metric setting, specifically for interleaved Gabidulin codes. They then modify the Ligero-based PCS for ordinary polynomials to obtain a -linearized polynomial commitment scheme. The security analysis of the PCS relies on the proximity gap results. The methodology is rigorous, combining theoretical proofs with explicit constructions and algorithmic adaptations.
Why it matters
The results demonstrate that rank-metric codes, particularly Gabidulin codes, exhibit proximity gaps comparable to their Hamming-metric counterparts. The tightness result highlights a fundamental limitation: the bound cannot be improved for Gabidulin codes. The counterexample at further underscores the delicate trade-off between the gap parameter and the error probability. The applications to IOPPs and PCSs are particularly noteworthy. The IOPP for interleaved Gabidulin codes extends the Ligero framework to the rank metric, enabling efficient proximity testing for these codes. The -linearized polynomial commitment scheme is the first of its kind, opening new avenues for cryptographic protocols based on rank-metric codes. These constructions could lead to more efficient and secure systems in scenarios where rank-metric codes offer advantages, such as in network coding and distributed storage. The authors also discuss potential improvements and open problems, such as closing the gap between the general bound and the Gabidulin-specific bound, and exploring other families of rank-metric codes. Overall, this work significantly advances the understanding of proximity gaps in the rank metric and provides practical cryptographic applications.
Who should read this
CS practitioners and researchers
Opening member contentโฆ