Folding schemes in the lattice setting: pay-per-bit and NTTs
Lattice cryptography allows us to build cryptographic primitives from hard lattice problems. LatticeFold[1] is the first lattice-based folding scheme protocol, inspired by HyperNova[2], whose security is rooted in the Module Short Integer Solution (MSIS) problem. In short, it substitutes the existing discrete logarithm-based commitment schemes such as KZG[3] with Ajtai commitments (or more precisely, a module-based version of Ajtai commitments proposed by Lyubashevsky et al[4]). Ajtai commitments require the committed elements to have a small norm. This extra step of having to prove that witnesses are small turns out to be a major complication in lattice-based zero-knowledge proofs in comparison to their discrete logarithm-based counterparts. As expected, the main challenge in lattice-based folding schemes comes from managing norm growth after folding.
Arguably, one of the main drawbacks of LatticeFold is the use of Number Theoretic Transforms (NTTs) when embedding fields from a given instance (e.g., Customisable Constraint System (CCS) [5]) into polynomial rings needed in the Ajtai commitment scheme. Neo[6], a recent folding scheme inspired by LatticeFold, avoids running NTTs thanks to a different encoding, and achieves a so called "pay-per-bit" commitment scheme, where the cost of committing to an element is linear to the number of bits. Since for most cases the elements to be committed are small, this "pay-per-bit" property is desirable.
Thus, this note aims to address the following connected questions:
- What was the approach that LatticeFold took in their field-to-polynomial ring embedding?
- How does Neo avoid NTTs and achieves pay-per-bit in their commitment scheme while preserving homomorphism?
Note that this post only focuses on the differences of the field-to-polynomial ring encoding between LatticeFold and Neo. But there is a lot more to these schemes than what is mentioned here, including open problems such as adding zero-knowledge or compressing the size of the proofs, that I hope to cover in the near future. I also didn't mention a more recent folding scheme called LatticeFold+[7] which eliminates the need to compute many commitments for the decomposed vectors and addresses the expensive grand-product that is used in LatticeFold for the norm bound check. It is worth mentioning that Neo's field encoding method is also fully compatible with LatticeFold+'s new range proof, which can further boost the efficiency of LatticeFold+.
Background
Before we jump into the different embeddings of LatticeFold and Neo and their trade-offs, I will briefly outline the main primitives used. Cyclotomic rings are the underlying algebraic structure upon which Ajtai commitments operate, and NTTs one of the means to embed finite field elements (e.g. from a CCS relation) to cyclotomic rings. I hope to make this background section as contextual as possible.
Cyclotomic Polynomials
The $n$-th cyclotomic polynomial is the unique monic irreducible polynomial that divides $x^n - 1$ but doesn't divide $x^k - 1$, for any $k < n$. If it were not monic it wouldn't be unique. It is worth noting that the roots of this polynomial are the $n$-th primitive roots of unity, that is, those elements $\zeta$ in $\mathbb{C}$ such that $\zeta^n = 1$, but $\zeta^k \neq 1$ for all $k < n$.
The number of $n$-th primitive roots of unity comes from the Euler's totient function $\phi(n)$, which gives the number of integers $k$ in the range $1 \leq k \leq n$ for which $\gcd(n, k)$ is equal to $1$. For example, if $n$ is prime, then $\phi(n) = n-1$ and the $n$-th cyclotomic polynomial is of the form $\Phi_n(X)=X^{n-1} + \ldots+ X + 1$. If $n$ is a power of 2, $n = 2^s$, then $\phi(n) = 2^{s-1}$. The $n$-th cyclotomic polynomial is $\Phi_n(X) = X^{n/2} + 1$. The latter example is the cyclotomic polynomial used in LatticeFold, which also restricts the fields upon which LatticeFold can be instantiated. Neo doesn't have this restriction.
Cyclotomic Rings
Lattice-based protocols are built upon well-known computational lattice problems, such as Module-SIS (MSIS), which are defined over a polynomial ring $\mathcal{R}_q$.
As we noted, if $d$ a power of 2, then $n = 2d$ is also a power of 2 and $\Phi_n(X) = X^d + 1$ is such $n$-th cyclotomic polynomial. The ring $\mathcal{R} := \mathbb{Z}[X]/(X^d + 1)$ is called cyclotomic. This is the ring of polynomials of the form:
$$ \mathcal{R} := \{ a_{d-1} X^{d-1} + \ldots + a_1 X + a_0 \mid a_i \in \mathbb{Z}, X^d = -1 \}. $$LatticeFold sets $q$ to be a prime such that $q \equiv 1 + 2t \pmod{4t}$, for $t$ a divisor of $d$, i.e. $t = 2^s$ is also a power of $2$, then $\mathbb{F}_q$ has $t$ primitive $2t$-th roots of unity.
$$\begin{aligned} q - 1 &\equiv 2t \pmod{4t}, \\ q - 1 &= 2t + 4kt = 2t \cdot (2k +1). \end{aligned}$$Because $2t \mid q - 1$, $\mathbb{F}_q$ contains all $2t$-th primitive roots of unity $\{\zeta_j\}_{j \in [t]}$ in $\mathbb{F}^{\times}_q$. Because $4t \nmid q - 1$, $X^{d/t} - \zeta_j$ is irreducible in $\mathbb{F}_q[X]$ for all $j \in [t]$. We can check that $\zeta_j$ is indeed a $2t$-th primitive root of unity: If $x^{d/t} = \zeta_j$, then $x^d = \zeta_j^t = -1$ and so $\zeta_j^{2t} = 1$. Thus, $X^d + 1 \equiv \prod_{j = 1}^t (X^{d/t} - \zeta_j) \pmod{q}$.
It is clear that $X^{d/t} - \zeta_i$ and $X^{d/t} - \zeta_j$ are irreducible and co-prime if $i \neq j$, so we can apply the Chinese Remainder Theorem and $\mathcal{R}_q := \mathcal{R}/q\mathcal{R} = \mathbb{F}_q[X] / (X^d + 1)$ can be split into the product of $t$ quotient rings:
$$ \mathcal{R}_q \cong \prod_{j = 1}^t \mathbb{F}_q[X]/(X^{d/t} - \zeta_j) \cong \mathbb{F}^t_{q^{d/t}}, $$where $\mathbb{F}_{q^{d/t}}$ is the extension field given by $X^{d/t} = \zeta_j$.
LatticeFold simplifies the rest of their exposition by setting $t = d$ (so $q \equiv 1 + 2d \pmod{4d}$). In this case, there are $d$ $n$-th ($n = 2d$) primitive roots of unity in $\mathbb{F}_q$ and
$$ \mathcal{R}_q \cong \prod_{j=1}^d \mathbb{F}_q[X]/(X-\zeta_j) \cong \mathbb{F}_q^d. $$Note that this restriction on the choice of $q$ is what makes LatticeFold not work with certain finite fields such as Goldilocks or Mersenne61. Section 3.3 of LatticeFold describes a modification that supports a wider class of moduli, i.e., any $\mathcal{R}_q \cong \mathbb{F}^{d/t}_{q^t}$ where $t | d$.
Number Theoretic Transforms (NTTs)
Given $\mathcal{R}_q := \mathcal{R}/q\mathcal{R} = \mathbb{F}_q[X] / (X^d + 1)$ for $d$ a power of $2$, an NTT consists of the evaluations of a polynomial $f \in \mathcal{R}_q$ at the $d$ $n$-th primitive root of unity $\{\zeta_j\}_{j \in [d]}$ as described above. That is,
$$ \text{NTT}(f) := [f(\zeta_1), \ldots, f(\zeta_d)]^T $$Equivalently,
$$ \text{NTT}(f) := [\hat{f}_1, \ldots, \hat{f}_d]^T \in \mathbb{F}_{q^{d/t}}^t, $$where $\hat{f}_j := f \bmod (X - \zeta_j)$. In other words, for all $j \in [d]$, $f \bmod (X - \zeta_j) = f(\zeta_j)$. It is easy to see that if $f(X) = q(X) (X - \zeta_j) + r$, then $f(\zeta_j) = q(0) \cdot 0 + r = r$ and also $f \bmod (X - \zeta_j) = r$. This is the case when $t = d$. If $t < d$, $t | d$, then the irreducible factor has degree $(d/t)$ instead.
Module-SIS and Ajtai's commitments
Given a matrix $\mathbf{A} \in \mathcal{R}_q^{n \times m}$, the Module-SIS problem consists on finding a vector $\mathbf{s} \in \mathcal{R}_q^m$ of small norm $(0 < |\mathbf{s}| \leq B)$ such that
$$
\mathbf{A}\mathbf{s} = \mathbf{0}.
$$
Solving the SIS problem is equivalent to solving a linear equation system where the matrix $\mathbf{A}$ gives the coefficients and the vector $\mathbf{s}$ the desired variables. The additional requirement that $|\mathbf{s}|$ needs to be small is crucial for the hardness of the problem because otherwise it could be easily solved using Gaussian elimination.
In the Ajtai commitment scheme, one commits to a message $\mathbf{s}_1$ using randomness $\mathbf{s}_2$ (for hiding), where both $|\mathbf{s}_i|$ are small and
$$
\mathbf{A}_1 \mathbf{s}_1 + \mathbf{A}_2 \mathbf{s}_2 = \mathbf{t}.
$$
LatticeFold
Embedding $\mathbb{F}_q$ into $\mathcal{R}_q$
We assume that $t = d$ and $\mathcal{R}_q \cong \prod_{j=1}^d \mathbb{F}_q[X]/(X-\zeta_j) \cong \mathbb{F}_q^d$. An element in $\mathcal{R}_q$ is defined by
$$\mathbf{a}=\sum_{i=1}^{d} a_i X^{i-1}\in\mathcal{R}_q,$$where $a_i \in \mathbb{F}_q$.
LatticeFold packs $d$ instance-witness pairs in the CCS relation over $\mathbb{F}_q$ into a single instance-witness pair in the CCS relation over $\mathcal{R}_q$. There are two ways to interpret $\vec{a} \in \mathbb{F}_q^{m}$:
- as the coefficients embeddings of some $f \in \mathcal{R}_q$
- as the NTT representations of some $\hat{f} \in \mathcal{R}_q$.
In LatticeFold, each entry $a \in \mathcal{R}_q$ is set such that $\text{NTT}(a) = (a_0,\ldots, a_{d-1})$, where $a_i \in \mathbb{F}_q$. That is, $a$ is a polynomial whose $d$ evaluations over the $2d$-th primitive roots of unity are $(a_0,\ldots, a_{d-1})$.
One may ask, why not embedding $\{a_i\}_{i \in [d]}$ directly as coefficients of $a$? In other words, given a CCS relation over $\mathbb{F}_q$, why does LatticeFold embed $\mathbb{F}_q$ elements into $\mathcal{R}_q$ in NTT form?
For illustrative purposes, take an R1CS relation (R1CS is a subset of CCS): $A \cdot z \circ B \cdot z = C \cdot z$, for $A, B, C \in \mathbb{F}^{m \times n}$, and set $z = (1, \ldots, 1)^T$. Then we have the following equations that are satisfied:
$$\begin{aligned} a_1 \cdot b_1 &= c_1 \\ &\vdots \\ a_d \cdot b_d &= c_d \end{aligned}$$If we pack them as coefficients of elements in $\mathcal{R}_q$, that is, $\text{cf}(a) = (a_0,\ldots, a_{d-1})$, $\text{cf}(b) = (b_0, \ldots, b_{d-1})$, $\text{cf}(c) = (c_0, \ldots, c_{d-1})$, this doesn't guarantee that $a \cdot b = c$. Indeed,
$$ (a_{d-1}X^{d-1} + \ldots + a_1X + a_0) \cdot (b_{d-1}X^{d-1} + \ldots + b_1X + b_0) \neq c_{d-1}X^{d-1} + \ldots + c_1X + c_0. $$For the CCS relation to hold, we need to run an inverse NTT (iNTT) such that $\text{NTT}(a) = (a_0,\ldots, a_{d-1})$, $\text{NTT}(b) = (b_0, \ldots, b_{d-1})$, $\text{NTT}(c) = (c_0, \ldots, c_{d-1})$. So, when $a, b, c$ are evaluated over the primitive roots of unity $\{ \zeta_j \}_{j\in [t]}$ they render:
$$ a(\zeta_j) \cdot b(\zeta_j) = a_j \cdot b_j = c_j = c(\zeta_j). $$It's important to note that if $\{a_i\}_{i \in [d]}$ are of low norm (i.e. $\|a_i\|_\infty < B$ for some bound $B$), this doesn't guarantee that $\|a\|_\infty < B$. That is, iNTT doesn't preserve the norm. Thus LatticeFold needs to commit to an arbitrary element independently of its original size.
On the other hand, an advantage of NTT is that it can batch $d$ separate relations over $\mathbb{F}_q$ altogether into one relation over $\mathcal{R}_q$. Say we have $d$ R1CS relations of the form $\{A_i \cdot z_i \circ B_i \cdot z_i = C_i \cdot z_i\}_{i=1\ldots d}$. We can use NTT to pack it into a single R1CS relation over $\mathcal{R}_q$:
$$ A' \cdot z' \circ B' \cdot z' = C' \cdot z' $$where $\text{NTT}(A') = (A_1, \ldots, A_d)$, $\text{NTT}(B') = (B_1, \ldots, B_d)$, $\text{NTT}(C') = (C_1, \ldots, C_d)$, and $\text{NTT}(z) = (z_1, \ldots, z_d)$.
LatticeFold's commitment scheme
Putting it together, the (simplified) LatticeFold's commitment relation is defined by
$$ \begin{align*} \mathcal{R}^{B}_{\mathrm{cm}} \;:=\; \left\{ (\textsf{pp},\; \mathrm{cm} \in \mathcal{R}_{q}^{\kappa};\; \vec{f} \in \mathcal{R}_{q}^{m}) \;\colon\; \left( \mathrm{cm} = A \vec{f} \;\land\; \left( \hat{f} \circ \left[ \bigcirc_{i=1}^{B-1} (\hat{f} - \hat{i}) \circ (\hat{f} + \hat{i}) \right] = \hat{0} \right) \right) \right\} \end{align*} $$This relation is used to prove the correct opening of the Ajtai commitment. In the R1CS context, we may think of each element in $\vec{f} \in \mathcal{R}_q^m$ as obtained by doing an iNTT over a subset of the $\{a_i, b_i, c_i\}$ in the original R1CS relation. The full-fledged relation for CCS is in Definition 4.2.
In $\mathcal{R}^{B}_{\mathrm{cm}}$, $\hat{f}$ is a vector of polynomials in $\mathcal{R}_q$. The NTT form of each of its elements is the coefficients of the elements $f$ in $\vec{f}$. That is, $\text{cf}(\vec{f}) = \text{NTT}(\hat{f})$. The zero-check $\left( \hat{f} \circ \left[ \bigcirc_{i=1}^{B-1} (\hat{f} - \hat{i}) \circ (\hat{f} + \hat{i}) \right] = \hat{0} \right)$ as a grand-product argument encodes the norm bound $\|\vec{f}\|_\infty$ required by the Ajtai commitment scheme. The reason why LatticeFold uses $\hat{f}$ instead of $\vec{f}$ for this grand-product argument is to apply the sum-check protocol over $\hat{f}$ to reduce the relation $\mathcal{R}_{cm}^B$ to another relation $\mathcal{R}_{eval}^B$,
$$ \mathcal{R}^{B}_{\mathrm{eval}} \;:=\; \left\{ (\textsf{pp},\; \mathbf{x} := (\vec{r}, \hat{\vec{v}}, \mathrm{cm}) \in \mathcal{R}_{q}^{\log m} \times \mathcal{R}_{q} \times \mathcal{R}_{q}^{\kappa};\; \vec{f} \in \mathcal{R}_{q}^{m}) \;\colon\; \left( (\textsf{pp}, \mathrm{cm}; \vec{f}) \in \mathcal{R}^{B}_{\mathrm{cm}} \;\land\; \mathrm{mle}\left[ \hat{f} \right](\vec{r}) = \hat{\vec{v}} \right) \right\} $$and simply check that $\mathrm{mle}\left[ \hat{f} \right](\vec{r}) = \hat{\vec{v}}$.
Neo
Embedding $\mathbb{F}_q$ into $\mathcal{R}_q$
Given the downside of running an iNTT over the elements in $\mathbb{F}_q$ in the CCS relation to run the LatticeFold protocol, Neo provides an answer to the following question:
How can we embed $z \in \mathbb{F}_q^m$ into a low-norm vector $z' \in \mathcal{R}_q^m$ such that $z'$ can be committed directly with Ajtai's commitment scheme while preserving homomorphism?
Neo maps each element $z_i \in \mathbb{F}_q$ to a ring element $z_i' \in \mathcal{R}_q$ by embedding the $b$-ary decomposition of $z_i$ into the coefficients $z_i'$:
$$\begin{align*} \phi \colon \mathbb{F}_q &\to \mathcal{R}_q \\ z_i := \sum_{j=1}^d b^{j-1} z_{i,j} &\mapsto z'_i := \sum_{j=1}^d z_{i,j} X^{j-1} \end{align*}$$This embedding guarantees that $\|z'_i\|_\infty < b$, that is, it has low norm. Unlike the embedding used in LatticeFold, $\phi$ preserves the original CCS constraints. Note that if all $z_i$ are small, then one could embed multiple elements of $\mathbb{F}_q$ into $\mathcal{R}_q$.
For illustrative purposes, take an R1CS relation $A\cdot \vec{z} \circ B\cdot \vec{z} = C\cdot \vec{z}$ as an example, where $\vec{z} = [1,\ldots,1]^T \in \mathbb{F}_q^m$ for $m$ constraints. If $m=1$, a constraint is of the form $(a \cdot z_i) \cdot (b \cdot z_i) = a \cdot b = c = c \cdot z_i$, where $a,b,c \in \mathbb{F}_q$. Let $a = 7$, $b = 9$ and $c = 9 \cdot 7 = 63$. Their binary decomposition is $a = 111$, $b = 1001$ and $c = 111111$, so their embeddings are $a' = X^2 + X + 1$, $b' = X^3 + 1$ and $c' = X^5 + X^4 + X^3 + X^2 + X + 1$. Since $z' = [1,\ldots,1]^T \in \mathcal{R}_q^m$, it is clear to see that
$$\begin{align*} (a' \cdot z') \cdot (b' \cdot z') = a' \cdot b' &= (X^2 + X + 1) \cdot (X^3 + 1) \\ &= X^5 + X^4 + X^3 + X^2 + X + 1 \\ & = c' = c' \cdot z'. \end{align*}$$Thus the original CCS constraint holds after embedding.
Note that this equality holds only when $\deg(a') + \deg(b') < d$, i.e., there is no wrapup after modulo $(X^d+1)$.
From Rings to Matrices
Ajtai's commitments are described over $\mathcal{R}_q$ elements. However, Neo's protocol is described over matrices. We've already shown how to embed $\mathbb{F}_q$ elements into elements in $\mathcal{R}_q$ of low norm. This section shows how to convert elements from $\mathcal{R}_q$ into $\mathbb{F}_q$ as used in Neo.
Coefficient maps
For an element $\mathbf{a}=\sum_{i=1}^{d} a_i X^{i-1}\in\mathcal{R}_q$, the coefficient map $\mathrm{cf} \colon \mathcal{R}_q \to \mathbb{F}_q^d$ is defined by
$$ \mathrm{cf}(\mathbf{a}) := (a_1,\ldots,a_d)^{\mathsf T}\in\mathbb{F}_q^{d}, \qquad \text{and}\qquad \mathrm{cf}_i(\mathbf{a}) := a_i \quad\text{for every } i\in[d]. $$For a vector $\vec{\mathbf{a}} := (\mathbf{a}_1,\ldots,\mathbf{a}_m)^{\mathsf T}\in\mathcal{R}_q^{m}$,
$$ \mathrm{cf}(\vec{\mathbf{a}}) :=\begin{bmatrix} \mathrm{cf}_1(\mathbf{a}_1) & \cdots & \mathrm{cf}_d(\mathbf{a}_1) \\[4pt] \vdots & \ddots & \vdots \\[4pt] \mathrm{cf}_1(\mathbf{a}_m) & \cdots & \mathrm{cf}_d(\mathbf{a}_m) \end{bmatrix} \in\mathbb{F}_q^{m\times d}. $$Decomposition maps
Given a vector of field elements $\vec{z} \in \mathbb{F}^m$, Neo defines a b-ary decomposition mapping
$$\begin{align*} \text{Decomp}_b \colon \mathbb{F}_q^m &\to \mathbb{F}_q^{d \times m} \\ \vec{z} := [z_1, \ldots, z_m] &\mapsto Z := \begin{bmatrix} z_{1,1} & z_{2,1} & \ldots & z_{m, 1} \\ z_{1, 2} & z_{2, 2} & \ldots & z_{m, 2} \\ \vdots & \vdots & \ddots & \vdots \\ z_{1, d} & \ldots & \ldots & z_{m, d} \end{bmatrix} = \left[ \begin{array}{c} Z^{(1)} \\ \hline Z^{(2)} \\ \hline \vdots \\ \hline Z^{(d)} \end{array} \right] \end{align*}$$where
- the matrix $Z \in \mathbb{F}^{d \times m}$ is of low norm, that is, for all $i,j$, $\|z_{i,j}\|_{\infty} < b$,
- each column of $Z$, $[z_{i,1}, \ldots, z_{i, d}] \in \mathbb{F}^d_q$, can be viewed as the coefficients of a ring element $z'_i$ in $\mathcal{R}_q$,
- each row $Z^{(i)} := [z_{1,i}, \ldots , z_{m, i}] \in \mathbb{F}^m_q$ can be viewed as the degree-$i$ coefficients of all elements in $\mathcal{R}_q^m$.
One can easily see that $\vec{z} = \sum_{i = 1}^d b^{i-1}Z^{(i)}$.
Since Ajtai's commitments act on $\mathcal{R}_q$, when we say we apply Ajtai's commitment scheme to commit to a matrix $Z \in \mathbb{F}^{d \times m}$, we refer to the operation $M \cdot \vec{z'}$, where $\vec{z'} \in \mathcal{R}_q^m \leftarrow \text{cf}^{-1}(Z)$ is of low norm and $M \in \mathcal{R}_q^{\kappa \times m}$.
Rotation matrices
How does Neo practically compute these commitments? The idea comes from the observation that the set of rotation matrices
$$\begin{align*} S := \{ \text{rot}(a) \colon a \in \mathcal{R}_q \} \subset \mathbb{F}_q^{d\times d} \end{align*}$$forms a ring and happens to be isomorphic to $\mathcal{R}_q$. Hence, instead of an $\mathcal{R}_q$-module homomorphism (as described in Ajtai), the commitment scheme can be viewed as a S-module homomorphism $L \colon \mathbb{F}_q^{d\times m} \to \mathbb{F}_q^{d\times \kappa}$. That is, for all matrices $Z_1, Z_2 \in \mathbb{F}^{d \times m}$ and $\rho_1, \rho_2 \in S$ that
$$ \rho_1 \cdot \mathsf{Commit}(\mathsf{pp}, Z_1) + \rho_2 \cdot \mathsf{Commit}(\mathsf{pp}, Z_2) = \mathsf{Commit}(\mathsf{pp}, \rho_1 \cdot Z_1 + \rho_2 \cdot Z_2). $$So, what are these rotation matrices?
We define a shift matrix $F\in\mathbb{F}^{d\times d}$ and a rotation matrix $\text{rot}(a)\in\mathbb{F}^{d\times d}$ for an element $a\in \mathcal{R}_q$, as
$$ F \;:=\; \left[ \begin{array}{cccc|c} 0 & 0 & \cdots & 0 & -c_{0}\\\hline 1 & 0 & 0 & \cdots & -c_1\\ 0 & 1 & 0 & \cdots & -c_2\\ \vdots & & \ddots & \ddots & \vdots\\ 0 & 0 & \cdots & 1 & -c_{d-1} \end{array} \right], $$where $c_i$ are the coefficients of the cyclotomic polynomial
$$ \Phi_\eta = X^{d}+c_{d-1}X^{d-1}+c_{d-2}X^{d-2}+\cdots+c_{0}. $$For all $a\in \mathcal{R}_q$, $\mathrm{cf}\!\bigl(X\cdot a\bigr)=F\cdot\mathrm{cf}(a)$. If $\Phi_\eta = X^{d}+1$, $c_0 = 1$ and $c_i = 0$ for all $i$. Let $a = a_{d-1} X^{d-1} + \ldots + a_0$:
$$ F\cdot\mathrm{cf}(a)= \left[ \begin{array}{cccc|c} 0 & 0 & \cdots & 0 & -1\\\hline 1 & 0 & 0 & \cdots & 0\\ 0 & 1 & 0 & \cdots & 0\\ \vdots & & \ddots & \ddots & \vdots\\ 0 & 0 & \cdots & 1 & 0 \end{array} \right] \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{d-1} \end{bmatrix}= \begin{bmatrix} -a_{d-1}\\ a_0\\ \vdots\\ a_{d-2} \end{bmatrix} $$The rotation matrix is defined as:
$$ \text{rot}(a) := [ \text{cf}(a) | F \cdot \text{cf}(a) | \ldots | F^{d-1} \cdot \text{cf}(a)] $$which visually looks like
$$ \text{rot}(a)= \begin{bmatrix} a_{0} & -a_{d-1} & \ldots & -a_{1}\\ a_{1} & a_{0} & \ldots & -a_{2}\\ \vdots& \vdots & \ddots& \vdots\\ a_{d-1}& a_{d-2}& \ldots & a_{0} \end{bmatrix}. $$Hence, for all $a,b\in \mathcal{R}_q$, $\text{rot}(a)\cdot\mathrm{cf}(b)=\mathrm{cf}(ab)$.
A "pay-per-bit" commitment scheme
This last property $\text{rot}(a)\cdot\mathrm{cf}(b)=\mathrm{cf}(a \cdot b)$ (initially proved in Lemma 2.1 of the LatticeFold paper), is crucial to understand how the costs of the Ajtai commitments in Neo scale linearly with the bit-width of the elements of the witness $z$. It shows how to compute the product of two ring elements using the rotation matrix of an element in $\mathcal{R}_q$.
$$\begin{align*} \text{cf}(a\cdot b) = \text{rot}(a) \cdot \text{cf}(b) &= \begin{bmatrix} a_{0} & -a_{d-1} & \ldots & -a_{1}\\ a_{1} & a_{0} & \ldots & -a_{2}\\ \vdots& \vdots & \ddots& \vdots\\ a_{d-1}& a_{d-2}& \ldots & a_{0} \end{bmatrix} \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_d \end{bmatrix} \\ &= \begin{bmatrix} \vec{a'_1} | \vec{a'_2} | \ldots | \vec{a'_d}\end{bmatrix} \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_d \end{bmatrix} \\ &= \sum_{i=1}^d b_i \cdot \vec{a'_i}. \end{align*}$$Recall that a commitment is a matrix multiplication $M \cdot \vec{z'}$, of $\mathcal{R}_q^m$ elements. Now, let $a_i \in \mathcal{R}_q$ be an entry of $M$ and $z'$ an element of the witness vector $\vec{z'}$.
If the embedding $\phi \colon \mathbb{F}_q \to \mathcal{R}_q$ from the original CCS instance uses a binary decomposition of $z'$, that is, if $b = 2$ in the map that takes $z := \sum_{i=1}^d b^{i-1} z_{i} \in \mathbb{F}_q$ to $z' := \sum_{i=1}^d z_{i} X^{i-1} \in \mathcal{R}_q$, then the coefficients $z_i$ are bits, and $\sum_{i=1}^d z_i \cdot a_i$ amounts to just adding the columns which correspond to the $z_i = 1$. Thus, we only need to pay per bit.
Furthermore, computing the columns $\vec{a'_i}$ requires just a rotation of the prior column and adding a constant number of field elements.
Acknowledgments
Thanks to Wyatt Benno, Binyi Chen, Nicolas Mohnblatt and Srinath Setty for their valuable feedback.
- LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems https://eprint.iacr.org/2024/257 ↩︎
- HyperNova: Recursive arguments for customizable constraint systems https://eprint.iacr.org/2023/573.pdf ↩︎
- Constant-Size Commitments to Polynomials and Their Applications https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf ↩︎
- SWIFFT: A Modest Proposal for FFT Hashing https://web.eecs.umich.edu/~cpeikert/pubs/swifft.pdf ↩︎
- Customizable constraint systems for succinct arguments https://eprint.iacr.org/2023/552 ↩︎
- Neo: Lattice-based folding scheme for CCS over
small fields and pay-per-bit commitments https://eprint.iacr.org/2025/294.pdf ↩︎ - LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems https://eprint.iacr.org/2025/247
ZKP researcher at ICME.