Proximity Gaps for Gabidulin Codes and Applications
Researchers prove proximity-gap bounds for rank-metric and Gabidulin codes, enabling the first polynomial commitment scheme framework based on rank-metric error-correcting codes.
The paper proves every linear rank-metric code admits a proximity gap for deltas up to (d-1)/(3n) with error at most q^(e+1)/q^m, and improves the gap to (d-1)/(2n) for Gabidulin codes with error at most 10q^(n-1)/q^m, matching bounds for Reed-Solomon codes. A constructed infinite family of constant-rate Gabidulin codes shows the (d-1)/(2n) bound is tight, and a counterexample establishes a lower bound on the error at the d/(3n) gap. Applications include an IOPP for interleaved Gabidulin codes adapted from the Ligero IOPP and a q-linearized polynomial commitment scheme adapted from Ligero-based PCS, reportedly the first PCS framework based on rank-metric codes.
- Proximity gap (d-1)/(2n) for Gabidulin codes matches Reed-Solomon bounds.
- Constructs an infinite family proving the (d-1)/(2n) bound is tight.
- Adapts Ligero to build an IOPP for interleaved Gabidulin codes.
- Introduces the first polynomial commitment framework based on rank-metric codes.
- Products
- Ligero
From the original article
1 min read at arxiv.orgProximity 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 $δ$-proximity gap with error $ε$ if, for every $u_0,u_1\in\mathbb F^n$, either all points on $\ell_{u_0,u_1}=\{u_0+αu_1:α\in\mathbb F\}$ are $δ$-close to $C$, or at most an $ε$ fraction are.
By Songsong Li · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.