PaperlayerView exact revision on arXiv

Source-linked AI summary

Proximity Gaps for Gabidulin Codes and Applications

Songsong Li, Chaoping Xing, Chen Yuan, Ruiqi Zhu

arXiv:2609.09838v1cs.ITcs.CRmath.IT

TL;DR

The paper asks whether Hamming-metric proximity gaps extend to rank metric, where verifying rank statements in existing proof systems incurs significant overhead. It develops rank-metric proximity-gap results and adapts Ligero-style constructions; its passages include a Gabidulin example at the half-distance threshold and a lower bound on proximity error.

  • Problem

    The paper asks whether Hamming-metric proximity gaps extend to rank metric, where verifying rank statements in existing proof systems incurs significant overhead.

    Source: §1 · pp. 3–4

  • Method

    It develops a Gabidulin-specific reconstruction argument and adapts Ligero-style constructions for rank-metric codes and q-linearized polynomials.

    Source: §1 · p. 4, §1.2 · pp. 6, 10

  • Results

    At δ=d/(2n), all but O(Q^-1) line parameters yield Gabidulin-code-close points; at e=d/3, the error cannot generally improve to o(q^-e).

    Source: §1.2 · pp. 9–10

  • Takeaways & Limitations

    The results are applied to construct IOPPs for rank-metric codes and a Ligero-style commitment scheme for q-linearized polynomials.

    Source: §1 · p. 4, §1.2 · p. 10

    The extension-degree requirement may limit scalability, and arithmetic overhead suggests costs more suitable for small or moderate instances without further optimization.

    Source: §4.2 · p. 36

Abstract

from arXiv · show

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.

1 Introduction

The section studies proximity gaps for rank-metric codes and their applications to rank-metric IOPPs and a commitment scheme for q-linearized polynomials. It outlines constructions limiting proximity-gap soundness at d/(2n) and d/(3n), and describes a Gabidulin-based commitment scheme, including coefficient lifting and a correlated-rank-bound step.

1 Introduction

  • The authors target native rank-metric proofs because existing generic arithmetic-circuit reductions for rank statements incur significant overhead, while rank-metric proximity gaps were unstudied.They use these gaps to construct rank-metric IOPPs and corresponding polynomial commitment schemes.Source: §1 · p. 4

1.1 Our Contributions

  • (d-1)/(3n) proximity gaps hold for arbitrary linear rank-metric codes, with soundness error at most q^(e+1)/q^m for e = floor(δn).This extends the proximity-gap phenomenon to the rank metric.Source: §1.1 · p. 5
  • (d-1)/(2n) proximity gaps hold for Gabidulin codes, with error bounded by 10q^(n-1)/q^m.The proof uses rank-metric Berlekamp–Welch decoding.Source: §1.1 · p. 5
  • 1-o(1) of points on certain affine lines are d/(2n)-close to Gabidulin codes, although the interleaved vector remains d/(2n)-far.The counterexample uses an infinite family of [n, 2g + 1, 4g] codes with n = 6g.Source: §1.1 · p. 5
  • Θ(q^-e) of points can be e-close at e = d/3 even when u0 and the interleaved vector are both farther than e.Thus, the proximity error cannot generally be improved to o(q^-e).Source: §1.1 · pp. 5–6
  • Ligerorm-PCS is a transparent, extractable commitment scheme for q-linearized polynomials with prover and verifier times eO(λk).It follows the Ligero framework using interleaved Gabidulin codes; this targets complexity sublinear in the input size k rather than the potentially much larger ordinary degree.Source: §1.1 · p. 6

1.2 Technical Overview

  • The Gabidulin proof replaces the Reed–Solomon divisibility argument with a global rational-function-field system and coefficient-by-coefficient reconstruction, since symbolic composition prevents applying the Polishchuk–Spielman lemma.Many pointwise Berlekamp–Welch systems are unified into one system, and the reconstructed polynomial is shown to be linear in the line parameter.Source: §1.2 · pp. 6–8
  • Canceling a nonzero factor and comparing coefficients shows that P_s agrees with b_us on E for s=0,1, yielding the stated correlated rank bound.Source: §1.2 · p. 9
  • For n=6g Gabidulin codes with d=4g, (1−O(Q^-1)) of line points are d/(2n)-close, while u1 is at least 3d/4-far.The construction uses second-highest annihilator-polynomial coefficients that cover almost all λ; each such λ yields a point whose difference has rank d/2.Source: §1.2 · pp. 9–10
  • At e=d/3, a Θ(q^-e) fraction of line points are e-close while λ=0 remains e-far, so the proximity error cannot generally be o(q^-e).The construction uses codimension-one FQ-subspaces to produce the close points.Source: §1.2 · p. 10
  • For k=κ² with κ dividing m, the PCS lifts the q-linearized polynomial’s coefficient vector, reshapes it into a κ × κ matrix, and expresses it using a symbolic product.The decomposition adapts Ligero’s tensor-product approach to q-linearized polynomials.Source: §1.2 · p. 10
  • The scheme encodes matrix columns as Gabidulin codewords, commits to them with Merkle hashes, and checks queried rows for local consistency.Its soundness rests on the Gabidulin proximity test and Merkle-hash collision resistance.Source: §1.2 · pp. 10–11

2 Preliminaries

These preliminaries set up q-linearized polynomials and rank-metric codes, then define the decoding, proof, and commitment primitives used in the paper.

2.1 Linearized Polynomials

  • q-linearized polynomials are F_q-linear functions on F_qm, and their symbolic product is composition, which is associative but non-commutative.They also admit a long-division analogue using symbolic product.Source: §2.1 · pp. 11–12

2.2 Rank-Metric Codes and Gabidulin Codes

  • The preliminaries identify F_qm vectors with matrices over F_q to define rank distance and relative rank distance, with relative distance normalized by n.A vector is δ-close to a code when its relative rank distance is at most δ.Source: §2.2 · pp. 12–13
  • Gabidulin codes evaluate q-linearized polynomials on F_q-linearly independent points and have rank distance d = n − k + 1.They are the rank-metric analogue of Reed–Solomon codes.Source: §2.2 · p. 13

2.3 The Berlekamp–Welch Unique Decoding Algorithm for Gabidulin codes

  • The Berlekamp–Welch decoder reconstructs a polynomial through a linear system, then recovers P from N = Λ◦P and checks the rank-distance bound.The unique-decoding radius satisfies 2t < d.Source: §2.3 · pp. 13–14

2.4 Interactive Oracle Proofs

  • An IOPP lets the verifier query a witness oracle sparsely and requires rejection with high probability when the witness is far from any valid one.The definition here uses relative rank distance for that far condition.Source: §2.4 · p. 14

2.5 Polynomial Commitment Schemes

  • An extractable PCS for q-linearized polynomials comprises Gen, Commit, Open, and Eval algorithms, with Eval checking a claimed value β = f(α).The committed polynomial space consists of q-linearized polynomials of q-degree less than k.Source: §2.5 · p. 15

3 Rank-Metric Proximity Gaps

This section studies proximity gaps for linear rank-metric codes, including correlated-agreement results for Gabidulin codes and their relation to the unique-decoding radius under a line-probability condition. It also gives counterexamples and an asymptotic lower bound that delineate limits on the proximity threshold and soundness error.

3n-Proximity Gap for General Linear Rank-Metric Codes

  • For e ≤ floor((d−1)/3) and q^(e+1) < q^m, every line is either entirely e-close to C or has fewer than q^(e+1) e-close points.The proof bounds the number of close points in the non-all-close case by q^(e+1)−1.Source: §3 · pp. 16–17

Correlated agreement

  • The rank-metric proximity gap also implies the existence of a correlated-agreement set.Theorem 3.2 states the correlated-agreement result for parameters defined as in Lemma 3.1.Source: §3 · p. 17

2n-Proximity Gap for Gabidulin Codes

  • For Gabidulin codes, the gap reaches e < d/2: if the theorem’s line-probability condition holds, every point on the line is e-close to C.The proof uses the algebraic decoding algorithm and globalizes Berlekamp–Welch reconstruction systems across close points on the line.Source: §3 · p. 19

3 Rank-Metric Proximity Gaps

  • For Gabidulin codes, if more than 10q^(n−1) points on a line are e-close for e<d/2, then every point on the line is e-close.The proof establishes agreement on a common Fq-subspace of dimension n−e, which yields the conclusion for every line parameter.Source: §3 · pp. 22, 24, §3.3 · p. 24

3.3 Counterexamples at the Unique-Decoding Boundary

  • At e=d/2, an infinite family of constant-rate 1/3 Gabidulin codes has lines with 1−o(1) fraction of points d/2-close, while the direction is at least 3d/4-far.The construction includes codes of length 6g over Fq^(6g).Source: §3.3 · pp. 24, 27

3.4 A Lower Bound on the Proximity Error at δ = d 3n

  • At e=d/3, a line has a point farther than e yet at least (q^n−1)/(q^r−1) points are e-close, giving a proximity-error lower bound of order q^-e.The e-close parameters form H=(E* )^(Q−1), with Q=q^r.Source: §3.4 · p. 28
  • The argument establishes d([u0, u1], C2) > e, ruling out the correlated-agreement conclusion for this construction.It derives d(ℓ(0), C) > e by contradiction, and ℓ(0) = u0.Source: §3.4 · p. 29
  • The construction has good parameters of density Θ(q^-e), yet not all line points are e-close and its interleaved word is not e-close, so ε_e cannot be o(q^-e).Here e = r and m = n = (c + 1)r.Source: §3.4 · p. 29

4 Cryptographic applications of proximity gap

This section applies Gabidulin proximity gaps to cryptographic constructions: an interactive proximity test for interleaved codes and a Ligero-style commitment scheme for q-linearized polynomials. It also describes the scheme’s extraction and efficiency guarantees and its query and field-size limitations.

4.1 Proximity test for interleaved rank metric codes

  • If an interleaved matrix is farther than e from the code, its column span contains a vector farther than e from the underlying Gabidulin code.This holds for e ≤ floor((d − 1)/2) when q^m > q^(e+1), supporting the random-combination test.Source: §4.1 · p. 30
  • For any malicious prover, an oracle input at distance greater than e from Cs is rejected except with probability (1-e/n)^t + εe; the test reduces interleaved membership to underlying Gabidulin membership via a random Fqm-linear combination of columns.Source: §4.1 · pp. 29, 31

4.2 Ligero-style Rank Metric PCS

  • A tensor-product coefficient decomposition expresses q-linearized polynomial evaluations through a coefficient matrix, enabling the Ligero-style commitment construction.For k = κ^2 ≤ m, the decomposition gives f(α) = x_l ⊙ F · (α, α^q, …, α^(q^(κ−1)))^T.Source: §4.2 · pp. 31–32
  • Ligerorm-PCS commits to Gabidulin encodings of the coefficient-matrix columns with a Merkle root, then uses the interleaved-code IOPP for testing and evaluation.For evaluation, the verifier sends the challenge-derived vector b = (α, α^q, …, α^(q^(κ−1))).Source: §4.2 · pp. 33–34
  • Under the stated square-dimension and field assumptions, the PCS has bounded binding soundness and binds a commitment to a unique q-linearized polynomial with evaluation binding.A valid close interleaved codeword determines the unique polynomial; an accepted evaluation must equal that polynomial’s value at α.Source: §4.2 · p. 34
  • Acceptance enables column-wise Gabidulin decoding and Moore interpolation to recover the committed polynomial g; evaluation binding then forces beta=g(alpha).Source: §4.2 · p. 35
  • For t=Theta(lambda), the scheme has prover and verifier time Õ(lambda k) and proof size Õ(lambda k) elements over F_qm.These bounds assume independent query repetitions.Source: §4.2 · pp. 35–36
  • Although random F_q-linear queries can test rank proximity with error at most q^-t(e+1), supporting arbitrary linear openings adds roughly 1/q soundness per check, so the PCS retains coordinate queries.The coordinate-query test instead relies on the fact that rank distance is no greater than Hamming distance.Source: §4.2 · p. 36
  • The proximity-gap soundness error requires m to exceed n by an amount growing with the security parameter and depending on q to reach 2^-lambda, potentially limiting scalability due to extension-field arithmetic costs.The authors leave concrete applications in small or moderate-size instances and practical performance evaluation for future work.Source: §4.2 · p. 36
Loading 2609.09838v1…