Polylogarithmic Proofs for Multilinears over Binary Towers

Abstract

The use of small fields has come to typify the design of modern, production-oriented SNARKs. In this work, we treat multilinear polynomial commitment over tiny fields. A tiny-field polynomial—in the nomenclature of Diamond and Posen (EUROCRYPT ’25)—is defined over a field that has fewer elements than the polynomial itself has coefficients. We focus on multilinears over the field with just two elements.

In this work, we generically reduce the problem of tiny-field commitment to that of large-field commitment. We introduce a sumcheck-based compiler—called “ring-switching”—which, upon being fed a multilinear polynomial commitment scheme over some large extension field, yields a further scheme over that field’s ground field. The resulting scheme lacks embedding overhead, in that its commitment cost, on each input, equals that of the large-field scheme on each input of identical size (in bits). Its evaluation protocol’s overhead is linear for the prover and logarithmic for the verifier, and is essentially optimal.

Instantiating our ring-switching reduction on the BaseFold (CRYPTO ’24) large-field multilinear polynomial commitment scheme—or more precisely on a characteristic-2 adaptation of that scheme that we develop at length—we obtain an extremely fast polynomial commitment scheme for bit-valued multilinears. Our scheme outperforms its state-of-the-art peers, a fact we demonstrate experimentally.

1  Introduction

Today’s fastest, production-oriented SNARKs universally use small fields. Before 2022, virtually all SNARKs operated over just one—cryptographically large—field. The small-field revolution began in earnest with ethSTARK and Plonky2. Those systems decouple the respective fields used within their arithmetization and cryptography portions. That is, they use small fields—sized roughly like a 64-bit register—for their arithmetizations; each, during its security-critical portions, passes to a cryptographically large field extension of its arithmetization field. Subsequent production-oriented SNARKs like Plonky3 and RISC Zero have embraced similar designs, based on 32-bit prime fields; S-two has adopted a related architecture based on Haböck, Levit and Papini’s Circle STARK [HLP24]. By using small fields, these systems have managed to deliver industry-leading provers, which outperform those grounded in elliptic-curve-based SNARKs (like Sonic [MBKM19], PlonK [GWC19] and Marlin [Chi+20]).

These SNARKs all use arithmetization fields which, though relatively small, are nonetheless at least as large as the statements they’re capable of proving. This fact is not a coincidence. Indeed, all of them operate by, roughly, arranging their witness data into a trace table, Reed–Solomon-encoding that table’s columns, and finally invoking a low-degree test based on FRI [BBHR18a]. Reed–Solomon codes demand alphabets that are at least as large as their block lengths are.

A recent work of Diamond and Posen [DP25] breaks this trace-length barrier, in that it treats even polynomials over tiny fields—fields smaller than the statement’s trace length. Crucially, that work does so without embedding overhead. One might trivially attempt to commit to a tiny-field multilinear simply by embedding its coefficients into an extension, before blackbox-invoking a standard scheme on the resulting object. That approach would face at least two deficiencies. On the efficiency front, it would secure no gain from the tininess of its input’s coefficients. On the security front, it would fail to guarantee the tininess of the prover’s input, a security desideratum which, in practice, turns out to be essential.

In this work, we introduce a generic reduction from the problem of tiny-field multilinear polynomial commitment to that of large-field multilinear commitment. Our techniques are rather different from those of Diamond–Posen [DP25]. Our reduction, applied to any large-field scheme, yields a corresponding tiny-field scheme, which moreover lacks embedding overhead. It is agnostic to the large-field scheme used. In fact, our reduction works even on recently introduced, state-of-the-art large-field schemes like Blaze [Bre+25] and WHIR [ACFY25], and even on large-field schemes that haven’t been created yet. Its overhead over the underlying large-field scheme given to it is essentially optimal, and beats that associated with alternative constructions, like Hashcaster.

1.1  Some Historical Remarks

Diamond and Posen [DP25] break the trace-length barrier by further decoupling two fields which, in all of the small-field schemes noted above, coincide: the arithmetization field and the alphabet field. All of those schemes use just one prime field—again, sized just under 32 or 64 bits—both as the coefficient field of the polynomials committed and as the alphabet of the Reed–Solomon code used to encode them. The scheme [DP25] makes possible the simultaneous use of a tiny arithmetization field and a small alphabet field. Separately, that work reintroduces the use of binary fields, fields of characteristic 2. Finally, that work treats exclusively multilinear polynomials; in this capacity, it extends an important line of work which includes Libra [Xie+19], Virgo [ZXZS20], Spartan [Set20], Brakedown [Gol+23], and HyperPlonk [CBBZ23].

To make their technique work, Diamond and Posen [DP25] introduce a data-casting operation—which they call packing, and which is based on field extensions—which serves to recast a witness defined over \mathbb{F}_2, say, into a shorter witness over the larger field \mathbb{F}_{2^{32}}. They then apply a Brakedown-like multilinear commitment procedure to the resulting witness, whose coefficient field, crucially, is large enough to be used as a Reed–Solomon alphabet.

As Diamond and Posen [DP25] implicitly observe, unlike DEEP-ALI [BGKS19], Brakedown [Gol+23]—like its predecessor works Bootle, Chiesa and Groth [BCG20] and Ron-Zewi and Rothblum [RR24]—decouples the coding-theoretic specifications of its code from the semantics of its code. This decoupling makes Diamond and Posen’s packing procedure coherent.

Zeilberger, Chen and Fisch’s BaseFold PCS [ZCF24, § 5] seems to be the first multilinear polynomial commitment scheme with a polylogarithmic verifier that doesn’t use quotienting. This work’s small-field PCS works in a drop-in way with the PIOP of [DP25]. By combining this work’s PCS with that work’s PIOP, one stands to obtain an efficient, full-blown SNARK for binary witnesses.

1.2  Our Contributions

We sketch our contributions here.

A reduction from tiny-field commitment to huge-field commitment. Ring-switching is a generic compiler, which, on input a multilinear polynomial commitment scheme over some large extension field L/K, yields a new multilinear polynomial commitment scheme over the ground field K. Here, L can be of any characteristic, including 2. Each scheme our compiler outputs lacks embedding overhead, in that its commitment cost on each K-multilinear equals the original scheme’s commitment cost on an L-multilinear of equal size in bits.

We write 2^\kappa for the degree of L over K, which we assume is a power of 2. Diamond and Posen’s [DP25, § 4] packing procedure takes in an \ell-variate multilinear t(X_0, \ldots, X_{\ell-1}) over K and produces the packed multilinear t'(X_0, \ldots, X_{\ell'-1}) over L, where \ell' := \ell - \kappa. Our K-scheme’s commitment procedure simply packs t(X_0,\ldots,X_{\ell-1}) and invokes the underlying L-scheme’s commitment procedure on t'(X_0,\ldots,X_{\ell'-1}), the result. The hard part is relating an evaluation claim on t to one on t'. To do this, we devise an unusual matrix-transposition trick, and write down an \ell - \kappa-round sumcheck between t' and a new sort of polynomial we call a ring-switch equality indicator.

An improved multilinear PCS for large binary fields, based on BaseFold. Zeilberger, Chen and Fisch’s BaseFold PCS [ZCF24, § 5] is an important multilinear polynomial commitment scheme for large prime fields. In order to spin up a target for our ring-switching reduction, we develop a characteristic-2 variant of BaseFold PCS, i.e. for large binary fields. We also improve that scheme by incorporating into it higher-arity folding, an optimization that reduces its proof sizes by more than half.

To make higher-arity folding work with BaseFold, we introduce oracle-skipping, a new higher-arity folding mechanism. Our security proof necessitates a different sort of proximity gap than FRI’s approach does, one pertaining not to low-degree curves but instead to tensor combinations. Precisely this kind of proximity gap is established in recent work of Diamond and Gruen [DG25], which we leverage.

A state-of-the-art PCS for multilinears over tiny binary fields. Putting the two parts above together, we obtain an extremely fast PCS for tiny-field multilinears. On a 28-variate multilinear over \mathbb{F}_2, our scheme achieves singlethreaded commitment and opening times of just 144 and 160 milliseconds, respectively; our multithreaded commitment and opening times are 44 and 71 milliseconds, respectively. Our proofs for polynomials of this size are 0.351 MiB, and our verifier runs in under a millisecond.

Our measurements beat Plonky3’s by between one and two orders of magnitude. Plonky3 takes 25 and 13 seconds, respectively, to commit a comparable amount of data, in the singlethreaded setting, and 4 and 2 seconds in multithreaded mode. Its proofs are also larger, and its verifier is around 20 milliseconds.

1.3  Ring-Switching

In this subsection, we gently introduce ring-switching, prioritizing technical simplicity and accuracy. We fix a field extension L/K of power-of-2 degree 2^\kappa. Though ring-switching works for any such field extension, of any characteristic, the special case K = \mathbb{F}_2 and L = \mathbb{F}_{2^{128}} is especially important and exemplary. We write \mathcal{B}_\kappa := \{0,1\}^\kappa for the \kappa-dimensional unit cube.

The problem. We assume access to a large-field multilinear polynomial commitment scheme for multilinears over L. How might we obtain a small-field commitment scheme for multilinears over K, assuming access to that large-field scheme?

We begin with a small-field multilinear, say t(X_0, \ldots, X_{\ell-1}) \in K[X_0, \ldots, X_{\ell-1}]^{\leq 1}, that we’d like to commit to. Following Diamond and Posen [DP25], we fix a basis (\beta_v)_{v \in \mathcal{B}_\kappa} of L over K, write \ell' := \ell - \kappa, and define the packed multilinear:

Our commitment procedure is simple: it just packs t(X_0, \ldots, X_{\ell-1}) and invokes the underlying large-field scheme’s commitment procedure on t'(X_0, \ldots, X_{\ell'-1}). This procedure lacks embedding overhead, since t and t' are of the same size in bits.

To check an evaluation claim on t, we must reduce it to one on t'. We fix a point (r_0, \ldots, r_{\ell-1}) and an evaluation claim s \stackrel{?}{=} t(r_0, \ldots, r_{\ell-1}).

A strawman approach. The prover sends values (\hat{s}_v)_{v \in \mathcal{B}_\kappa} which—it claims—respectively satisfy \hat{s}_v \stackrel{?}{=} t(v_0, \dots, v_{\kappa-1}, r_\kappa, \dots, r_{\ell-1}) for each v \in \mathcal{B}_\kappa. The verifier checks whether

holds. While this protocol is complete, it’s not secure. The basis (\beta_v)_{v \in \mathcal{B}_\kappa} is linearly independent over K, but not over L.

Our solution. Our idea is—very roughly—to further decompose the claims until they are defined over K. We may then apply the linear combination “slice-wise”. For each v \in \mathcal{B}_\kappa, the verifier can freely basis-decompose the prover’s quantity \hat{s}_v, writing

for appropriate K-elements. After further decomposition, batching via random scalars (r''_0, \ldots, r''_{\kappa-1}), and running a sumcheck, the verifier must finally evaluate the “ring-switch equality indicator”

where \varphi_0 and \varphi_1 denote the two canonical embeddings of L into the tensor algebra A := L \otimes_K L. The verifier may compute this quantity succinctly in just 2 \cdot 2^\kappa \cdot \ell' L-multiplications.

Hashcaster. We compare ring-switching in detail to Hashcaster. Soukhanov’s Hashcaster [Sou24] is a SNARK for binary witnesses. That work yields an alternative reduction from the problem of evaluating the K-multilinear to that of evaluating its packed L-multilinear. Hashcaster’s verifier must compute a matrix transformation that entails a quadratic number of L-multiplications in the extension degree 2^\kappa. Ring-switching’s verifier’s number of L-multiplications grows only linearly.

1.4  Binary BaseFold

In order to apply ring-switching, we need a large-field scheme to invoke it on. To this end, we adapt BaseFold PCS [ZCF24, § 5] to the characteristic 2 setting. To achieve this, we must re-examine the classic additive NTT of Lin, Chung and Han [LCH14]. We show that that NTT fits into a framework articulated by Haböck, Levit and Papini [HLP24], though it predates that latter work.

The problem. BaseFold PCS identifies a connection between FRI and multilinear evaluation. Each honest FRI prover begins with the evaluation of some polynomial P(X) := \sum_{j=0}^{2^\ell-1} a_j \cdot X^j over its initial domain S^{(0)}. During the course of the protocol, the prover repeatedly “folds” its initial word. BaseFold PCS relies on the fact whereby a FRI execution which begins on the Reed–Solomon encoding will end on a constant polynomial whose value equals the multilinear evaluation at the verifier’s FRI challenges. For maps chosen generically, this fact will fail to hold in characteristic 2.

Our solution. We recover BaseFold PCS in characteristic 2 by introducing a specialization of binary FRI that works compatibly with Lin–Chung–Han’s additive NTT [LCH14]. We introduce a particular choice of folding maps q^{(0)}, \ldots, q^{(\ell-1)} which causes the equality between the final FRI constant and the multilinear evaluation to re-emerge. The right choice turns out to be that for which, for each i, the composition identity \widehat{W}_i = q^{(i-1)} \circ \dots \circ q^{(0)} holds, where \widehat{W}_i are Lin–Chung–Han’s normalized subspace vanishing polynomials.

Oracle-skipping. Standard FRI supports arbitrary-arity folding, controlled by a folding arity parameter \eta \geq 1. BaseFold PCS, however, does not support the use of univariate higher-arity folding. We introduce a new, multilinear style of many-to-one FRI folding. We parameterize our method by a constant \vartheta: the prover performs standard 2-to-1 folding \vartheta times in succession, committing only to the last among the oracles it obtains. Our folding technique makes necessary a tensor-folding proximity gap of the sort recently established by Diamond and Gruen [DG25].

1.5  Concurrent and Subsequent Works

Blaze. Blaze [Bre+25] is a polynomial commitment scheme for multilinears over large binary fields. Using a technique grounded in code-switching [RR24], Blaze obtains a strictly linear-time commitment procedure, a linear-time prover, and a polylogarithmic verifier. Operating over \mathbb{F}_{2^{128}} throughout, Blaze reports commitment and proving times that improve upon binary BaseFold’s by roughly threefold at the \ell = 28 problem size, though its proofs are larger (2.5 MiB compared to 1.4 MiB for binary BaseFold). Incorporating oracle-skipping and further concrete proof size optimizations, this work obtains a proof size of 0.436 MiB in the \ell = 28 case.

Blaze’s PCS is compatible with this work’s ring-switching compiler. Upon instantiating our ring-switching reduction on Blaze’s large-field PCS, one would obtain an alternative small-field scheme.

2  Background and Notation

We write \mathbb{N} for the nonnegative integers. All fields in this work are finite. We fix a binary field L. For each \ell \in \mathbb{N}, we write \mathcal{B}_\ell for the \ell-dimensional boolean hypercube \{0,1\}^\ell \subset L^\ell. For L a field and R \subset L^\vartheta a subset, we write \mu(R) := \frac{|R|}{|L|^\vartheta}.

2.1  Multilinear Polynomials

An \ell-variate polynomial in L[X_0,\ldots,X_{\ell-1}] is multilinear if each of its indeterminates appears with individual degree at most 1. We introduce the 2 \cdot \ell-variate polynomial

For each fixed (r_0, \ldots, r_{\ell-1}) \in L^\ell, the vector (\widetilde{\text{eq}}(r_0, \ldots, r_{\ell-1}, w_0, \ldots, w_{\ell-1}))_{w \in \mathcal{B}_\ell} takes the form of a tensor product expansion \bigotimes_{i=0}^{\ell-1} (1 - r_i, r_i), computable in 2^\ell L-additions and L-multiplications.

2.2  Error-Correcting Codes

A code of block length n over the alphabet \Sigma is a subset of \Sigma^n. A linear [n,k,d]-code over L is a k-dimensional linear subspace C \subset L^n for which d(v_0,v_1) \geq d holds for each unequal pair. The unique decoding radius is \lfloor \frac{d-1}{2} \rfloor.

We recall Reed–Solomon codes. We fix nonnegative message length and rate parameters \ell and \mathcal{R}, as well as a subset S \subset L of size 2^{\ell+\mathcal{R}}. We write C for the Reed–Solomon code \mathsf{RS}_{L,S}[2^{\ell+\mathcal{R}},2^\ell], defined to be the set of evaluation vectors of polynomials of degree less than 2^\ell over S.

2.3  The Novel Polynomial Basis

We recall in detail the novel polynomial basis of Lin, Chung and Han [LCH14, § II. C.]. We fix a binary field L of degree r over \mathbb{F}_2. We fix an \mathbb{F}_2-basis (\beta_0, \dots, \beta_{r-1}) of L. For each i \in \{0, \dots, \ell\}, we define the subspace vanishing polynomial W_i(X) := \prod_{u \in U_i}(X-u) and its normalized variant \widehat{W}_i(X) := \frac{W_i(X)}{W_i(\beta_i)}. The novel polynomial basis elements are X_j(X) := \prod_{i=0}^{\ell-1}\widehat{W}_i(X)^{j_i}.

2.4  FRI

We recall Ben-Sasson, Bentov, Horesh and Riabzev’s [BBHR18a] Fast Reed–Solomon Interactive Oracle Proof of Proximity (FRI). For L a binary field, FRI yields an IOP of proximity for the Reed–Solomon code. Internally, FRI makes use of a fixed, global sequence of subspaces and maps:

For each i, q^{(i)} is a subspace polynomial of degree 2, whose kernel is 1-dimensional and contained in S^{(i)}.

2.5  Tensor Products of Fields

We define the tensor product A := L \otimes_K L of L with itself over K. Each A-element is, concretely, a 2^\kappa \times 2^\kappa array of K-elements. For each a \in A, there is a unique tuple of L-elements (a_v)_{v \in \mathcal{B}_\kappa} for which a = \sum_{v \in \mathcal{B}_\kappa} a_v \otimes \beta_v holds (the column representation). Similarly, there is a unique row representation.

The maps \varphi_0 and \varphi_1 respectively embed L into A’s left-hand column and top row. Concretely, \varphi_0(\alpha) \cdot a differs from a by column-wise multiplication by \alpha; \varphi_1(\alpha) \cdot a differs from a by row-wise multiplication by \alpha.

2.6  Proximity Gaps

2.7  Security Definitions

3  Ring-Switching

In this section, we formally present ring-switching. The key identity underlying the protocol is tensor-algebraic:

For each pair of L-elements \alpha_0 and \alpha_1, the exterior product satisfies \alpha_0 \star \alpha_1 = \varphi_0(\alpha_0) \cdot \varphi_1(\alpha_1), where the right-hand product is the ambient multiplication in the tensor algebra.

3.1  Ring-Switching Protocol

3.2  Efficiency

Prover cost. The prover’s main cost is that of computing the tensor expansion \bigotimes_{i=\kappa}^{\ell-1} (1 - r_i, r_i), taking 2^{\ell'} L-multiplications. The total prover cost is O(2^\ell) \cdot \lambda K-operations—linear in the input length and the security parameter.

Verifier cost. To compute e, the verifier must perform 2 \cdot 2^\kappa \cdot \ell' L-multiplications (via Remark 3.4: alternating column-scaling and row-scaling with transpositions). The verifier is logarithmic in the statement size and quadratic in \lambda (up to polylogarithmic factors): O(\ell) \cdot \widetilde{O}(\lambda^2) K-operations.

Comparison to Hashcaster. Hashcaster’s verifier’s dependence on \lambda is cubic (\widetilde{O}(\lambda^3) K-operations), as opposed to our quadratic. Hashcaster’s prover, if implemented naïvely, is about 2^\kappa-fold more costly than ours.

4  Binary BaseFold

In this section, we present our large-field PCS. We tie together Lin, Chung and Han [LCH14]’s additive NTT and FRI [BBHR18a].

4.1  Using FRI in Novel Polynomial Basis

4.2  FRI Folding, Revisited

4.3  Our Large-Field IOPCS

4.4  Efficiency

Prover cost. In its commitment phase, the prover uses Lin, Chung and Han’s additive NTT to encode its length-2^\ell vector, using 2^{\ell+\mathcal{R}-1} \cdot \ell L-multiplications and 2^{\ell+\mathcal{R}} \cdot \ell L-additions. The prover is linear-time.

Verifier cost. The verifier expends O(\ell) L-operations for the sumcheck, and O(\lambda \cdot \ell) total L-operations for \gamma query repetitions.

5  Unrolled Small-Field IOPCS

In this section, we describe a one-shot small-field IOPCS construction. This construction inlines the large-field IOPCS of Section 4 into the ring-switching reduction of Section 3, and streamlines the combination by unifying the two sumchecks.

5.1  Combined Small-Field Protocol

5.2  Efficiency

Concrete soundness. Construction 5.1’s concrete soundness error is bounded from above by

Proof sizes. In Table 1 below, we compare [DP25, Cons. 3.11] and Construction 5.1 on input polynomials over \mathbb{F}_2, processing evaluation claims over \mathbb{F}_{2^{128}}, attaining 100 bits of provable security.

Table 1: Proof sizes of polynomial commitment schemes for \mathbb{F}_2-multilinears. Folding factor \vartheta := 4, Merkle cap height j := 8.

Concrete performance. We benchmark Construction 5.1 against Plonky3 using Binius, an open-source SNARK. Both schemes use a 128-bit field. This work uses the GHASH field \mathbb{F}_2[X]/(X^{128} + X^7 + X^2 + X + 1) \cong \mathbb{F}_{2^{128}}. Plonky3 uses the quartic extension of the Baby Bear prime field. Throughout, we use rate \rho = \frac{1}{2} and attain 100 bits of provable security.

Table 2: Concrete performance benchmarks on 28-variate multilinears over \mathbb{F}_2 (this work) and batches of 16 degree-2^{24} polynomials over Baby Bear (Plonky3). AWS c7i.8xlarge, SHA-256 Merklization.

Our scheme outperforms Plonky3 by between one and two orders of magnitude across all computational performance metrics. Our proofs are also smaller by more than fivefold.

References

1. [ACFY25] Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev. “WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification”. EUROCRYPT 2025, pp. 214–243.
2. [AER24] Guillermo Angeris, Alex Evans, and Gyumin Roh. A Note on Ligero and Logarithmic Randomness. ePrint 2024/1399.
3. [AHIV23] Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. “Ligero: lightweight sublinear arguments without a trusted setup”. Designs, Codes and Cryptography (2023).
4. [BBHR18a] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. “Fast Reed-Solomon Interactive Oracle Proofs of Proximity”. ICALP 2018, 14:1–14:17.
5. [BBHR18b] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. ePrint 2018/046.
6. [BCG20] Jonathan Bootle, Alessandro Chiesa, and Jens Groth. “Linear-Time Arguments with Sublinear Verification from Tensor Codes”. TCC 2020, pp. 19–46.
7. [BCS16] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. “Interactive Oracle Proofs”. TCC 2016, pp. 31–60.
8. [Ben+23] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. “Proximity Gaps for Reed–Solomon Codes”. Journal of the ACM 70.5 (Oct. 2023).
9. [BGKS19] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. ePrint 2019/336.
10. [Bre+25] Martijn Brehm, Binyi Chen, Ben Fisch, Nicolas Resch, Ron D. Rothblum, and Hadas Zeilberger. “Blaze: Fast SNARKs from Interleaved RAA Codes”. EUROCRYPT 2025, pp. 123–152.
11. [Can89] David G Cantor. “On arithmetical algorithms over finite fields”. J. Combinatorial Theory, Series A 50.2 (1989), pp. 285–300.
12. [CBBZ23] Binyi Chen, Benedikt Bünz, Dan Boneh, and Zhenfei Zhang. “HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates”. EUROCRYPT 2023.
13. [Chi+20] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas Ward. “Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS”. EUROCRYPT 2020, pp. 738–768.
14. [COS20] Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. “Fractal: Post-quantum and Transparent Recursive Proofs from Holography”. EUROCRYPT 2020, pp. 769–793.
15. [DG25] Benjamin E. Diamond and Angus Gruen. “Proximity Gaps in Interleaved Codes”. IACR Comms. in Cryptology 1.4 (Jan. 2025).
16. [DP24] Benjamin E. Diamond and Jim Posen. “Proximity Testing with Logarithmic Randomness”. IACR Comms. in Cryptology 1.1 (2024).
17. [DP25] Benjamin E. Diamond and Jim Posen. “Succinct Arguments over Towers of Binary Fields”. EUROCRYPT 2025, pp. 93–122.
18. [GG13] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. 3rd Edition. Cambridge University Press, 2013.
19. [GLL19] Shay Gueron, Adam Langley, and Yehuda Lindell. AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption. RFC 8452, Apr. 2019.
20. [GM10] Shuhong Gao and Todd Mateer. “Additive Fast Fourier Transforms Over Finite Fields”. IEEE Trans. Inf. Theory 56.12 (2010), pp. 6265–6272.
21. [Gol+23] Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. “Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS”. CRYPTO 2023, pp. 193–226.
22. [Gur06] Venkatesan Guruswami. Algorithmic Results in List Decoding. Foundations and Trends in TCS 2. now publishers, 2006.
23. [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK. ePrint 2019/953.
24. [Hab22] Ulrich Haböck. A summary on the FRI low degree test. ePrint 2022/1216.
25. [Hab24] Ulrich Haböck. A note on the G-FFT. ePrint 2024/1036.
26. [HLP24] Ulrich Haböck, David Levit, and Shahar Papini. Circle STARKs. ePrint 2024/278.
27. [LAH16] S.-J. Lin, T. Y. Al-Naffouri, and Y. S. Han. “FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed–Solomon Codes”. IEEE Trans. Inf. Theory 62.10 (2016), pp. 5343–5358.
28. [Lan02] Serge Lang. Algebra. Revised Third Edition. Springer, 2002.
29. [LCH14] Sian-Jheng Lin, Wei-Ho Chung, and Yunghsiang S. Han. “Novel Polynomial Basis and Its Application to Reed–Solomon Erasure Codes”. IEEE FOCS 2014, pp. 316–325.
30. [Li+18] Wen-Ding Li, Ming-Shing Chen, Po-Chun Kuo, Chen-Mou Cheng, and Bo-Yin Yang. “Frobenius Additive Fast Fourier Transform”. ACM ISSAC 2018.
31. [LN96] Rudolf Lidl and Harald Niederreiter. Finite Fields. 2nd Edition. Cambridge University Press, 1996.
32. [LX24] Songsong Li and Chaoping Xing. “Fast Fourier transform via automorphism groups of rational function fields”. SODA 2024, pp. 3836–3859.
33. [MBKM19] Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. “Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings”. ACM CCS 2019, pp. 2111–2128.
34. [RR24] Noga Ron-Zewi and Ron Rothblum. “Local Proofs Approaching the Witness Length”. Journal of the ACM 71.3 (June 2024).
35. [Set20] Srinath Setty. “Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup”. CRYPTO 2020, pp. 704–737.
36. [Sou24] Lev Soukhanov. “Hashcaster”. Unpublished report. Sept. 2024.
37. [Tha22] Justin Thaler. Proofs, Arguments and Zero-Knowledge. Foundations and Trends in Privacy and Security, vol. 4. now publishers, 2022.
38. [Wat79] William C. Waterhouse. “The Normal Basis Theorem”. The American Mathematical Monthly 86.3 (1979), pp. 212–212.
39. [Xie+19] Tiacheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. “Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation”. CRYPTO 2019, pp. 733–764.
40. [ZCF24] Hadas Zeilberger, Binyi Chen, and Ben Fisch. “BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes”. CRYPTO 2024, pp. 138–169.
41. [ZXZS20] Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song. “Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof”. IEEE S&P 2020, pp. 859–876.