Proximity Gaps for Gabidulin Codes and Applications
Abstract
Proximity gaps are central to the soundness of interactive oracle proofs of proximity (IOPPs) and polynomial commitment schemes (PCSs). An [n,k,d] linear code C⊆𝔽n has a δ-proximity gap with error ε if, for every u0,u1∈𝔽n, either all points on ℓu0,u1={u0+αu1:α∈𝔽} are δ-close to C, or at most an ε fraction are. Although proximity gaps for Hamming-metric codes are well understood, their rank-metric counterparts remain largely unexplored despite their applications in coding theory and cryptography. In this work, we study proximity gaps for linear rank-metric codes and their cryptographic applications. First, we show that every [n,k,d] linear rank-metric code C over 𝔽qm admits a proximity gap for every δ≤(d−1)/(3n), with error at most qe+1/qm, where e=⌊δn⌋. For Gabidulin codes, we improve the gap to $(d-1)/(2n)$ with error 10qn−1/qm. These two proximity gaps match those for general linear Hamming-metric codes and Reed--Solomon (RS) codes, respectively. We prove the $(d-1)/(2n)$ bound is tight by constructing an infinite family of constant-rate Gabidulin codes and affine lines ℓu0,u1 on which a 1−o(1) fraction of points are d/(2n)-close to the code, while u1 is at least 3d/(4n)-far from it. At the d/(3n) gap, we also give a counterexample establishing a lower bound on ε. As applications, we construct an IOPP for interleaved Gabidulin codes by adapting the Ligero IOPP for interleaved RS codes. We then adapt the Ligero-based PCS for ordinary polynomials to obtain a q-linearized polynomial commitment scheme. To our knowledge, this is the first PCS framework based on rank-metric error-correcting codes.
Related
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
- Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
- On Proximity Gaps for One-Point Algebraic Geometric Codes
- Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
- Constant-time decoding of Gabidulin codes and their generalizations with application to RQC
BibTeX
@misc{li2026proximity,
title = {{Proximity Gaps for Gabidulin Codes and Applications}},
author = {Songsong Li and Chaoping Xing and Chen Yuan and Ruiqi Zhu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09838},
eprint = {2609.09838},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09838},
}
RIS
TY - UNPB
TI - Proximity Gaps for Gabidulin Codes and Applications
AU - Songsong Li
AU - Chaoping Xing
AU - Chen Yuan
AU - Ruiqi Zhu
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09838
UR - https://arxiv.org/abs/2609.09838
AB - Proximity gaps are central to the soundness of interactive oracle proofs of proximity (IOPPs) and polynomial commitment schemes (PCSs). An [n,k,d] linear code C⊆𝔽^n has a δ-proximity gap with error ε if, for every u_0,u_1∈𝔽^n, either all points on ℓ_u_0,u_1={u_0+αu_1:α∈𝔽} are δ-close to C, or at most an ε fraction are. Although proximity gaps for Hamming-metric codes are well understood, their rank-metric counterparts remain largely unexplored despite their applications in coding theory and cryptography. In this work, we study proximity gaps for linear rank-metric codes and their cryptographic applications. First, we show that every [n,k,d] linear rank-metric code C over 𝔽_q^m admits a proximity gap for every δ≤(d−1)/(3n), with error at most q^e+1/q^m, where e=⌊δn⌋. For Gabidulin codes, we improve the gap to $(d-1)/(2n)$ with error 10q^n−1/q^m. These two proximity gaps match those for general linear Hamming-metric codes and Reed--Solomon (RS) codes, respectively. We prove the $(d-1)/(2n)$ bound is tight by constructing an infinite family of constant-rate Gabidulin codes and affine lines ℓ_u_0,u_1 on which a 1−o(1) fraction of points are d/(2n)-close to the code, while u_1 is at least 3d/(4n)-far from it. At the d/(3n) gap, we also give a counterexample establishing a lower bound on ε. As applications, we construct an IOPP for interleaved Gabidulin codes by adapting the Ligero IOPP for interleaved RS codes. We then adapt the Ligero-based PCS for ordinary polynomials to obtain a q-linearized polynomial commitment scheme. To our knowledge, this is the first PCS framework based on rank-metric error-correcting codes.
ER -