Paper 2026/2081

FRI-Style Rank Metric PCS via FFT for Gabidulin Encoding

Abstract

Polynomial commitment schemes (PCSs) are fundamental cryptographic primitives, with applications to SNARKs, data availability, and privacy preserving protocols. Many efficient transparent PCSs are built from interactive oracle proofs of proximity (IOPPs) for codes in the Hamming metric. In constructions based on the fast Reed-Solomon IOPP (FRI), low degree polynomials are encoded as Reed-Solomon (RS) codewords over suitable evaluation domains, and FRI is used to test proximity to the RS code. The efficiency of this approach relies on fast Fourier transform (FFT) based encoding and recursive proximity testing through folding operations. Motivated by applications of rank metric codes in post quantum cryptography, random linear network coding, and distributed storage, we develop an analogous framework based on Gabidulin codes, the rank metric counterparts of RS codes. These codes encode $q$-linearized polynomials of bounded $q$-degree over $\mathbb F_{q^m}$ by evaluating them at $\mathbb F_q$-linearly independent points in this field. We construct a recursive FFT for these polynomials and show that its algebraic structure supports both proximity testing for Gabidulin codes and succinct verification of polynomial evaluations, yielding a FRI-style PCS for $q$-linearized polynomials. Our contributions are as follows. \begin{enumerate} \item[(1)] \textbf{FFT algorithms for $q$-linearized polynomials.} For every $O(1)$-smooth positive integer $n\mid m$, we construct an $\mathbb F_q$-linearly independent evaluation set $\mathcal A\subseteq\mathbb F_{q^m}$ of size $n$. On this set, we present FFT and inverse FFT algorithms for evaluating and interpolating $q$-linearized polynomials of $q$-degree less than $n$ over $\mathbb F_{q^m}$. Both algorithms require $O(n\log n)$ operations in $\mathbb F_{q^m}$. Consequently, Gabidulin codes defined over $\mathcal A$ admit encoding with the same complexity. \item[(2)] \textbf{A FRI-style IOPP for Gabidulin codes.} The recursive structure of our FFT induces a folding operation that reduces a Gabidulin code instance of length $n$ to one of length $n/2$. Combining this operation with recent proximity gap results for Gabidulin codes, we construct a FRI-style IOPP, which we call the Fast Gabidulin IOPP (FGI). The soundness analysis accounts for the Frobenius twists introduced by folding and their effect on rank metric proximity. \item[(3)] \textbf{A FGI based PCS for $q$-linearized polynomials.} The usual quotient based opening reduction in PCSs for ordinary polynomials does not directly preserve for $q$-linearized polynomials. We instead use the FGI folding structure to recursively reduce the proximity claim and the evaluation claim together. Combined with Merkle tree commitments, this yields a transparent PCS for $q$-linearized polynomials with polylogarithmic proof size and verification time. \end{enumerate}