4 Various Papers 4.12 Practical Product Proof from Lattice Commitments 4.14 Lattice Proofs for Exact Euclidean Norm Bounds and Quadratic Relations

4.13 Practical Exact Proofs from Lattices

We now apply the product proof in [ALS20] from the computationally indistinguishable masked opening to [BLS19]. A baseline protocol for the exact proof follows:

•

The prover sends out $\overline{w}\leftarrow A\hat{\mathbf{y}}$ and $\overline{\mathbf{w}}\leftarrow\mathbf{B}_{0}\overline{\mathbf{y}}$ , where $\mathbf{y}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}R_{q}$ and $\overline{\mathbf{y}}\leftarrow D_{\sigma}^{Nd}$ , and samples $\overline{\mathbf{r}}\leftarrow\chi^{Nd}$ to commit

$\begin{bmatrix}\overline{\mathbf{t}}_{0}\\ \mathbf{t}_{1}\\ \mathbf{t}_{2}\end{bmatrix}\leftarrow\begin{bmatrix}\mathbf{B}_{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\\ \overline{\mathbf{b}}_{2}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{y}\\ \mathbf{s}\end{bmatrix}.$
•

The verifier challenges by sending $c\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{Z}_{q}$ .
•
The prover replies with $\mathbf{z}\leftarrow c\cdot\mathbf{s}+\mathbf{y}$ , and starts $\Pi_{\mathsf{lin}}$ and the shortness check in [ALS20] by:
- –
  
  The prover derives $\overline{\mathbf{b}}_{f_{0}}:=\overline{\mathbf{b}}_{1}+c\cdot\overline{% \mathbf{b}}_{2}$ , replies $\mathbf{w}^{\prime}\leftarrow\langle\overline{\mathbf{b}}_{f_{0}},\overline{% \mathbf{y}}\rangle$ , then it commits
  
  $\begin{bmatrix}\mathbf{t}_{3}\\ \mathbf{t}_{4}\end{bmatrix}\leftarrow\begin{bmatrix}\overline{\mathbf{b}}_{3}^% {\mathsf{T}}\\ \overline{\mathbf{b}}_{4}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\langle\overline{\mathbf{b}}_{4},\overline{\mathbf{y}}\rangle-3% \langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle^{2}\mathbf{s}\\ \langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle\left(3\mathbf{s}% ^{2}-\boldsymbol{1}\right)\end{bmatrix},$ (4.32)
  
  and replies $\mathbf{t}_{3},\mathbf{t}_{4}$ , and the claim $\mathbf{v}\leftarrow\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}% \rangle^{3}+\langle\overline{\mathbf{b}}_{3},\overline{\mathbf{y}}\rangle$ .
- –
  
  The verifier samples $\mathbf{c}$ over the $\{-1,0,1\}$ challenge set $\mathcal{C}$ , with each coefficient has $P(\pm 1)=1/4$ , $P(0)=1/2$ .
- –
  
  The prover runs rejection sampling, and outputs $\overline{\mathbf{z}}^{\prime}\leftarrow\overline{\mathbf{y}}+\mathbf{c}\cdot% \overline{\mathbf{r}}$ .
•

The verifier checks by ensuring $\overline{\mathbf{z}}^{\prime}$ being short, $A\hat{\mathbf{z}}=\overline{w}+c\cdot\overline{u}$ ,

$\begin{bmatrix}\overline{\mathbf{w}}\\ \mathbf{w}^{\prime}\end{bmatrix}+\mathbf{c}\cdot\begin{bmatrix}\overline{% \mathbf{t}}_{0}\\ \mathbf{t}_{1}+c\cdot\mathbf{t}_{2}\end{bmatrix}=\begin{bmatrix}\mathbf{B}_{0}% \\ \overline{\mathbf{b}}_{f_{0}}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}^{% \prime}+\mathbf{c}\cdot\begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{z}\end{bmatrix},$

and the shortness check from the product proof in [ALS20] by

$\mathbf{f}_{2}\left(\mathbf{f}_{2}-\mathbf{c}\right)\left(\mathbf{f}_{2}+% \mathbf{c}\right)+\mathbf{f}_{3}+\mathbf{c}\mathbf{f}_{4}=\mathbf{v},$ (4.33)

where $\mathbf{f}_{i}=\langle\overline{\mathbf{b}}_{i},\overline{\mathbf{z}}^{\prime}% \rangle-\mathbf{c}\mathbf{t}_{i}$ for $i\in[2,4]$ .

The 2 garbage terms defined in eq. 4.32 derive from the degree-3 shortness check over $\{-1,0,1\}$ from the product proof over the masked opening, similar to the one in [ALS20]:

	$\displaystyle\mathbf{f}_{2}\left(\mathbf{f}_{2}-\mathbf{c}\right)\left(\mathbf% {f}_{2}+\mathbf{c}\right)$	$\displaystyle=\left(\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}% \rangle-\mathbf{c}\mathbf{s}\right)\left(\langle\overline{\mathbf{b}}_{2},% \overline{\mathbf{y}}\rangle-\mathbf{c}\left(\mathbf{s}-\boldsymbol{1}\right)% \right)\left(\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle-% \mathbf{c}\left(\mathbf{s}+\boldsymbol{1}\right)\right)$
		$\displaystyle=\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle^{3% }-3\mathbf{s}\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle^{2}% \mathbf{c}+\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle\left(% 3\mathbf{s}^{2}-\boldsymbol{1}\right)\mathbf{c}^{2}-\left(\mathbf{s}^{3}-% \mathbf{s}\right)\mathbf{c}^{3}.$

Hence, when $\mathbf{f}_{2}$ is the masked opening for $\mathbf{s}$ , we let the garbage terms defined in eq. 4.32, such that

	$\displaystyle\mathbf{f}_{4}$	$\displaystyle=\langle\overline{\mathbf{b}}_{4},\overline{\mathbf{y}}\rangle-% \mathbf{c}\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle\left(3% \mathbf{s}^{2}-\boldsymbol{1}\right),$
	$\displaystyle\mathbf{f}_{3}$	$\displaystyle=\langle\overline{\mathbf{b}}_{3},\overline{\mathbf{y}}\rangle-% \mathbf{c}\left(\langle\overline{\mathbf{b}}_{4},\overline{\mathbf{y}}\rangle-% 3\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle^{2}\mathbf{s}% \right),$

so $\mathbf{f}_{3}$ can cancel out the computationally indistinguishable masking $\langle\overline{\mathbf{b}}_{4},\overline{\mathbf{y}}\rangle$ in $\mathbf{f}_{4}$ , and the claim $\mathbf{v}$ is

\mathbf{f}_{2}\left(\mathbf{f}_{2}-\mathbf{c}\right)\left(\mathbf{f}_{2}+% \mathbf{c}\right)+\mathbf{f}_{3}+\mathbf{c}\mathbf{f}_{4}=\langle\overline{% \mathbf{b}}_{2},\overline{\mathbf{y}}\rangle^{3}+\langle\overline{\mathbf{b}}_% {3},\overline{\mathbf{y}}\rangle-\left(\mathbf{s}^{3}-\mathbf{s}\right)\mathbf% {c}^{3}=\mathbf{v}-\left(\mathbf{s}^{3}-\mathbf{s}\right)\mathbf{c}^{3},

where a satisfying $\mathbf{s}$ should be vanishing in $\mathbf{s}^{3}-\mathbf{s}$ .

The current baseline protocol deviates from [BLS19], as $c$ was needed for both the random linear combination to embed $\mathbf{s}$ to $\mathbf{z}$ (later proved by the linear relation proof), and the shortness check from the product proof, now $c$ only serves the first purpose.

Now we move forward and amplify the soundness for the baseline protocol via automorphism repetition, such that the BDLOP commits to $k$ uniform maskings, 1 message, and 2 garbage terms for shortness check. The masked openings for the garbage terms, and the combined claim, are formed as

\begin{split}\mathbf{f}_{k+3}&=\langle\overline{\mathbf{b}}_{k+3},\overline{% \mathbf{y}}_{1}\rangle-\mathbf{c}\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j+1}% \sigma^{-j}\left(\langle\overline{\mathbf{b}}_{k+1},\overline{\mathbf{y}}_{j+1% }\rangle\left(3\mathbf{s}^{2}-\boldsymbol{1}\right)\right)=\langle\overline{% \mathbf{b}}_{k+3},\overline{\mathbf{y}}_{1}\rangle-\mathbf{c}\mathbf{m}_{k+3},% \\ \mathbf{f}_{k+2}&=\langle\overline{\mathbf{b}}_{k+2},\overline{\mathbf{y}}_{1}% \rangle-\mathbf{c}\left(\langle\overline{\mathbf{b}}_{k+3},\overline{\mathbf{y% }}_{1}\rangle-3\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j+1}\sigma^{-j}\left(% \langle\overline{\mathbf{b}}_{k+1},\overline{\mathbf{y}}_{j+1}\rangle^{2}% \mathbf{s}\right)\right)=\langle\overline{\mathbf{b}}_{k+2},\overline{\mathbf{% y}}_{1}\rangle-\mathbf{c}\mathbf{m}_{k+2},\\ \mathbf{v}&=\langle\overline{\mathbf{b}}_{k+2},\overline{\mathbf{y}}_{1}% \rangle+\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j+1}\sigma^{-j}\left(\langle% \overline{\mathbf{b}}_{k+1},\overline{\mathbf{y}}_{j+1}\rangle^{3}\right),\end% {split}

(4.34)

such that the random linear combination yields the statement and the invariant for combined claim

\begin{split}\boldsymbol{0}&=\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j+1}\sigma% ^{-j}\left(\mathbf{s}^{3}-\mathbf{s}\right),\\ \mathbf{v}&=\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j+1}\sigma^{-j}\left(% \mathbf{f}_{k+1,j+1}\left(\mathbf{f}_{k+1,j+1}-\sigma^{j}\left(\mathbf{c}% \right)\right)\left(\mathbf{f}_{k+1,j+1}+\sigma^{j}\left(\mathbf{c}\right)% \right)\right)+\mathbf{f}_{k+2}+\mathbf{c}\mathbf{f}_{k+3}.\end{split}

(4.35)

The amplified baseline protocol follows:

•

The prover sends out $\overline{w}_{i}\leftarrow A\hat{\mathbf{y}}_{i}$ and $\overline{\mathbf{w}}_{i}\leftarrow\mathbf{B}_{0}\overline{\mathbf{y}}_{i}$ , where $\mathbf{y}_{i}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}R_{q}$ and $\overline{\mathbf{y}}_{i}\leftarrow D_{\sigma}^{Nd}$ , and samples $\overline{\mathbf{r}}\leftarrow\chi^{Nd}$ to commit

$\begin{bmatrix}\overline{\mathbf{t}}_{0}\\ \mathbf{t}_{1}\\ \vdots\\ \mathbf{t}_{k}\\ \mathbf{t}_{k+1}\end{bmatrix}\leftarrow\begin{bmatrix}\mathbf{B}_{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\\ \vdots\\ \overline{\mathbf{b}}_{k}^{\mathsf{T}}\\ \overline{\mathbf{b}}_{k+1}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{y}_{1}\\ \vdots\\ \mathbf{y}_{k}\\ \mathbf{s}\end{bmatrix}.$
•

The verifier challenges by sending $c_{1},\ldots,c_{k}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{Z}_% {q}$ and $\boldsymbol{\alpha}_{1},\ldots,\boldsymbol{\alpha}_{k}\stackrel{{\scriptstyle% \textsc{r}}}{{\leftarrow}}R_{q}$ .
•
The prover replies with $\mathbf{z}_{i}\leftarrow c_{i}\cdot\mathbf{s}+\mathbf{y}_{i}$ for $i\in[1,k]$ , and starts $\Pi_{\mathsf{lin}}$ and the shortness check in [ALS20] by:
- –
  
  The prover derives $\overline{\mathbf{b}}_{f_{i}}:=\overline{\mathbf{b}}_{i}+c_{i}\cdot\overline{% \mathbf{b}}_{k+1}$ , replies $\mathbf{w}_{i}^{\prime}\leftarrow\langle\overline{\mathbf{b}}_{f_{i}},% \overline{\mathbf{y}}_{i}\rangle$ , then it commits
  
  $\begin{bmatrix}\mathbf{t}_{k+2}\\ \mathbf{t}_{k+3}\end{bmatrix}\leftarrow\begin{bmatrix}\overline{\mathbf{b}}_{k% +2}^{\mathsf{T}}\\ \overline{\mathbf{b}}_{k+3}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\mathbf{m}_{k+2}\\ \mathbf{m}_{k+3}\end{bmatrix},$
  
  and replies with $\mathbf{t}_{k+2},\mathbf{t}_{k+3}$ , and the claim $\mathbf{v}$ in eq. 4.34,
- –
  
  The verifier samples $\mathbf{c}$ over the $\{-1,0,1\}$ challenge set $\mathcal{C}$ , with each coefficient has $P(\pm 1)=1/4$ , $P(0)=1/2$ .
- –
  
  The prover runs rejection sampling, and outputs $\overline{\mathbf{z}}_{i}^{\prime}\leftarrow\overline{\mathbf{y}}_{i}+\sigma^{% i-1}\left(\mathbf{c}\right)\cdot\overline{\mathbf{r}}$ for $i\in[1,k]$ .
•

The verifier checks by ensuring $\overline{\mathbf{z}}_{i}^{\prime}$ being short, $A\hat{\mathbf{z}}_{i}=\overline{w}_{i}+c_{i}\cdot\overline{u}$ for $i\in[1,k]$ ,

$\begin{bmatrix}\overline{\mathbf{w}}_{i}\\ \mathbf{w}_{i}^{\prime}\end{bmatrix}+\sigma^{i-1}\left(\mathbf{c}\right)\cdot% \begin{bmatrix}\overline{\mathbf{t}}_{0}\\ \mathbf{t}_{i}+c_{i}\cdot\mathbf{t}_{k+1}\end{bmatrix}=\begin{bmatrix}\mathbf{% B}_{0}\\ \overline{\mathbf{b}}_{f_{i}}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}_{% i}^{\prime}+\sigma^{i-1}\left(\mathbf{c}\right)\cdot\begin{bmatrix}\overline{% \boldsymbol{0}}\\ \mathbf{z}_{i}\end{bmatrix},$

and the shortness check from the product proof in [ALS20] by checking the second equality eq. 4.35, where

$\mathbf{f}_{k+1,j+1}=\langle\overline{\mathbf{b}}_{k+1},\overline{\mathbf{z}}_% {j+1}^{\prime}\rangle-\sigma^{j}\left(\mathbf{c}\right)\mathbf{t}_{k+1},$

for $j\in[0,k-1]$ , and $\mathbf{f}_{j}=\langle\overline{\mathbf{b}}_{j},\overline{\mathbf{z}}_{1}^{% \prime}\rangle-\mathbf{c}\mathbf{t}_{j}$ for $j\in\{k+2,k+3\}$ .

But now the baseline protocol augmented with automorphism repetition is more like the prior attempt to amplify soundness for product proof with automorphism repetition. The shortness proof itself needs 2 garbage terms, while the linearity test for each repetition needs $k$ separate masking terms. A question arises that how can BDLOP commits to only a constant number of messages, while we can still amplify the soundness.

Linear Relation Testing via NTT Averaging.

We consider an interactive protocol testing the matrix multiplication statement $A\hat{\mathbf{s}}=\overline{u}$ without $\mathbf{y}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}R_{q}$ : Consider a linear prover, which is bound to a witness chosen before the challenge, and must return the verifier-specified linear evaluation of the witness, then

•

The verifier challenges by $\overline{\gamma}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{Z}_{% q}^{d}$ .
•

The prover replies with $z\leftarrow\overline{\gamma}^{\mathsf{T}}A\hat{\mathbf{s}}$ .
•

The verifier checks $z=\langle\overline{\gamma},\overline{u}\rangle$ .

By Schwartz-Zippel, if $A\hat{\mathbf{s}}-\overline{u}\neq\overline{0}$ , over the randomness of $\overline{\gamma}$ , the probability of $\overline{\gamma}^{\mathsf{T}}\left(A\hat{\mathbf{s}}-\overline{u}\right)=0$ is $q^{-1}$ .

Put it in the polynomial ring computation over the NTT terms, we first consider the lemma in [ENS20].

Lemma 4.13.1 (NTT Averaging Lemma).

Let $R_{q}$ be defined as eq. 4.14, $\mathbf{f}\in R_{q}$ , and $\hat{\mathbf{f}}_{i}=\mathbf{f}\mod\left(X^{d/\ell}-\xi^{i}\right)$ for $i\in\mathbb{Z}^{\ast}_{2\ell}$ , then when we lift $\hat{\mathbf{f}}_{i}$ to $R_{q}$ , we have

\frac{1}{\ell}\sum_{i\in\mathbb{Z}^{\ast}_{2\ell}}\hat{\mathbf{f}}_{i}=\sum_{j% \in[0,d/\ell-1]}f_{j}X^{j}.

Proof.

Recall the eq. 4.17, then noticing

\sum_{i\in[0,\ell-1]}\xi^{(2i+1)v}=\xi^{v}\frac{\xi^{2\ell v}-1}{\xi^{2v}-1}=0

for any $v\in[1,\ell-1]$ , then all the $\xi^{j}$ in eq. 4.17 with degree $j>0$ are filtered out in the averaging summation of $\hat{\mathbf{f}}_{i}$ , while the constant coefficients $\{f_{i}\}_{i\in[0,d/\ell-1]}$ are scaled up by $\ell$ . ∎

Consider $\mathsf{NTT}^{-1}(\overline{\gamma}^{\mathsf{T}}A)\in R_{q}$ , then by lemma 4.13.1, $d^{-1}\langle\overline{\gamma}^{\mathsf{T}}A,\hat{\mathbf{s}}\rangle$ is in the constant coefficient of $\mathsf{NTT}^{-1}(\overline{\gamma}^{\mathsf{T}}A)\cdot\mathbf{s}\in R_{q}$ .

•

The prover sends out $\overline{\mathbf{w}}\leftarrow\mathbf{B}_{0}\overline{\mathbf{y}}$ , where $\overline{\mathbf{y}}\leftarrow D_{\sigma}^{Nd}$ , samples $\mathbf{g}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{R_{q}:g_{0}=0\}$ and $\overline{\mathbf{r}}\leftarrow\chi^{Nd}$ , to commit

$\begin{bmatrix}\overline{\mathbf{t}}_{0}\\ \mathbf{t}_{1}\\ \mathbf{t}_{2}\end{bmatrix}\leftarrow\begin{bmatrix}\mathbf{B}_{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\\ \overline{\mathbf{b}}_{2}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{g}\\ \mathbf{s}\end{bmatrix}.$
•

The verifier challenges by sending $\overline{\gamma}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{Z}_{% q}^{d}$ .
•
The prover replies with $\mathbf{z}\leftarrow\mathsf{NTT}^{-1}(d\overline{\gamma}^{\mathsf{T}}A)\cdot% \mathbf{s}+\mathbf{g}$ , and starts $\Pi_{\mathsf{lin}}$ and the shortness check in [ALS20] by:
- –
  
  The prover derives $\overline{\mathbf{b}}_{f_{0}}:=\overline{\mathbf{b}}_{1}+\mathsf{NTT}^{-1}(d% \overline{\gamma}^{\mathsf{T}}A)\cdot\overline{\mathbf{b}}_{2}$ , replies $\mathbf{w}^{\prime}\leftarrow\langle\overline{\mathbf{b}}_{f_{0}},\overline{% \mathbf{y}}\rangle$ , then it commits
  
  $\begin{bmatrix}\mathbf{t}_{3}\\ \mathbf{t}_{4}\end{bmatrix}\leftarrow\begin{bmatrix}\overline{\mathbf{b}}_{3}^% {\mathsf{T}}\\ \overline{\mathbf{b}}_{4}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\langle\overline{\mathbf{b}}_{4},\overline{\mathbf{y}}\rangle-3% \langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle^{2}\mathbf{s}\\ \langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}\rangle\left(3\mathbf{s}% ^{2}-\boldsymbol{1}\right)\end{bmatrix},$
  
  and replies $\mathbf{t}_{3},\mathbf{t}_{4}$ , and the claim $\mathbf{v}\leftarrow\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}% \rangle^{3}+\langle\overline{\mathbf{b}}_{3},\overline{\mathbf{y}}\rangle$ .
- –
  
  The verifier samples $\mathbf{c}$ over the $\{-1,0,1\}$ challenge set $\mathcal{C}$ , with each coefficient has $P(\pm 1)=1/4$ , $P(0)=1/2$ .
- –
  
  The prover runs rejection sampling, and outputs $\overline{\mathbf{z}}^{\prime}\leftarrow\overline{\mathbf{y}}+\mathbf{c}\cdot% \overline{\mathbf{r}}$ .
•

The verifier checks by ensuring $\overline{\mathbf{z}}^{\prime}$ being short, $z_{0}=\langle\overline{\gamma},\overline{u}\rangle$ ,

$\begin{bmatrix}\overline{\mathbf{w}}\\ \mathbf{w}^{\prime}\end{bmatrix}+\mathbf{c}\cdot\begin{bmatrix}\overline{% \mathbf{t}}_{0}\\ \mathbf{t}_{1}+\mathsf{NTT}^{-1}(d\overline{\gamma}^{\mathsf{T}}A)\cdot\mathbf% {t}_{2}\end{bmatrix}=\begin{bmatrix}\mathbf{B}_{0}\\ \overline{\mathbf{b}}_{f_{0}}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}^{% \prime}+\mathbf{c}\cdot\begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{z}\end{bmatrix},$

and the shortness check from the product proof in [ALS20] by eq. 4.33.

Coefficient Filtering via Automorphisms.

The prior construction from NTT averaging suffices as a single repetition, but for soundness amplification by automorphism repetition, the masking term over $\{R_{q}:g_{0}=0\}$ makes it admissible for only a single repetition.

We now want a way to filter out coefficients over $R_{q}$ via linear operations and automorphisms, or otherwise the new linearity test is no better than the [BLS19] one.

We start by an observation that can filter out all the odd powered coefficients. Since

\sigma_{d+1}(X)=X^{d+1}\equiv-X\mod(X^{d}+1),

then

\mathbf{f}+\sigma_{d+1}(\mathbf{f})=2\left(f_{0}+f_{2}X^{2}+\cdots+f_{d-2}X^{d% -2}\right).

Then, in $\log k$ rounds, the automorphisms $\sigma_{d+1},\sigma_{d/2+1},\ldots,\sigma_{2d/k+1}$ can yield

k\left(f_{0}+f_{k}X^{k}+\cdots+f_{d-k}X^{d-k}\right).

Moreover, after $r$ round for $r\in[1,\log_{2}k]$ , all the automorphisms used are indexed by $\{\sigma_{i\cdot 2d/2^{r}+1}\}_{i\in[0,2^{r}-1]}$ .

Lemma 4.13.2 (Automorphism Filtering Lemma).

For $k\leq d$ and $k\mid d$ , then for any $\mathbf{f}\in R_{q}$ ,

F_{k}(\mathbf{f})=\sum_{i\in[0,k-1]}\sigma_{i\cdot 2d/k+1}\left(\mathbf{f}% \right)=k\left(f_{0}+f_{k}X^{k}+\cdots+f_{d-k}X^{d-k}\right).

Moreover, when $k<d$ ,

F_{k}(\mathbf{f})=\sum_{i\in[0,k-1]}\sigma^{i}_{2d/k+1}\left(\mathbf{f}\right).

(4.36)

Now with lemma 4.13.2, each repetition can be mapped to coefficients of degree in $i\in[0,k-1]$ , by multiplying terms $X^{i}$ , then the masking term can be relaxed to $\mathbf{g}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{R_{q}:g_{i}=0,i% \in[0,k-1]\}$ , the responses masked by $\mathbf{g}$ is,

\mathbf{z}\leftarrow\mathbf{g}+\sum_{i\in[0,k-1]}k^{-1}X^{i}F_{k}\left(\mathsf% {NTT}^{-1}\left(d\overline{\gamma}_{i}^{\mathsf{T}}A\right)\cdot\mathbf{s}% \right),

(4.37)

which can be derived from the commitment

\mathbf{t}=\mathbf{t}_{1}+\sum_{i\in[0,k-1]}k^{-1}X^{i}F_{k}\left(\mathsf{NTT}% ^{-1}\left(d\overline{\gamma}_{i}^{\mathsf{T}}A\right)\cdot\mathbf{t}_{2}% \right)=\langle\overline{\mathbf{b}}_{1},\overline{\mathbf{r}}\rangle+\sum_{i% \in[0,k-1]}k^{-1}X^{i}F_{k}\left(\mathsf{NTT}^{-1}\left(d\overline{\gamma}_{i}% ^{\mathsf{T}}A\right)\cdot\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{r% }}\rangle\right)+\mathbf{z},

(4.38)

where $\mathbf{t}_{1}$ commits to $\mathbf{g}$ , and $\mathbf{t}_{2}$ commits to $\mathbf{s}$ .

Yet, there are automorphism terms in eq. 4.38, and the prior vanilla $\Pi_{\mathsf{lin}}$ no longer suffices. We start by stepping back and thinking up a way to prove linear relation over 2 BDLOP commitments from different commitment keys (assuming they are of same size). Supposing they commit to $\mathbf{m}_{0}$ and $\mathbf{m}_{1}$ , by sampling $\overline{\mathbf{r}}_{0},\overline{\mathbf{r}}_{1}\leftarrow\chi^{Nd}$ , and

\begin{bmatrix}\overline{\mathbf{t}}_{0}\\ \mathbf{t}_{1}\end{bmatrix}\leftarrow\begin{bmatrix}\mathbf{B}_{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}_{0}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{m}_{0}\end{bmatrix},\quad\begin{bmatrix}\overline{\mathbf{t}}_{2}\\ \mathbf{t}_{3}\end{bmatrix}\leftarrow\begin{bmatrix}\mathbf{B}_{2}\\ \overline{\mathbf{b}}_{3}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}_{1}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{m}_{1}\end{bmatrix},

and $\mathbf{m}_{2}=\mathbf{m}_{0}+\mathbf{m}_{1}$ is the public statement. The protocol works as follows:

•

The prover samples $\overline{\mathbf{y}}_{0},\overline{\mathbf{y}}_{1}\leftarrow D_{\sigma}^{Nd}$ , and outputs $\overline{\mathbf{w}}_{0}\leftarrow\mathbf{B}_{0}\overline{\mathbf{y}}_{0}$ , $\overline{\mathbf{w}}_{1}\leftarrow\mathbf{B}_{2}\overline{\mathbf{y}}_{1}$ , and $\mathbf{w}_{2}\leftarrow\langle\overline{\mathbf{b}}_{1},\overline{\mathbf{y}}% _{0}\rangle+\langle\overline{\mathbf{b}}_{3},\overline{\mathbf{y}}_{1}\rangle$ .
•

The verifier challenges with $\mathbf{c}$ over the challenge set $\mathcal{C}$ , where each coefficient has $P(\pm 1)=1/4$ , $P(0)=1/2$ .
•

The prover runs rejection sampling, and replies $\overline{\mathbf{z}}_{0}^{\prime}\leftarrow\overline{\mathbf{y}}_{0}+\mathbf{% c}\cdot\overline{\mathbf{r}}_{0}$ and $\overline{\mathbf{z}}_{1}^{\prime}\leftarrow\overline{\mathbf{y}}_{1}+\mathbf{% c}\cdot\overline{\mathbf{r}}_{1}$ .
•

The verifier checks $\overline{\mathbf{z}}_{0}^{\prime}$ and $\overline{\mathbf{z}}_{1}^{\prime}$ are short, and

$\begin{bmatrix}\mathbf{B}_{0}\\ \boldsymbol{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}_{0}^{% \prime}+\begin{bmatrix}\boldsymbol{0}\\ \mathbf{B}_{2}\\ \overline{\mathbf{b}}_{3}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}_{1}^{% \prime}+\mathbf{c}\cdot\begin{bmatrix}\overline{\boldsymbol{0}}\\ \overline{\boldsymbol{0}}\\ \mathbf{m}_{2}\end{bmatrix}=\begin{bmatrix}\overline{\mathbf{w}}_{0}\\ \overline{\mathbf{w}}_{1}\\ \mathbf{w}_{2}\end{bmatrix}+\mathbf{c}\cdot\begin{bmatrix}\overline{\mathbf{t}% }_{0}\\ \overline{\mathbf{t}}_{2}\\ \mathbf{t}_{1}+\mathbf{t}_{3}\end{bmatrix}$

The soundness is at most $p$ by eq. 4.18. Automorphism repetition can be applied to have soundness to at most $p^{k}$ .

With this protocol, we can actually prove the public statement of automorphism filtering $F_{k}(\mathbf{s})$ for committed $\mathbf{s}$ . The intuition was to view $\sigma(\mathbf{B}_{0})$ and $\sigma(\overline{\mathbf{b}}_{1})$ as different commitment keys, where $\sigma=\sigma_{2d/k+1}$ for some $k<d$ and $k|d$ , and the commitment is formed from $\overline{\mathbf{r}}\leftarrow\chi^{Nd}$ by

\begin{bmatrix}\overline{\mathbf{t}}_{0}\\ \mathbf{t}_{1}\end{bmatrix}=\begin{bmatrix}\mathbf{B}_{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{s}\end{bmatrix}.

•

The prover samples $\overline{\mathbf{y}}_{i}\leftarrow D_{\sigma}^{Nd}$ , outputs $\overline{\mathbf{w}}_{i}\leftarrow\mathbf{B}_{0}\overline{\mathbf{y}}_{i}$ for $i\in[0,k-1]$ , and

$\mathbf{w}_{k}\leftarrow\sum_{i\in[0,k-1]}\sigma^{-i}\left(\langle\overline{% \mathbf{b}}_{1},\overline{\mathbf{y}}_{i}\rangle\right).$ (4.39)
•

The verifier challenges with $\mathbf{c}$ over the challenge set $\mathcal{C}$ , where each coefficient has $P(\pm 1)=1/4$ , $P(0)=1/2$ .
•

The prover runs rejection sampling, and replies $\overline{\mathbf{z}}_{i}^{\prime}\leftarrow\overline{\mathbf{y}}_{i}+\sigma^{% i}(\mathbf{c})\cdot\overline{\mathbf{r}}$ for $i\in[0,k-1]$ .

•

The verifier checks $\overline{\mathbf{z}}_{i}^{\prime}$ are short for $i\in[0,k-1]$ , and

\begin{bmatrix}\mathbf{B}_{0}\\ \boldsymbol{0}\\ \vdots\\ \boldsymbol{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}_{0}^{% \prime}+\begin{bmatrix}\boldsymbol{0}\\ \sigma^{-1}(\mathbf{B}_{0})\\ \vdots\\ \boldsymbol{0}\\ \sigma^{-1}(\overline{\mathbf{b}}_{1}^{\mathsf{T}})\end{bmatrix}\sigma^{-1}(% \overline{\mathbf{z}}_{1}^{\prime})+\cdots+\begin{bmatrix}\boldsymbol{0}\\ \vdots\\ \boldsymbol{0}\\ \sigma^{-(k-1)}(\mathbf{B}_{0})\\ \sigma^{-(k-1)}(\overline{\mathbf{b}}_{1}^{\mathsf{T}})\end{bmatrix}\sigma^{-(% k-1)}(\overline{\mathbf{z}}_{k-1}^{\prime})+\mathbf{c}\cdot\begin{bmatrix}% \overline{\boldsymbol{0}}\\ \vdots\\ \vdots\\ \overline{\boldsymbol{0}}\\ F_{k}(\mathbf{s})\end{bmatrix}=\begin{bmatrix}\overline{\mathbf{w}}_{0}\\ \sigma^{-1}(\overline{\mathbf{w}}_{1})\\ \vdots\\ \sigma^{-(k-1)}(\overline{\mathbf{w}}_{k-1})\\ \mathbf{w}_{k}\end{bmatrix}+\mathbf{c}\cdot\begin{bmatrix}\overline{\mathbf{t}% }_{0}\\ \sigma^{-1}(\overline{\mathbf{t}}_{0})\\ \vdots\\ \sigma^{-(k-1)}(\overline{\mathbf{t}}_{0})\\ F_{k}(\mathbf{t}_{1})\end{bmatrix}.

(4.40)

The soundness is at most $p$ by eq. 4.18. Now take a closer look: The prior protocol uses $\mathbf{c}$ to test the automorphism filtering via the linear relation test over distinct BDLOP commitment keys in eq. 4.40. For automorphism repetition, think concretely from $\overline{\mathbf{z}}_{1}^{\prime}\leftarrow\overline{\mathbf{y}}_{1}+\sigma(% \mathbf{c})\cdot\overline{\mathbf{r}}$ , then the next $\mathbf{w}_{k,1}$ to send before $\mathbf{c}$ is

\mathbf{w}_{k,1}\leftarrow\sum_{i\in[0,k-1]}\sigma^{-i}\left(\langle\overline{% \mathbf{b}}_{1},\overline{\mathbf{y}}_{i+1\bmod k}\rangle\right),

and eq. 4.40 becomes

\begin{bmatrix}\mathbf{B}_{0}\\ \boldsymbol{0}\\ \vdots\\ \boldsymbol{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}_{1}^{% \prime}+\begin{bmatrix}\boldsymbol{0}\\ \sigma^{-1}(\mathbf{B}_{0})\\ \vdots\\ \boldsymbol{0}\\ \sigma^{-1}(\overline{\mathbf{b}}_{1}^{\mathsf{T}})\end{bmatrix}\sigma^{-1}(% \overline{\mathbf{z}}_{2}^{\prime})+\cdots+\begin{bmatrix}\boldsymbol{0}\\ \vdots\\ \boldsymbol{0}\\ \sigma^{-(k-1)}(\mathbf{B}_{0})\\ \sigma^{-(k-1)}(\overline{\mathbf{b}}_{1}^{\mathsf{T}})\end{bmatrix}\sigma^{-(% k-1)}(\overline{\mathbf{z}}_{0}^{\prime})+\sigma(\mathbf{c})\cdot\begin{% bmatrix}\overline{\boldsymbol{0}}\\ \vdots\\ \vdots\\ \overline{\boldsymbol{0}}\\ F_{k}(\mathbf{s})\end{bmatrix}=\begin{bmatrix}\overline{\mathbf{w}}_{1}\\ \sigma^{-1}(\overline{\mathbf{w}}_{2})\\ \vdots\\ \sigma^{-(k-1)}(\overline{\mathbf{w}}_{0})\\ \mathbf{w}_{k,1}\end{bmatrix}+\sigma(\mathbf{c})\cdot\begin{bmatrix}\overline{% \mathbf{t}}_{0}\\ \sigma^{-1}(\overline{\mathbf{t}}_{0})\\ \vdots\\ \sigma^{-(k-1)}(\overline{\mathbf{t}}_{0})\\ F_{k}(\mathbf{t}_{1})\end{bmatrix}.

By induction,

\mathbf{w}_{k,j}\leftarrow\sum_{i\in[0,k-1]}\sigma^{-i}\left(\langle\overline{% \mathbf{b}}_{1},\overline{\mathbf{y}}_{i+j\bmod k}\rangle\right)=\sigma^{j}% \left(\mathbf{w}_{k}\right).

(4.41)

Supposing a slot under the slots grouped by $\left(X^{k}-\xi^{k}\right)$ is wrong, then the adversary needs to guess $\mathbf{c}\bmod\left(X^{k}-\xi^{k}\right)$ to convince the verifier, with the same strategy for the affine forging in weak opening in the note for [ALS20], by fixing the pre-challenge $\overline{\mathbf{w}}$ for the relevant error term, yielding the soundness of at most $p^{k}$ , where $p$ is eq. 4.18 for the guessing probability of each coefficient in coarse $\left(X^{k}-\xi^{k}\right)$ .

The rest is to prove the automorphism filtering of each $\mathsf{NTT}^{-1}(d\overline{\gamma}_{j}^{\mathsf{T}}A)\mathbf{s}$ for $j\in[0,k-1]$ by stacking them up over $X^{j}$ , normalizing by $k^{-1}$ , masking by $\mathbf{g}$ , and eventually eq. 4.37. To carry on the automorphism filtering test derived from the linearity test, each $\mathbf{w}_{k,j}$ derived from eq. 4.39 is indexed by $j\in[0,k-1]$ for each $\overline{\gamma}_{j}$ by

\mathbf{w}_{k,j}\leftarrow\sum_{i\in[0,k-1]}\sigma^{-i}\left(\langle\mathsf{% NTT}^{-1}(d\overline{\gamma}_{j}^{\mathsf{T}}A)\cdot\overline{\mathbf{b}}_{2},% \overline{\mathbf{y}}_{i}\rangle\right).

Correspondingly, the verifier can derive

\mathbf{u}_{k,j}\leftarrow\sum_{i\in[0,k-1]}\sigma^{-i}\left(\langle\mathsf{% NTT}^{-1}(d\overline{\gamma}_{j}^{\mathsf{T}}A)\cdot\overline{\mathbf{b}}_{2},% \overline{\mathbf{z}}_{i}^{\prime}\rangle\right),

and on the third round prover response, by eq. 4.41, for each $i\in[0,k-1]$ automorphic challenges $\sigma^{i}(\mathbf{c})$ ,

\mathbf{w}_{f_{i}}\leftarrow\langle\overline{\mathbf{b}}_{1},\overline{\mathbf% {y}}_{i}\rangle+\sum_{j\in[0,k-1]}k^{-1}X^{j}\sigma^{i}\left(\mathbf{w}_{k,j}% \right),

(4.42)

and the verifier can derive correspondingly

\mathbf{u}_{f_{i}}\leftarrow\langle\overline{\mathbf{b}}_{1},\overline{\mathbf% {z}}_{i}^{\prime}\rangle+\sum_{j\in[0,k-1]}k^{-1}X^{j}\sigma^{i}\left(\mathbf{% u}_{k,j}\right),

(4.43)

such that for each $i\in[0,k-1]$ automorphic challenges $\sigma^{i}(\mathbf{c})$ ,

\mathbf{w}_{f_{i}}+\sigma^{i}(\mathbf{c})\cdot\underbrace{\left(\mathbf{t}_{1}% +\sum_{j\in[0,k-1]}k^{-1}X^{j}F_{k}\left(\mathsf{NTT}^{-1}\left(d\overline{% \gamma}_{j}^{\mathsf{T}}A\right)\cdot\mathbf{t}_{2}\right)\right)}_{\mathbf{t}% }=\mathbf{u}_{f_{i}}+\sigma^{i}(\mathbf{c})\cdot\underbrace{\left(\mathbf{g}+% \sum_{j\in[0,k-1]}k^{-1}X^{j}F_{k}\left(\mathsf{NTT}^{-1}\left(d\overline{% \gamma}_{j}^{\mathsf{T}}A\right)\cdot\mathbf{s}\right)\right)}_{\mathbf{z}},

(4.44)

where $\mathbf{t},\mathbf{z}$ were in eq. 4.38 and eq. 4.37.

Again, now the masked openings for the garbage terms, and the combined claim, are formed as

\begin{split}\mathbf{f}_{4}&=\langle\overline{\mathbf{b}}_{4},\overline{% \mathbf{y}}_{0}\rangle-\mathbf{c}\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j}% \sigma^{-j}\left(\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{y}}_{j}% \rangle\left(3\mathbf{s}^{2}-\boldsymbol{1}\right)\right)=\langle\overline{% \mathbf{b}}_{4},\overline{\mathbf{y}}_{0}\rangle-\mathbf{c}\mathbf{m}_{4},\\ \mathbf{f}_{3}&=\langle\overline{\mathbf{b}}_{3},\overline{\mathbf{y}}_{0}% \rangle-\mathbf{c}\left(\langle\overline{\mathbf{b}}_{4},\overline{\mathbf{y}}% _{0}\rangle-3\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j}\sigma^{-j}\left(\langle% \overline{\mathbf{b}}_{2},\overline{\mathbf{y}}_{j}\rangle^{2}\mathbf{s}\right% )\right)=\langle\overline{\mathbf{b}}_{3},\overline{\mathbf{y}}_{0}\rangle-% \mathbf{c}\mathbf{m}_{3},\\ \mathbf{v}&=\langle\overline{\mathbf{b}}_{3},\overline{\mathbf{y}}_{0}\rangle+% \sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j}\sigma^{-j}\left(\langle\overline{% \mathbf{b}}_{2},\overline{\mathbf{y}}_{j}\rangle^{3}\right),\end{split}

(4.45)

such that the random linear combination yields the statement and the invariant for combined claim

\begin{split}\boldsymbol{0}&=\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j}\sigma^{% -j}\left(\mathbf{s}^{3}-\mathbf{s}\right),\\ \mathbf{v}&=\sum_{j\in[0,k-1]}\boldsymbol{\alpha}_{j}\sigma^{-j}\left(\mathbf{% f}_{2,j}\left(\mathbf{f}_{2,j}-\sigma^{j}\left(\mathbf{c}\right)\right)\left(% \mathbf{f}_{2,j}+\sigma^{j}\left(\mathbf{c}\right)\right)\right)+\mathbf{f}_{3% }+\mathbf{c}\mathbf{f}_{4},\end{split}

(4.46)

where $\mathbf{f}_{i}=\langle\overline{\mathbf{b}}_{i},\overline{\mathbf{z}}_{0}^{% \prime}\rangle-\mathbf{c}\mathbf{t}_{i}=\langle\overline{\mathbf{b}}_{i},% \overline{\mathbf{y}}_{0}\rangle-\mathbf{c}\mathbf{m}_{i}$ for $i\in\{3,4\}$ , each $\mathbf{f}_{2,j}$ for $j\in[0,k-1]$ is

\mathbf{f}_{2,j}=\langle\overline{\mathbf{b}}_{2},\overline{\mathbf{z}}_{j}^{% \prime}\rangle-\sigma^{j}\left(\mathbf{c}\right)\mathbf{t}_{2}=\langle% \overline{\mathbf{b}}_{2},\overline{\mathbf{y}}_{j}\rangle-\sigma^{j}\left(% \mathbf{c}\right)\mathbf{s},

and the second equality holds if the prover is honest.

The protocol for a single matrix multiplication claim follows:

•

The prover sends $\overline{\mathbf{w}}_{i}\leftarrow\mathbf{B}_{0}\overline{\mathbf{y}}_{i}$ , where $\overline{\mathbf{y}}_{i}\leftarrow D_{\sigma}^{Nd}$ , samples $\mathbf{g}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{R_{q}:g_{j}=0,j% \in[0,k-1]\}$ and $\overline{\mathbf{r}}\leftarrow\chi^{Nd}$ to commit

$\begin{bmatrix}\overline{\mathbf{t}}_{0}\\ \mathbf{t}_{1}\\ \mathbf{t}_{2}\end{bmatrix}\leftarrow\begin{bmatrix}\mathbf{B}_{0}\\ \overline{\mathbf{b}}_{1}^{\mathsf{T}}\\ \overline{\mathbf{b}}_{2}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{g}\\ \mathbf{s}\end{bmatrix}.$
•

The verifier challenges by sending $\overline{\gamma}_{0},\ldots,\overline{\gamma}_{k-1}\stackrel{{\scriptstyle% \textsc{r}}}{{\leftarrow}}\mathbb{Z}_{q}^{d}$ and $\boldsymbol{\alpha}_{0},\ldots,\boldsymbol{\alpha}_{k-1}\stackrel{{% \scriptstyle\textsc{r}}}{{\leftarrow}}R_{q}$ .
•
The prover replies $\mathbf{z}$ in eq. 4.37, and starts $\Pi_{\mathsf{lin}}$ and the shortness check in [ALS20] by:
- –
  
  The prover replies each $\mathbf{w}_{f_{i}}$ for $i\in[0,k-1]$ in eq. 4.42, then it commits
  
  $\begin{bmatrix}\mathbf{t}_{3}\\ \mathbf{t}_{4}\end{bmatrix}\leftarrow\begin{bmatrix}\overline{\mathbf{b}}_{3}^% {\mathsf{T}}\\ \overline{\mathbf{b}}_{4}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{r}}+% \begin{bmatrix}\mathbf{m}_{3}\\ \mathbf{m}_{4}\end{bmatrix},$
  
  and replies with $\mathbf{t}_{3},\mathbf{t}_{4}$ , and the claim $\mathbf{v}$ in eq. 4.45,
- –
  
  The verifier samples $\mathbf{c}$ over the $\{-1,0,1\}$ challenge set $\mathcal{C}$ , with each coefficient has $P(\pm 1)=1/4$ , $P(0)=1/2$ .
- –
  
  The prover runs rejection sampling, and outputs $\overline{\mathbf{z}}_{i}^{\prime}\leftarrow\overline{\mathbf{y}}_{i}+\sigma^{% i}\left(\mathbf{c}\right)\cdot\overline{\mathbf{r}}$ for $i\in[0,k-1]$ .
•

The verifier checks $\overline{\mathbf{z}}_{i}^{\prime}$ being short, $z_{j}=\langle\overline{\gamma}_{j},\overline{u}\rangle$ for $j\in[0,k-1]$ .

It then derives $\mathbf{u}_{f_{i}}$ for $i\in[0,k-1]$ in eq. 4.43, $\mathbf{t}$ in eq. 4.38, checks

$\displaystyle\overline{\mathbf{w}}_{i}+\sigma^{i}(\mathbf{c})\cdot\overline{% \mathbf{t}}_{0}$ $\displaystyle=\mathbf{B}_{0}\overline{\mathbf{z}}_{i}^{\prime},$

$\displaystyle\mathbf{w}_{f_{i}}+\sigma^{i}(\mathbf{c})\cdot\mathbf{t}$ $\displaystyle=\mathbf{u}_{f_{i}}+\sigma^{i}(\mathbf{c})\cdot\mathbf{z}$

for $i\in[0,k-1]$ , which is eq. 4.44 and eq. 4.40,

Finally, it checks the shortness of $\hat{\mathbf{s}}$ by the second equality eq. 4.46.

Cost Comparison Against [BLS19].

We compare the published noninteractive constructions of [BLS19, ENS20] by counting transmitted elements and their coefficient widths.

Let $n$ be the total witness length, $A\in\mathbb{Z}_{q}^{m\times n}$ , $d$ be the $R_{q}$ degree, and $b_{q}=\left\lceil\log_{2}q\right\rceil$ . We retain $N$ for the opening-vector width and $\mu$ for the top commitment rank. Counts exclude the public statement and commitment key. The following are the papers’ historical parameter choices for approximately 128-bit security.

Parameter	BLS19	ENS20
Matrix dimensions $m\times n$	$1024\times 2048$	$1024\times 2048$
Coefficient width $b_{q}$	$32$	$32$
Ring degree $d$	$2048$	$128$
Witness polynomials $n/d$	$1$	$16$
Repetitions	$t=4$ , $t^{\prime}=3$	$k=4$
Commitment ranks $(\lambda,\mu)$	$(1,1)$	$(10,9)$

In particular, ENS separates the witness length from the ring degree: Their example uses 16 witness polynomials.

BLS: transmitted objects. In the optimized Fiat–Shamir protocol of [BLS19, Algorithms 2–3 and Section 3.4], each of the $t$ commitment vectors has five ring elements, with one shared across repetitions. There are $t$ masked witness replies and $tt^{\prime}$ short opening vectors of width 6.

Component	Count	Bits per coefficient or choice
Commitments	$1+4t$ ring elements	$b_{q}$
Masked witness replies	$t$ ring elements	$b_{q}$
Short opening replies	$6tt^{\prime}$ ring elements	$b_{z}$
Scalar challenges	$t$ scalars	$b_{q}$
Monomial challenges	$tt^{\prime}$ choices	$\lceil\log_{2}\ell\rceil$

Here $d=n$ and $\ell=2d$ for the power-of-two benchmark. The proof size in bits is therefore

S_{\mathrm{BLS}}=(1+5t)db_{q}+6tt^{\prime}db_{z}+t\bigl{(}b_{q}+t^{\prime}% \lceil\log_{2}\ell\rceil\bigr{)}.

(4.47)

For $\sigma=919.13$ , the short-coefficient width is $b_{z}=\lceil\log_{2}(12\sigma)\rceil=14$ . Substituting the benchmark parameters gives

Component	Calculation in bytes	Size
Full part	$21\cdot 2048\cdot 32/8=172{,}032$	$168$ KiB
Short part	$72\cdot 2048\cdot 14/8=258{,}048$	$252$ KiB
Challenges	$4(32+3\cdot 12)/8=34$	$34$ bytes
Total	$430{,}114$	$420.0332$ KiB

ENS: transmitted objects. For $n/d$ witness polynomials, the committed message count and opening width are

L=n/d+3,\qquad N=\lambda+\mu+L.

The additional 3 messages are the $\mathbf{g}$ linear-test mask, and the two shortness garbage terms.

Besides the $\mu+L$ commitment elements, ENS transmits one masked linear-test polynomial, called $h$ in the paper. For our single-polynomial notation it is the publicly centered response

h=\mathbf{z}-\sum_{j=0}^{k-1}X^{j}\langle\overline{\gamma}_{j},\overline{u}\rangle,

so its first $k$ coefficients are known to be zero. After reconstructing the first messages, the remaining short replies contain $k N$ ring elements. With $b_{z}=\lceil\log_{2}(2\delta_{1})\rceil$ , [ENS20, Section 4.2, Equation (11)] gives the basic bit count

\begin{split}S_{\mathrm{ENS}}^{\mathrm{basic}}&=(\mu+n/d+4)db_{q}+k(\lambda+% \mu+n/d+3)db_{z}\\ &=[n+(\mu+4)d]b_{q}+k[n+(\lambda+\mu+3)d]b_{z}.\end{split}

(4.48)

This leading count omits the 256-bit challenge seed and the saving from the $k$ known coefficients of $h$ .

For bookkeeping, insert $\delta_{1}=2^{18}$ from [ENS20, Appendix B.1], so $b_{z}=19$ , $L=19$ , and $N=38$ :

Component	Calculation in bytes	Size
Full part	$29\cdot 128\cdot 32/8=14{,}848$	$14.5$ KiB
Short part	$152\cdot 128\cdot 19/8=46{,}208$	$45.125$ KiB
Basic total	$61{,}056$	$59.625$ KiB

Although ENS has more short polynomials ( $152$ versus $72$ ), it has $19456$ short coefficients, compared to BLS’s $147456$ . ENS and BLS contain $29$ and $21$ full ring elements, respectively, or $3712$ and $43008$ coefficients.

	$\displaystyle\overline{\mathbf{w}}_{i}+\sigma^{i}(\mathbf{c})\cdot\overline{% \mathbf{t}}_{0}$	$\displaystyle=\mathbf{B}_{0}\overline{\mathbf{z}}_{i}^{\prime},$
	$\displaystyle\mathbf{w}_{f_{i}}+\sigma^{i}(\mathbf{c})\cdot\mathbf{t}$	$\displaystyle=\mathbf{u}_{f_{i}}+\sigma^{i}(\mathbf{c})\cdot\mathbf{z}$