Metraipolis › archive › dc_c442969e03ea

Proximity Gaps for Gabidulin Codes and Applications — arXiv:2609.09838

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.09838
License (as archived)
CC0-1.0
Archived
2026-10-16T07:54:49.804Z
SHA-256 of the archived text
ed4d42b2d310fa2f7713fd2ad31b91fc360690825cf39569ba27ac9a3d0425ea
Stable URL of this page
https://metraipolis.com/documento/dc_c442969e03ea

How to cite

Proximity Gaps for Gabidulin Codes and Applications — arXiv:2609.09838 — arXiv (en), https://arxiv.org/abs/2609.09838 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c442969e03ea (Metraipolis archive dc_c442969e03ea, sha256 ed4d42b2d310fa2f7713fd2ad31b91fc360690825cf39569ba27ac9a3d0425ea)
BibTeX
@misc{dcc442969e03ea,
  title = {Proximity Gaps for Gabidulin Codes and Applications — arXiv:2609.09838},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09838},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c442969e03ea; sha256 ed4d42b2d310fa2f7713fd2ad31b91fc360690825cf39569ba27ac9a3d0425ea},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09838. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-10 in cs.CR).
Categorie arXiv: Information Theory (cs.IT) ; Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.09838 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T07:37:41.598Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).