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\subseteq {\mathbb{F}}^n$ has a $\delta$-proximity gap with error $\epsilon$ if, for every $u_0,u_1\in {\mathbb{F}}^n$, either all points on ${\ell }_{u_0,u_1}=\{u_0+\alpha u_1:\alpha \in \mathbb{F}\}$ are $\delta$-close to $C$, or at most an $\epsilon$ 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 ${\mathbb{F}}_{q^m}$ admits a proximity gap for every $\delta \le (d-1)/(3n)$, with error at most $q^{e+1}/q^m$, where $e=\lfloor \delta n\rfloor$. 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 ${\ell }_{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 $\epsilon$. 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.

40 pages