Ring commutator commitment scheme

# Ring commutator commitment scheme ## Quaternion algebra Given a field $F$, a quaternion algebra $B := \left(\dfrac{a, b}{F}\right)$ is the $F$-algebra generated by $$ i^2 = a, \quad j^2 = b, \quad ij = -ji, $$ with $a, b \in F^\times$. Setting $k := ij$, we get an $F$-basis $\{1,i,j,k\}$, so $\dim_F B = 4$. It is a non-commutative ring. We may write such an algebra as $$ \left(\dfrac{a, b}{F}\right) := F + iF + jF + kF, $$ and the natural order of an algebra $\left(\dfrac{a, b}{F}\right)$ is defined as $$ \Lambda := \mathcal{O} + i \mathcal{O} + j \mathcal{O} + k \mathcal{O}, $$ where $\mathcal{O} \subset F$ is the ring of integers of $F$. ## Cyclotomic field and cyclotomic ring Take $d \geq 1$ and let $\zeta_d := e^{2\pi i/d}$ be a primitive $d$-th root of unity. Define the cyclotomic field $F := \mathbb{Q}(\zeta_d)$. The ring of integers of $F$ is $\mathcal{O}_F := \mathbb{Z}[\zeta_d]$, which is also known as the _cyclotomic ring_, that is, the ring $\mathbb{Z}[X]/(\Phi_d(x))$ where $\Phi_d$ is the the cyclotomic polynomial (i.e., the minimal polynomial of $\zeta_d$ over $\mathbb{Q}$). The natural order of $B$ is $$ \Lambda = \mathbb{Z}[\zeta_d] + i \mathbb{Z}[\zeta_d] + j \mathbb{Z}[\zeta_d] + k \mathbb{Z}[\zeta_d] $$ with $i^2 = a, j^2 = b, k = ij = -ji$. It is an $\mathcal{O}_F$-lattice of rank $4$, hence a $\mathbb{Z}$-module of rank $4 \varphi(d)$, where $\varphi(d)$ is the Euler's totient function (the number of integers $1\leq k \leq d$ that are coprime to $d$. For $d$ prime, $\varphi(d) = d - 1$. Both the degree of the extension $\mathbb{Q}(\zeta_d) / \mathbb{Q}$, denoted by $[\mathbb{Q}(\zeta_d):\mathbb{Q}]$, and the degree of the cyclotomic polynomial, $\deg \Phi_d(X)$, are equal to $\varphi(d)$. ## Reducing the cyclotomic ring modulo a prime $q$ If $q \nmid d$ and $q \equiv 1 \pmod{d}$, then the order of $q$ modulo $d$ is $1$, so $f=1$. Hence $q$ splits completely and $$ \mathcal{O}_F / q\mathcal{O}_F \cong \mathbb{F}_q^{\,\varphi(d)}. $$ ## Reduction of the natural order $\Lambda$ Now reduce $$ \begin{align*} \Lambda/q\Lambda &= (\mathcal{O}_F + i \mathcal{O}_F + j \mathcal{O}_F + k \mathcal{O}_F)/q \\ &\cong (\mathcal{O}_F / q\mathcal{O}_F) \oplus i(\mathcal{O}_F/q\mathcal{O}_F) \oplus j (\mathcal{O}_F/q\mathcal{O}_F) \oplus k (\mathcal{O}_F/q\mathcal{O}_F) \end{align*} $$ as an $\mathcal{O}_F/q\mathcal{O}_F$-module. If $q$ splits completely in $F$, then $$ \Lambda_q := \Lambda/q\Lambda \cong \prod_{i = 1}^{\varphi(d)} M_2(\mathbb{F}_q) $$  ## Ring commutator The commutator of two elements $a$ and $b$ of a non-commutative ring $R$ is defined as $$ [a,b] := ab - ba. $$ The commutator is a homomorphism when one entry is fixed: $$ \begin{align*} [a, b+c] &=a(b+c) - (b+c)a \\ &= ab + ac - ba - ca \\ &= ab - ba + ac - ca \\ &= [a,b] + [a,c]. \end{align*} $$ If $\rho \in Z(R)$ is a central element of the ring $R$, then $$ \begin{align*} [a, \rho b] &=a\rho b - \rho ba \\ &= \rho a b - \rho ba \\ &= \rho [a,b]. \end{align*} $$ When $R$ is a vector space over a finite field $\mathbb{F}_q$ equipped with a symmetric trace function $\operatorname{Tr}$, we have that $$ \operatorname{Tr}([a,b]) = \operatorname{Tr}(ab - ba) = \operatorname{Tr}(ab) - \operatorname{Tr}(ba) = 0, $$ that is, a commutator defines a map into the space of traceless elements. ## The commutator compression function The function $$ \begin{align*} f_a \colon \mathcal{O}_q^m &\to \mathcal{O}_q \\ x &\mapsto \langle a, x \rangle \end{align*} $$ compresses from a space of size $q^{mN}$ to one of $q^N$, where $N$ is the dimension of the ambient ring $\mathcal{O}_q$ and $\langle a, x \rangle$ is the inner product. A matrix-vector product consists of a bunch of inner products, and Ajtai commitments are basically matrix-vector products. In contrast, the commutator compression function leverages the fact that $\dim_{\mathbb{F}_q} M_2(\mathbb{F}_q) = 4$, while the space of traceless matrices $T_0$ in such rings have $\dim_{\mathbb{F}_q}T_0 = 3$. Intuitively, we only need three $\mathbb{F}_q$ elements to describe an element in $T_0$. Denote $n := \varphi(d)$. Since $\Lambda_q \cong \prod_{i = 1}^{n} M_2(\mathbb{F}_q)$, the function $$ \begin{align*} F_a \colon \Lambda_q^m &\to T_0 \\ x &\mapsto \sum_{i=1}^m [a_i, x_i] \end{align*} $$ compresses from a space of size $q^{4 m n}$ to one of size $q^{3 n / 4}$. Equivalently, since the ambient ring $\Lambda_q$ is $N = 4 n$, $F_a$ compresses from $q^{mN}$ to $q^{3N/4}$. Thus, $F_a$ achieves a greater relative compression by considering the sum of commutators, compared to the inner product. ## A commutator-based variant of SIS (ComSIS) Finding the preimage of $F_a$ is equivalent to an average-case form of inhomogeneous SIS. Similarly, $F_a$ is collision resistent. These considerations motivate us to propose a commutator-based variant of SIS (ComSIS): > Given $a \in \Lambda_q^m$, find $z = (z_1,...,z_m)^T \in \Lambda_q^m$ such that $F_a(z) = \sum_{i=1}^m [a_i, z_i] = 0 \mod q$ and $0 \leq ||z|| \leq \beta$. ## A commitment scheme from ComSIS We now aim to describe a commitment scheme based on ComSIS. A commitment scheme consists of two functions: - Setup $(1^\lambda) \to pp$: - Sample $a, a' \leftarrow U(\Lambda_q^m)$. - Return $a, a'$. - Commit $(pp, \mu$; $r) \to \rho$: - Sample $r \leftarrow D_{\Lambda^m, \sigma}$. - Compute commitment $\rho$: $\rho = F_a(\mu) + F_{a'}(r) = \sum_i ([a_i, \mu_i] + [a'_i, r_i]).$ - Return $\rho$. The commitment function $$ \begin{align*} \mathcal{L} \colon \Lambda_q^m \times \Lambda_q^m &\to T_0 \\ (x, r) &\mapsto F_a(x) + F_{a'}(r) \end{align*} $$ is additively homomorphic. Indeed, given two vectors $\mu, \mu' \in \Lambda_q^m$, $$ \begin{align*} \mathcal{L}(\mu, r) + \mathcal{L}(\mu', r') &= F_a(\mu) + F_{a'}(r) + F_a(\mu') + F_{a'}(r') \\ &= \sum_i [a_i, \mu_i] + \sum_i [a'_i, r_i] + \sum_i [a_i, \mu'_i] + \sum_i[a'_i, r'_i] \\ &= \sum_i ([a_i, \mu_i] + [a_i, \mu'_i]) + \sum_i ([a'_i, r_i] + [a'_i, r'_i]) \\ &= \sum_i ([a_i, \mu_i + \mu'_i]) + \sum_i ([a'_i, r_i + r'_i]) \\ &= F_a(\mu_i + \mu'_i) + F_{a'}(r + r') \\ &= \mathcal{L}(\mu + \mu', r + r'). \end{align*} $$ In particular, the commitment function $\mathcal{L} \colon \Lambda_q^m \times \Lambda_q^m \to T_0$ is a $Z(\Lambda_q)$-module homomorphism, where $Z(\Lambda_q)$ is the center of $\Lambda_q$, which is of size $q^{\varphi(d)}$. For $\rho \in Z(\Lambda_q)$: $$ \begin{align*} \mathcal{L}(z_1 + \rho \cdot z_2, r) = \mathcal{L}(z_1, r) + \rho \cdot \mathcal{L}(z_2, r). \end{align*} $$ When taking random linear combinations of lattice-based commitments, there are two concerns: 1. The random combination of the openings might be larger than the norm-bound required for binding; and 2. for extraction (i.e., knowledge soundness of the folding scheme), we need the differences between challenges to be invertible. For this to hold we need $\rho$ to be an element in the [_pairwise different set_](https://eprint.iacr.org/2019/680.pdf) $G$ so that for any $\rho, \rho' \in G$, $(\rho - \rho')$ is invertible. We denote $H$ the set of elements that are both in $G$ and in $Z(\Lambda_q)$.  ## Applications: Neo's folding scheme ### Motivation Neo is a lattice-based folding scheme for CCS that, unlike prior work, keeps the constraint system over finite fields (instead of packing it over a polynomial ring), which allows the sum-check involved in the folding protocol run over finite fields. This not only reduces the overhead of the folding protocol, but also simplifies the scheme, leaving the dealing over polynomial rings to the polynomial commitment scheme exclusively. In particular, Neo proposes a folding-friendly instantiation of Ajtai's commitments, with "pay-per-bit" commitment costs. We propose a replacement of the Ajtai's commitment scheme with the ring commutator commitment scheme. ### Embedding $\mathbb{F}_q$ into $\Lambda_q$ We can take the embedding described in [Neo](https://eprint.iacr.org/2025/294), which 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*} where each $z'_i \in \mathcal{R}_q$ is of low norm and suitable to be committed with an Ajtai commitment. We also have a natural embedding of a product of $\mathcal{R}_q$ into $\Lambda_q$: $$ \begin{align*} \psi \colon \mathcal{R}_q \times \mathcal{R}_q \times \mathcal{R}_q \times \mathcal{R}_q &\to \Lambda_q \\ (z'_1, z'_2, z'_3, z'_4) &\mapsto z'_1 + i z'_2 + j z'_3 + k z'_4. \end{align*} $$ Thus given an input $\vec{z}:= (z_1, ..., z_m) \in \mathbb{F}_q^m$ for $m := 4k$, we can naturally embed $\vec{z}$ into $\vec{z''} := (z''_1, ..., z''_k) \in \Lambda_q^k$. This fits well with real-world use cases, where the input vector $z$ may contain millions of elements. ### A matrix representation of $\Lambda_q^m$ Recall that given a vector of field elements $\vec{z} \in \mathbb{F}_q^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}, \end{align*} where $\{z_{i,1},...z_{i,d}\}$ are the coefficients of $\phi(z) = z'_i := \sum_{j=1}^{d} z_{i,j} X^{j-1} \in \mathcal{R}_q$. We can think of $Z$ as the vertical concatenation of four matrices of size $\mathbb{F}_q^{\frac{d}{4} \times m}$ so that each partition $\{z_{i, 1}, ..., z_{i, d/4}\}$ is the coefficients of an element in $\mathcal{R}'_q$. \begin{bmatrix} z_{1,1} & z_{2,1} & \ldots & z_{m, 1} \\ \vdots & \vdots & \ddots & \vdots \\ z_{1, d/4} & \ldots & \ldots & z_{m, d/4} \\ \hline \ldots & \ldots & \ldots & \ldots \\ \hline z_{1,3d/4 + 1} & z_{2,3d/4 + 1} & \ldots & z_{m, 3d/4 + 1} \\ \vdots & \vdots & \ddots & \vdots \\ z_{1, d} & \ldots & \ldots & z_{m, d} \\ \end{bmatrix} Note that if $\mathcal{R}_q$ is of low norm, then $\mathcal{R}'_q$ is also of low norm. ### Apples-to-Apples: Setting up the parameters for comparing Ajtai and ABBA For us to compare the size of the commitments of the two commitment schemes in the context of Neo, we fix $N$ such that $N := [\mathcal{R}_q : \mathbb{Z}]$, that is, the degree of the extension of $\mathcal{R}_q$ over $\mathbb{Z}$. We want that $|\mathcal{R}_q|$ = $|\Lambda_q|$. We can then construct $\Lambda_{q} \cong \mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q}$ where $\mathcal{R}'_{q}$ is the polynomial ring derived from splitting the coefficients of $z' \in \mathcal{R}_q$ into four equal parts. So $[\Lambda_q: \mathbb{Z}] = [\mathcal{R}_{q} : \mathbb{Z}] = 4 \cdot [\mathcal{R}'_{q} : \mathbb{Z}]$. We denote the splitting of $\mathcal{R}_q$ into $\mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q}$ as $\pi$. That is, \begin{align*} \pi \colon \mathcal{R}_q &\to \mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q} \\ \sum_{j=1}^{d} z_{i,j} X^{j-1} &\mapsto (\sum_{j=1}^{d/4} z_{i,j} X^{j-1}, \sum_{j=1}^{d/4} z_{i,j + d/4} X^{j-1}, \sum_{j=1}^{d/4} z_{i,j + d/2} X^{j-1}, \sum_{j=1}^{d/4} z_{i,j + 3d/4} X^{j-1}) \end{align*} ### Relations Neo provides an analogue of the CCS relation, updated to ensure that committed elements are of low norm (which is enforced by decomposition). We slightly modify the original relations in Neo by replacing Ajtai commitments with ABBA commitments. The **Matrix Constraint System (MCS)** relation is defined as: $$ \operatorname{MCS}(b,\mathcal{L}) := \left\{ \begin{array}{l} \left(s;\; (c \in \mathcal{C},\; x \in \mathbb{F}_q^{m_{\mathrm{in}}}); \; w \in \mathbb{F}_q^{\,m-m_{\mathrm{in}}}\right) \end{array} \ \middle|\ \begin{array}{l} \text{for } z := x \,\|\, w \\[2pt] Z := (\psi \circ \pi \circ \phi) (z)\\[2pt] c = \mathcal{L}(Z),\\[2pt] f\!\left(\widetilde{M}_1 z, \ldots, \widetilde{M}_t z\right) \in ZS_n \end{array} \right\}. $$  To compute $c$, 1. we start by embedding each element $z \in \mathbb{F}_q^m$ into $\mathcal{R}_q^m$ as described in $\phi$, which renders an element of low norm. 2. We apply $\pi$ to obtain four elements in $\mathcal{R}'_{q}$ for each $\mathcal{R}_{q}$, also of low norm or, equivalently, an element in $\mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q}$. 3. We embed each element in $\mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q} \times \mathcal{R}'_{q}$ into $\Lambda_q$ by applying $\psi$. We have now $m$ copies of $\Lambda_q$, that is, $\Lambda_q^m$. 4. We apply $\mathcal{L}$ to this result in $\Lambda_q^m$ to obtain $c \in T_0^k$.  While Ajtai commitments take: $$ f_M \colon x \in \mathcal{R}_q^m \mapsto \begin{bmatrix} \langle M_1, x\rangle \\ \ldots \\ \langle M_k, x \rangle \end{bmatrix} \in \mathcal{R}_q^k, $$ ABBA commitments take: $$ F_M \colon x \in \Lambda_q^m \mapsto \begin{bmatrix} \sum_i[M_1, x_i] \\ \ldots \\ \sum_i[M_k, x_i] \end{bmatrix} \in T_0^k, $$ which is of size ... **!!! The result is of size... (TODO)** ### Commutator folding scheme for CCS Given two instances $\vec{u}, \vec{v} \in \mathbb{F}_q^m$ of two different CCS relations, their $\Lambda_q$ embeddings $\vec{u''}, \vec{v''} \in \Lambda_q^k$ satisfy, for $\rho \in H$, $$ \begin{align*} \mathcal{L}(\vec{u''} + \rho \cdot \vec{v''}, r) = \mathcal{L}(\vec{u''}, r) + \rho \cdot \mathcal{L}(\vec{v''}, r), \end{align*} $$ and the element $\vec{u''} + \rho \cdot \vec{v''}$ is of small norm.