4 Various Papers 4.13 Practical Exact Proofs from Lattices 4.15 Practical Sublinear Proofs for R1CS from Lattices

4.14 Lattice Proofs for Exact Euclidean Norm Bounds and Quadratic Relations

One of the motivations of [LNP22] is that, the prior works [BLS19, ENS20] for $A\hat{\mathbf{s}}=\overline{\mathbf{u}}$ restrict each entry of $\hat{\mathbf{s}}$ being over $\{-1,0,1\}$ , and thus committing the $\mathbf{m}=\mathsf{NTT}^{-1}(\hat{\mathbf{s}})$ , which can be arbitrarily long, can be expensive with [BDL+18b]. If we want to work with $\hat{\mathbf{s}}$ with larger $\ell_{\infty}$ -norm, then more garbage terms are needed in the commitment.

The question they asked was: Is NTT packing all that necessary, as both concrete efficiency and communication complexity can be improved if no NTT packing is involved. In [LNP22], the encoding over CRT slots [BLS19, ALS20, ENS20] is not used, messages are committed in coefficient form. In this case, $R_{q}$ is not necessarily fully splitting.

Challenge Set.

There are many ways to construct challenge sets for the $R_{q}$ :

•

In [LS18], the corollary 4.12.3 gives a short challenge set, such that all nonzero pairwise differences are invertible, but by corollaries 4.12.2 and 4.12.3, the modulus grows with the number of splitting factors and the norm bound of the set of short elements, and some computation is in table 4.12.1;
•

In [BLS19], the eq. 4.7 suffices;
•

In [ALS20], the anti-concentration lemma 4.12.5 gives the max point probability of a CRT slot, and the probability for pairwise difference being non-invertible is upper bounded by a union bound. The extractor can extract CRT slot by slot, so it is not required to be globally pairwise difference invertible.

In [LNP22], they found another set of elements in $R_{q}$ that is invertible.

Lemma 4.14.1.

By corollary 4.12.2, let $p\equiv 5\pmod{8}$ be a prime, then any nonzero $\mathbf{c}\in R_{p}$ such that $\sigma_{-1}(\mathbf{c})=\mathbf{c}$ is invertible.

Proof.

By corollary 4.12.2, if $p\equiv 5\bmod 8$ is a prime, then

R_{p}=\mathbb{Z}_{p}[X]/(X^{d}+1)\cong\mathbb{Z}_{p}[X]/(X^{d/2}-r)\times% \mathbb{Z}_{p}[X]/(X^{d/2}+r),

$r$ being the $4^{\mathrm{th}}$ primitive root of unity, splitting 2 irreducible factors. Since $\sigma_{-1}(\mathbf{c})=\mathbf{c}$ , then satisfying elements are

\mathbf{c}=c_{0}+\sum_{i\in[1,d/2-1]}c_{i}\left(X^{i}-X^{d-i}\right)=c_{0}+% \sum_{i\in[1,d/2-1]}c_{i}X^{i}-\sum_{i\in[1,d/2-1]}c_{i}X^{d-i},

as any $X^{i}-X^{d-i}$ satisfies $\sigma_{-1}(X^{i}-X^{d-i})=X^{i}-X^{d-i}$ . Hence, for each factor $(X^{d/2}\pm r)$ , we have

\mathbf{c}\equiv c_{0}+\sum_{i\in[1,d/2-1]}\left(c_{i}\pm rc_{d/2-i}\right)X^{% i}\mod\left(X^{d/2}\pm r\right).

We claim at least one of $c_{i}-rc_{d/2-i}$ and $c_{d/2-i}-rc_{i}$ is nonzero, given that at least one of $c_{i},c_{d/2-i}$ is nonzero: Supposing $c_{i}=rc_{d/2-i}$ , then $(1-r^{2})c_{d/2-i}\neq 0$ . The case for $c_{i}+rc_{d/2-i}$ and $c_{d/2-i}+rc_{i}$ is the same idea.

Hence, a nonzero $\mathbf{c}$ is nonzero at both factors if $\sigma_{-1}(\mathbf{c})=\mathbf{c}$ . ∎

The lemma 4.14.1 can be applied to the $R_{q}$ , where $q=\prod q_{i}$ , and $q_{1}<\cdots<q_{k}$ , with all $q_{i}\equiv 5\pmod{8}$ are primes, then $R_{q}=\prod R_{q_{i}}$ , and thus each $R_{q_{i}}$ splits into 2 irreducible factors. Hence, any nonzero $\mathbf{c}\in R_{q}$ satisfying $\sigma_{-1}(\mathbf{c})=\mathbf{c}$ and $0<\left\|\mathbf{c}\right\|_{\infty}<q_{1}$ , $\mathbf{c}$ is invertible.

The short invertible set of elements from lemma 4.14.1 shares a similar vibe to [LS18]. The similarity is generally “If it is just too short, it will not wrap around in any of the CRT slots”.

•

The current one finds a pattern of invertibility $\sigma_{-1}(\mathbf{c})=\mathbf{c}$ that applies to any $R_{q_{i}}$ splitting into 2 irreducible factors in the above setting, then any nonzero $\mathbf{c}\in R_{q}$ such that $\sigma_{-1}(\mathbf{c})=\mathbf{c}$ , that is shorter than $q_{1}$ in $\ell_{\infty}$ -norm is invertible, as the coefficient representations within $[-q_{1}+1,q_{1}-1]$ can remain the same for all $[-q_{i}+1,q_{i}-1]$ where $q_{i}\geq q_{1}$ .
•

The [LS18] one is, considering $R_{q}\cong\prod\mathbb{Z}_{q}[X]/(f_{i}(X))$ , then for the ideal lattice $\Lambda=\{\mathbf{x}\in R_{m}:\mathbf{x}\equiv 0\mod(f_{i},q)\}$ , if nonzero $\mathbf{x}\in R_{q}$ is shorter than $\lambda_{1}(\Lambda)$ in $\ell_{2}$ -norm, then $\mathbf{x}$ cannot belong to the CRT kernel lattice $\Lambda$ .

Now we move on and consider the norm growth when multiplying with challenge set elements, namely we want to bound $\left\|\mathbf{c}\overline{\mathbf{r}}\right\|_{2}$ . The main idea of the next lemma is to upper bound the operator norm of $\mathsf{rot}(\mathbf{c})\in\mathbb{Z}^{d\times d}$ , such that

\left\|\mathbf{c}\overline{\mathbf{r}}\right\|\leq\left(\max_{\left\|\mathbf{x% }\right\|_{2}=1}\left\|\mathbf{c}\mathbf{x}\right\|_{2}\right)\left\|\overline% {\mathbf{r}}\right\|_{2}=\left\|\mathsf{rot}(\mathbf{c})\right\|_{2}\left\|% \overline{\mathbf{r}}\right\|_{2}.

Lemma 4.14.2.

Let $\overline{\mathbf{r}}\in R^{\ell}$ and $\mathbf{c}\in R$ , then for any power-of-two $\kappa$ , we have

\left\|\mathbf{c}\overline{\mathbf{r}}\right\|_{2}\leq\left\|\sigma_{-1}\left(% \mathbf{c}^{\kappa}\right)\mathbf{c}^{\kappa}\right\|_{1}^{1/(2\kappa)}\cdot% \left\|\overline{\mathbf{r}}\right\|_{2}.

Proof.

We first write $\mathbf{C}=\mathsf{rot}(\mathbf{c})\in\mathbb{Z}^{d\times d}$ , then

\left\|\mathbf{C}\right\|_{2}^{2}=\max_{\left\|\overline{x}\right\|_{2}=1}% \left\|\mathbf{C}\overline{x}\right\|_{2}^{2}=\max_{\left\|\overline{x}\right% \|_{2}=1}{\overline{x}}^{\mathsf{T}}\mathbf{C}^{\mathsf{T}}\mathbf{C}\overline% {x},

(4.49)

where the last equality holds by squaring up and summing up all entries in $\mathbf{C}\overline{x}$ , then by eq. 4.49, $\mathbf{C}^{\mathsf{T}}\mathbf{C}$ is positive semidefinite. By the spectral theorem, $\mathbf{C}^{\mathsf{T}}\mathbf{C}$ has an orthonormal eigenbasis, that eigenvectors $\{\overline{v}_{i}\}_{i\in[1,d]}$ are mutually perpendicular and of $\ell_{2}$ -norm being 1. Hence, for $\overline{x}$ with $\left\|\overline{x}\right\|_{2}=1$ ,

\mathbf{C}^{\mathsf{T}}\mathbf{C}\overline{x}=\mathbf{C}^{\mathsf{T}}\mathbf{C% }\sum_{i\in[1,d]}\alpha_{i}\overline{v}_{i}=\sum_{i\in[1,d]}\alpha_{i}\lambda_% {i}\overline{v}_{i},

(4.50)

and by the $\left\|\overline{x}\right\|_{2}=1$ ,

1=\left\|\sum_{i\in[1,d]}\alpha_{i}\overline{v}_{i}\right\|_{2}^{2}=\sum_{i\in% [1,d]}\alpha_{i}^{2}+\sum_{i\neq j\in[1,d]}\alpha_{i}\alpha_{j}\langle% \overline{v}_{i},\overline{v}_{j}\rangle=\sum_{i\in[1,d]}\alpha_{i}^{2}.

(4.51)

Therefore, conditioned that eq. 4.51, we have

\left\|\mathbf{C}^{\mathsf{T}}\mathbf{C}\right\|_{2}=\max_{\left\|\overline{x}% \right\|=1}\left\|\mathbf{C}^{\mathsf{T}}\mathbf{C}\overline{x}\right\|_{2}=% \max_{\{\alpha_{i}\}_{i\in[1,d]}}\left\|\sum_{i\in[1,d]}\alpha_{i}\lambda_{i}% \overline{v}_{i}\right\|_{2}=\max_{\{\alpha_{i}\}_{i\in[1,d]}}\left(\sum_{i\in% [1,d]}\alpha_{i}^{2}\lambda_{i}^{2}\right)^{1/2}=\max_{i\in[1,d]}\left|\lambda% _{i}\right|,

where the third equality holds by eq. 4.51. Moreover, continuing from eq. 4.50, we finish eq. 4.49 by

\left\|\mathbf{C}\right\|_{2}^{2}=\max_{\{\alpha_{i}\}_{i\in[1,d]}}\sum_{i\in[% 1,d]}\alpha_{i}^{2}\lambda_{i}=\max_{i\in[1,d]}\lambda_{i}=\left\|\mathbf{C}^{% \mathsf{T}}\mathbf{C}\right\|_{2},

where the last equality holds by the positive semidefiniteness of $\mathbf{C}^{\mathsf{T}}\mathbf{C}$ , such that each $\lambda_{i}$ is nonnegative. Continuing on, since $\mathbf{A}=\mathbf{C}^{\mathsf{T}}\mathbf{C}$ is positive semidefinite, then $\mathbf{A}^{\mathsf{T}}\mathbf{A}=\mathbf{A}^{2}$ as $\mathbf{A}$ is diagonal symmetric, then

\left\|\mathbf{C}\right\|_{2}^{2\kappa}=\left\|\mathbf{C}^{\mathsf{T}}\mathbf{% C}\right\|_{2}^{\kappa}=\left\|\left(\mathbf{C}^{\mathsf{T}}\mathbf{C}\right)^% {\kappa}\right\|_{2}.

For $\mathbf{u},\mathbf{v}\in R$ , another observation for $\mathbf{u}\mathbf{v}=\mathsf{rot}(\mathbf{u})\overline{v}$ is,

\mathsf{rot}(\mathbf{u})\overline{v}=\sum_{i\in[0,d-1]}u_{i}\mathsf{rot}(X^{i}% )\overline{v},

and therefore by triangle inequality,

\left\|\mathsf{rot}(\mathbf{u})\overline{v}\right\|_{2}\leq\sum_{i\in[0,d-1]}% \left|u_{i}\right|\left\|\mathsf{rot}(X^{i})\overline{v}\right\|_{2}=\left\|% \mathbf{u}\right\|_{1}\cdot\left\|\mathbf{v}\right\|_{2}.

(4.52)

Hence, for $\mathbf{v}$ with $\left\|\mathbf{v}\right\|_{2}=1$ and coefficients over $\mathbb{R}$ , by operator norm eq. 4.49, $\left\|\mathsf{rot}(\mathbf{u})\right\|_{2}\leq\left\|\mathbf{u}\right\|_{1}$ . The rest is immediate by the fact that $\mathbf{C}^{\mathsf{T}}=\mathsf{rot}(\sigma_{-1}(\mathbf{c}))$ , then

\left(\mathbf{C}^{\mathsf{T}}\mathbf{C}\right)^{2}=\mathsf{rot}\left(\sigma_{-% 1}\left(\sigma_{-1}(\mathbf{c})\mathbf{c}\right)\right)\mathsf{rot}\left(% \sigma_{-1}(\mathbf{c})\mathbf{c}\right)=\mathsf{rot}\left(\sigma_{-1}(\mathbf% {c})^{2}\mathbf{c}^{2}\right)=\mathsf{rot}\left(\sigma_{-1}(\mathbf{c}^{2})% \mathbf{c}^{2}\right),

and by induction,

\left\|\mathbf{C}\right\|_{2}^{2\kappa}=\left\|\mathbf{C}^{\mathsf{T}}\mathbf{% C}\right\|_{2}^{\kappa}=\left\|\left(\mathbf{C}^{\mathsf{T}}\mathbf{C}\right)^% {\kappa}\right\|_{2}=\left\|\mathsf{rot}\left(\sigma_{-1}(\mathbf{c}^{\kappa})% \mathbf{c}^{\kappa}\right)\right\|_{2}\leq\left\|\sigma_{-1}(\mathbf{c}^{% \kappa})\mathbf{c}^{\kappa}\right\|_{1}.

∎

Moreover, by eq. 4.52, we have $\left\|\mathbf{u}\mathbf{v}\right\|_{1}\leq\left\|\mathbf{u}\right\|_{1}\left% \|\mathbf{v}\right\|_{1}$ , then $\left\|\sigma_{-1}(\mathbf{c}^{\kappa})\mathbf{c}^{\kappa}\right\|_{1}^{1/(2% \kappa)}$ is monotonically nonincreasing by

\left\|\sigma_{-1}(\mathbf{c}^{2\kappa})\mathbf{c}^{2\kappa}\right\|_{1}^{1/(4% \kappa)}=\left\|(\sigma_{-1}(\mathbf{c}^{\kappa})\mathbf{c}^{\kappa})^{2}% \right\|_{1}^{1/(4\kappa)}\leq\left\|\sigma_{-1}(\mathbf{c}^{\kappa})\mathbf{c% }^{\kappa}\right\|_{1}^{1/(2\kappa)}.

On the other hand, by Cauchy-Schwartz, $\left\|\mathbf{v}\right\|_{1}\leq\sqrt{d}\left\|\mathbf{v}\right\|_{2}$ , then

\left\|\sigma_{-1}(\mathbf{c}^{\kappa})\mathbf{c}^{\kappa}\right\|_{1}^{1/(2% \kappa)}\leq d^{1/(4\kappa)}\left\|\sigma_{-1}(\mathbf{c}^{\kappa})\mathbf{c}^% {\kappa}\right\|_{2}^{1/(2\kappa)}\leq d^{1/(4\kappa)}\left\|\left(\mathbf{C}^% {\mathsf{T}}\mathbf{C}\right)^{\kappa}\right\|_{2}^{1/(2\kappa)}=d^{1/(4\kappa% )}\left\|\mathbf{C}\right\|_{2},

where the second inequality holds by letting the rotational matrix multiplying against $\overline{e}_{0}=[1,0,\ldots,0]^{\mathsf{T}}$ .

Therefore,

\left\|\mathbf{C}\right\|_{2}\leq\left\|\sigma_{-1}(\mathbf{c}^{2\kappa})% \mathbf{c}^{2\kappa}\right\|_{1}^{1/(4\kappa)}\leq\left\|\sigma_{-1}(\mathbf{c% }^{\kappa})\mathbf{c}^{\kappa}\right\|_{1}^{1/(2\kappa)}\leq d^{1/(4\kappa)}% \left\|\mathbf{C}\right\|_{2},

and the upper bound by lemma 4.14.2 is monotonically nonincreasing, and is approaching the operator norm $\left\|\mathbf{C}\right\|_{2}$ .

Given lemma 4.14.2 as an estimation for the $\ell_{2}$ operator norm of $\mathbf{c}\in R$ , we construct the challenge set $\mathcal{C}$ defined over the elements specified by lemma 4.14.1, that for a power-of-two $k$ ,

\mathcal{C}:=\{\mathbf{c}\in S_{\kappa}^{\sigma}~{}:~{}\left\|\sigma_{-1}(% \mathbf{c}^{k})\mathbf{c}^{k}\right\|_{1}^{1/(2k)}\leq\eta\},

(4.53)

where $S_{\kappa}^{\sigma}=\{\mathbf{c}\in S_{\kappa}~{}:~{}\sigma(\mathbf{c})=% \mathbf{c}\}$ for $\sigma\in\mathsf{Aut}(R_{q})$ , and $S_{\kappa}$ is defined in eq. 4.5, that $\kappa\leq(q_{1}-1)/2$ . Eventually, the goal is to make the $\ell_{\infty}$ -norm of challenges to be bounded by $(q_{1}-1)/2$ , and estimate $\left\|\mathsf{rot}(\mathbf{c})\right\|_{2}\leq\eta$ , such that $\left\|\mathbf{c}\overline{\mathbf{r}}\right\|_{2}\leq\eta\left\|\overline{% \mathbf{r}}\right\|_{2}$ .

Rejection Sampling and Parameters.

We haven’t get to the extended MLWE from [LNS21], so we use the vanilla rejection sampling from [Lyu12] throughout this note. In [LNP22], the masking randomness for [BDL+18b] and [Ajt96] is sampled over a Gaussian distribution, and the next lemma help describe the concentration property of a sample.

Lemma 4.14.3 (Gaussian Tail Bound [Ban93]).

Let $\overline{\mathbf{z}}\leftarrow D_{s}^{md}$ , then for $t>1$ ,

\Pr\left[\left\|\overline{\mathbf{z}}\right\|_{2}>t\cdot s\sqrt{md}\right]<% \left(t\exp\left(\frac{1-t^{2}}{2}\right)\right)^{md}.

In [LNP22], the lemma 4.14.3 is parameterized with $t=\sqrt{2}$ , then

\Pr\left[\left\|\overline{\mathbf{z}}\right\|_{2}>s\sqrt{2md}\right]<\left(2/e% \right)^{md/2}.

We continue on describing the rejection sampling from the same algorithm in [Lyu12], but parameterized differently from [BLS19]. The key idea is using the outputting probability threshold by [Lyu12] for $\overline{\mathbf{z}}\leftarrow\overline{\mathbf{y}}+\overline{\mathbf{v}}$ where $\overline{\mathbf{y}}\leftarrow D_{s}^{md}$

\min\left(\frac{1}{M}\cdot\frac{D^{md}_{s}(\overline{\mathbf{z}})}{D^{md}_{% \overline{\mathbf{v}},s}(\overline{\mathbf{z}})},1\right)=\min\left(\frac{1}{M% }\cdot\frac{\rho_{s}(\overline{\mathbf{z}})}{\rho_{s}(\overline{\mathbf{z}}-% \overline{\mathbf{v}})},1\right),

(4.54)

where $\rho_{s}$ is defined in eq. 4.9, and since we are working over Gaussian distributions, the equality holds. Moreover, over $\overline{\mathbf{z}}\leftarrow D_{s}^{md}$ ,

\Pr\left[D_{s}^{md}(\overline{\mathbf{z}})\leq M\cdot D_{\overline{\mathbf{v}}% ,s}^{md}(\overline{\mathbf{z}})\right]\geq 1-2^{-128},

(4.55)

then the threshold eq. 4.54 uses the left term with overwhelming probability: The $M$ is chosen by $s:=\gamma\left\|\overline{\mathbf{v}}\right\|_{2}$ , then

\frac{\rho_{s}(\overline{\mathbf{z}})}{\rho_{s}(\overline{\mathbf{z}}-% \overline{\mathbf{v}})}=\exp\left(\frac{-2\langle\overline{\mathbf{z}},% \overline{\mathbf{v}}\rangle+\left\|\overline{\mathbf{v}}\right\|_{2}^{2}}{2s^% {2}}\right)\leq\exp\left(\frac{28s\left\|\overline{\mathbf{v}}\right\|_{2}+% \left\|\overline{\mathbf{v}}\right\|_{2}^{2}}{2s^{2}}\right)=\exp\left(\frac{1% 4}{\gamma}+\frac{1}{2\gamma^{2}}\right)=M,

(4.56)

(if $\left\|\overline{\mathbf{v}}\right\|_{2}\leq T$ , then $s:=\gamma T$ ), and the second inequality holds with overwhelming probability by Lemma 4.3 of [Lyu12]:

\Pr\left[\left|\langle\overline{\mathbf{z}},\overline{\mathbf{v}}\rangle\right% |\geq 14s\left\|\overline{\mathbf{v}}\right\|_{2}\right]\leq 2\exp\left(-98% \right)\leq 2^{-128},

thus eq. 4.55 holds, the accepting probability is at least $(1-2^{-128})/M$ , and conditioned on the sample’s acceptance, the statistical distance of the real distribution is within $2^{-128}$ against the simulated distribution.

ABDLOP Commitment Scheme.

Consider combining Ajtai [Ajt96] and BDLOP [BDL+18b] together, then we have ABDLOP commitment [LNP22]. Recall eq. 4.19, where the commitment key is over $R_{q}^{(\mu+L)\times N}$ :

•

Binding is reduced to ${\mathsf{MSIS}}_{\mu,N,B}$ .
•

Hiding is reduced to ${\mathsf{MLWE}}_{\lambda,\mu+L,\chi}$ , where commitment randomness is drawn from distribution $\chi^{Nd}$ .

Onwards, we use $m_{1}$ to denote the length of the Ajtai message, and $m_{2}$ to denote the length of the BDLOP randomness. The combination is done by stacking an Ajtai commitment to the SIS part in the BDLOP commitment:

\begin{bmatrix}\overline{\mathbf{t}}_{A}\\ \overline{\mathbf{t}}_{B}\end{bmatrix}=\begin{bmatrix}\mathbf{A}_{1}\\ \boldsymbol{0}\end{bmatrix}\overline{\mathbf{s}}_{1}+\begin{bmatrix}\mathbf{A}% _{2}\\ \mathbf{B}\end{bmatrix}\overline{\mathbf{s}}_{2}+\begin{bmatrix}\overline{% \boldsymbol{0}}\\ \overline{\mathbf{m}}\end{bmatrix}\in R_{q}^{\mu+L},

such that binding is reduced to ${\mathsf{MSIS}}_{\mu,m_{1}+m_{2},B}$ , while hiding is reduced to ${\mathsf{MLWE}}_{\lambda,\mu+L,\chi}$ .

Assume $\left\|\overline{\mathbf{s}}_{1}\right\|_{2}\leq\alpha$ and $\left\|\overline{\mathbf{s}}_{2}\right\|_{\infty}\leq\nu$ . By $\left\|\mathsf{rot}(\mathbf{c})\right\|_{2}\leq\eta$ from lemma 4.14.2, the $\ell_{2}$ -norm bound for the centering shifts are $T_{1}:=\eta\alpha$ and $T_{2}:=\eta\nu\sqrt{m_{2}d}$ . Choose $\gamma_{1},\gamma_{2}>0$ , and thus $s_{i}:=\gamma_{i}T_{i}$ and $M_{i}:=\exp\left(14/\gamma_{i}+1/(2\gamma_{i}^{2})\right)$ in eq. 4.56.

Combining the proof of opening for Ajtai [Ajt96] and [BDL+18b], a three move ABDLOP proof of opening follows:

•

The prover samples $\overline{\mathbf{y}}_{1}\leftarrow D_{s_{1}}^{m_{1}d}$ and $\overline{\mathbf{y}}_{2}\leftarrow D_{s_{2}}^{m_{2}d}$ , and sends over $\overline{\mathbf{w}}\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1}+\mathbf% {A}_{2}\overline{\mathbf{y}}_{2}$ .
•

The verifier challenges by $\mathbf{c}\leftarrow\mathcal{C}$ defined in eq. 4.53.
•

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

The verifier checks shortness $\left\|\overline{\mathbf{z}}_{1}\right\|_{2}\leq s_{1}\sqrt{2m_{1}d}$ , $\left\|\overline{\mathbf{z}}_{2}\right\|_{2}\leq s_{2}\sqrt{2m_{2}d}$ , and

$\overline{\mathbf{w}}+\mathbf{c}\cdot\overline{\mathbf{t}}_{A}=\mathbf{A}_{1}% \overline{\mathbf{z}}_{1}+\mathbf{A}_{2}\overline{\mathbf{z}}_{2}.$

For MSIS hardness reduction for binding, the concrete parameter instantiated is $B=8\eta\sqrt{s_{1}^{2}(2m_{1}d)+s_{2}^{2}(2m_{2}d)}$ . Similar to eqs. 4.10 and 4.21, supposing we have a pair of accepting $(\overline{\mathbf{w}},\overline{\mathbf{v}},\mathbf{c},\overline{\mathbf{z}}_% {1},\overline{\mathbf{z}}_{2})$ and $(\overline{\mathbf{w}},\overline{\mathbf{v}},\mathbf{c}^{\prime},\overline{% \mathbf{z}}_{1}^{\prime},\overline{\mathbf{z}}_{2}^{\prime})$ , then let $\Delta\mathbf{c}:=\mathbf{c}-\mathbf{c}^{\prime}$ , $\Delta\overline{\mathbf{z}}_{1}:=\overline{\mathbf{z}}_{1}-\overline{\mathbf{z% }}_{1}^{\prime}$ , and $\Delta\overline{\mathbf{z}}_{1}:=\overline{\mathbf{z}}_{2}-\overline{\mathbf{z% }}_{2}^{\prime}$ , an extracted relaxed opening has $(\Delta\mathbf{c},\Delta\overline{\mathbf{z}}_{1},\Delta\overline{\mathbf{z}}_% {2},\overline{\mathbf{m}})$ , such that

\Delta\mathbf{c}\begin{bmatrix}\overline{\mathbf{t}}_{A}\\ \overline{\mathbf{t}}_{B}\end{bmatrix}=\begin{bmatrix}\mathbf{A}_{1}\\ \boldsymbol{0}\end{bmatrix}\Delta\overline{\mathbf{z}}_{1}+\begin{bmatrix}% \mathbf{A}_{2}\\ \mathbf{B}\end{bmatrix}\Delta\overline{\mathbf{z}}_{2}+\Delta\mathbf{c}\begin{% bmatrix}\overline{\boldsymbol{0}}\\ \overline{\mathbf{m}}\end{bmatrix},

(4.57)

where the term $\Delta\mathbf{c}\cdot\overline{\mathbf{m}}=\Delta\mathbf{c}\cdot\overline{% \mathbf{t}}_{B}-\mathbf{B}\Delta\overline{\mathbf{z}}_{2}$ . Given relaxed openings $(\Delta\mathbf{c},\Delta\overline{\mathbf{z}}_{1},\Delta\overline{\mathbf{z}}_% {2},\overline{\mathbf{m}})$ and $(\Delta\mathbf{c}^{\prime},\Delta\overline{\mathbf{z}}_{1}^{\prime},\Delta% \overline{\mathbf{z}}_{2}^{\prime},\overline{\mathbf{m}}^{\prime})$ , that at least one of $\Delta\mathbf{c}^{\prime}\Delta\overline{\mathbf{z}}_{1}\neq\Delta\mathbf{c}% \Delta\overline{\mathbf{z}}_{1}^{\prime}$ and $\overline{\mathbf{m}}\neq\overline{\mathbf{m}}^{\prime}$ is true, then

\overline{\boldsymbol{0}}=\begin{bmatrix}\mathbf{A}_{1}&\mathbf{A}_{2}\\ \boldsymbol{0}&\mathbf{B}\end{bmatrix}\left(\Delta\mathbf{c}^{\prime}\cdot% \begin{bmatrix}\Delta\overline{\mathbf{z}}_{1}\\ \Delta\overline{\mathbf{z}}_{2}\end{bmatrix}-\Delta\mathbf{c}\cdot\begin{% bmatrix}\Delta\overline{\mathbf{z}}_{1}^{\prime}\\ \Delta\overline{\mathbf{z}}_{2}^{\prime}\end{bmatrix}\right)+\Delta\mathbf{c}% \Delta\mathbf{c}^{\prime}\begin{bmatrix}\overline{\boldsymbol{0}}\\ \overline{\mathbf{m}}-\overline{\mathbf{m}}^{\prime}\end{bmatrix},

which gives a solution to the MSIS instance $[\mathbf{A}_{1}\mid\mathbf{A}_{2}]\in R_{q}^{\mu\times(m_{1}+m_{2})}$ in either case. Since for $\overline{\boldsymbol{\beta}}:=\left[\Delta\overline{\mathbf{z}}_{1}^{\mathsf{% T}}~{}|~{}\Delta\overline{\mathbf{z}}_{2}^{\mathsf{T}}\right]^{\mathsf{T}}$ ,

\left\|\overline{\boldsymbol{\beta}}\right\|_{2}\leq 2\sqrt{s_{1}^{2}(2m_{1}d)% +s_{2}^{2}(2m_{2}d)},

and by lemma 4.14.2, $\left\|\mathsf{rot}(\mathbf{c})\right\|_{2}\leq\eta$ for a $\mathbf{c}\in\mathcal{C}$ , thus $\left\|\mathsf{rot}(\Delta\mathbf{c})\right\|_{2}\leq 2\eta$ , which concludes the proof for $B$ derivation.

Now consider a linear relation proof over $R_{q}$ . Consider instantiating from just Ajtai commitment for $\mathbf{R}\overline{\mathbf{s}}_{1}=\overline{\mathbf{u}}$ .

•

The prover samples $\overline{\mathbf{y}}_{1}\leftarrow D_{s_{1}}^{m_{1}d}$ and sends over $\overline{\mathbf{w}}\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1}$ and $\overline{\mathbf{v}}\leftarrow\mathbf{R}\overline{\mathbf{y}}_{1}$ .
•

The verifier challenges by $\mathbf{c}\leftarrow\mathcal{C}$ defined in eq. 4.53.
•

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

The verifier checks shortness $\left\|\overline{\mathbf{z}}_{1}\right\|_{2}\leq s_{1}\sqrt{2m_{1}d}$ and

$\displaystyle\overline{\mathbf{w}}+\mathbf{c}\cdot\overline{\mathbf{t}}$ $\displaystyle=\mathbf{A}_{1}\overline{\mathbf{z}}_{1},$

$\displaystyle\overline{\mathbf{v}}+\mathbf{c}\cdot\overline{\mathbf{u}}$ $\displaystyle=\mathbf{R}\overline{\mathbf{z}}_{1}.$

Continuing on, consider the BDLOP commitment for $\mathbf{R}\overline{\mathbf{m}}=\overline{\mathbf{u}}$ , which is basically $\Pi_{\mathsf{lin}}$ .

•

The prover samples $\overline{\mathbf{y}}_{2}\leftarrow D_{s_{2}}^{m_{2}d}$ and sends over $\overline{\mathbf{w}}\leftarrow\mathbf{A}_{2}\overline{\mathbf{y}}_{2}$ and $\overline{\mathbf{v}}\leftarrow\mathbf{R}\mathbf{B}\overline{\mathbf{y}}_{2}$ .
•

The verifier challenges by $\mathbf{c}\leftarrow\mathcal{C}$ defined in eq. 4.53.
•

The prover runs rejection sampling, and replies $\overline{\mathbf{z}}_{2}\leftarrow\overline{\mathbf{y}}_{2}+\mathbf{c}\cdot% \overline{\mathbf{s}}_{2}$ .
•

The verifier checks shortness $\left\|\overline{\mathbf{z}}_{2}\right\|_{2}\leq s_{2}\sqrt{2m_{2}d}$ and

$\begin{bmatrix}\overline{\mathbf{w}}\\ \overline{\mathbf{v}}\end{bmatrix}+\mathbf{c}\cdot\begin{bmatrix}\overline{% \mathbf{t}}_{A}\\ \mathbf{R}\overline{\mathbf{t}}_{B}\end{bmatrix}=\begin{bmatrix}\mathbf{A}_{2}% \\ \mathbf{R}\mathbf{B}\end{bmatrix}\overline{\mathbf{z}}_{2}+\mathbf{c}\cdot% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{u}\end{bmatrix}.$

Hence, we can somehow merge them together for the statement $\mathbf{R}_{1}\overline{\mathbf{s}}_{1}+\mathbf{R}_{2}\overline{\mathbf{m}}=% \overline{\mathbf{u}}$ by

•

The prover samples $\overline{\mathbf{y}}_{1}\leftarrow D_{s_{1}}^{m_{1}d}$ , $\overline{\mathbf{y}}_{2}\leftarrow D_{s_{2}}^{m_{2}d}$ and sends over $\overline{\mathbf{w}}\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1}+\mathbf% {A}_{2}\overline{\mathbf{y}}_{2}$ and $\overline{\mathbf{v}}\leftarrow\mathbf{R}_{2}\mathbf{B}\overline{\mathbf{y}}_{% 2}-\mathbf{R}_{1}\overline{\mathbf{y}}_{1}$ .
•

The verifier challenges by $\mathbf{c}\leftarrow\mathcal{C}$ defined in eq. 4.53.
•

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

The verifier checks shortness $\left\|\overline{\mathbf{z}}_{1}\right\|_{2}\leq s_{1}\sqrt{2m_{1}d}$ , $\left\|\overline{\mathbf{z}}_{2}\right\|_{2}\leq s_{2}\sqrt{2m_{2}d}$ , and

$\begin{bmatrix}\overline{\mathbf{w}}\\ \overline{\mathbf{v}}\end{bmatrix}+\mathbf{c}\cdot\begin{bmatrix}\overline{% \mathbf{t}}_{A}\\ \mathbf{R}_{2}\overline{\mathbf{t}}_{B}\end{bmatrix}+\begin{bmatrix}\overline{% \boldsymbol{0}}\\ \mathbf{R}_{1}\overline{\mathbf{z}}_{1}\end{bmatrix}=\begin{bmatrix}\mathbf{A}% _{1}\\ \boldsymbol{0}\end{bmatrix}\overline{\mathbf{z}}_{1}+\begin{bmatrix}\mathbf{A}% _{2}\\ \mathbf{R}_{2}\mathbf{B}\end{bmatrix}\overline{\mathbf{z}}_{2}+\mathbf{c}\cdot% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{u}\end{bmatrix}.$

Hence, a relaxed opening $(\Delta\mathbf{c},\Delta\overline{\mathbf{z}}_{1},\Delta\overline{\mathbf{z}}_% {2},\overline{\mathbf{m}})$ satisfies eq. 4.57, $\left\|\Delta\overline{\mathbf{z}}_{1}\right\|_{2}\leq 2s_{1}\sqrt{2m_{1}d}$ , $\left\|\Delta\overline{\mathbf{z}}_{2}\right\|_{2}\leq 2s_{2}\sqrt{2m_{2}d}$ , and

\mathbf{R}_{1}\Delta\overline{\mathbf{z}}_{1}+\mathbf{R}_{2}\left(\Delta% \mathbf{c}\cdot\overline{\mathbf{m}}\right)=\Delta\mathbf{c}\cdot\overline{% \mathbf{u}}.

Now from the linear relation proof over $R_{q}$ , consider the linear relation proof over $\mathbb{Z}_{q}$ . Consider the inner product performed over the coefficients of polynomial ring via automorphism $\sigma_{-1}$ , that the constant coefficient of $\sigma_{-1}(\mathbf{a})\mathbf{b}$ is the inner product $\langle\overline{a},\overline{b}\rangle$ of coefficients in $\mathbf{a}=\sum a_{i}X^{i}$ and $\mathbf{b}=\sum b_{i}X^{i}$ , allowing for encoding the $Z_{q}$ linear relation over the coefficients: $\langle\sigma_{-1}(\overline{\mathbf{r}}_{1}),\overline{\mathbf{s}}_{1}\rangle% +\langle\sigma_{-1}(\overline{\mathbf{r}}_{2}),\overline{\mathbf{m}}\rangle=% \mathbf{u}$ . Augmenting the BDLOP message for maskings like [ENS20] by

\begin{bmatrix}\overline{\mathbf{t}}_{A}\\ \overline{\mathbf{t}}_{B}\\ \overline{\mathbf{t}}_{g}\end{bmatrix}=\begin{bmatrix}\mathbf{A}_{1}\\ \boldsymbol{0}\\ \boldsymbol{0}\end{bmatrix}\overline{\mathbf{s}}_{1}+\begin{bmatrix}\mathbf{A}% _{2}\\ \mathbf{B}\\ \mathbf{B}_{g}\end{bmatrix}\overline{\mathbf{s}}_{2}+\begin{bmatrix}\overline{% \boldsymbol{0}}\\ \overline{\mathbf{m}}\\ \overline{\mathbf{g}}\end{bmatrix}\in R_{q}^{\mu+L+\rho},

where $\overline{\mathbf{g}}\in R_{q}^{\rho}$ are the masking terms. Start by proving with the $\Pi_{\mathsf{lin}}$ for $R_{q}$ in ABDLOP, with a single repetition:

•

The prover commits $\mathbf{g}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{R_{q}:g_{0}=0\}$ by $\mathbf{t}_{g}\leftarrow\langle\overline{\mathbf{b}}_{g},\overline{\mathbf{s}}% _{2}\rangle+\mathbf{g}$ , and sends $\mathbf{t}_{g}$ over.
•

The verifier challenges by sampling $\gamma\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{Z}_{q}$ .
•
The prover replies $\mathbf{u}^{\prime}\leftarrow\mathbf{g}+\gamma\cdot\mathbf{u}$ , and starts the $\Pi_{\mathsf{lin}}$ with ABDLOP for $\langle\gamma\sigma_{-1}(\overline{\mathbf{r}}_{1}),\overline{\mathbf{s}}_{1}% \rangle+\langle\gamma\sigma_{-1}(\overline{\mathbf{r}}_{2}),\overline{\mathbf{% m}}\rangle+\mathbf{g}=\mathbf{u}^{\prime}$ by
- –
  
  The prover samples $\overline{\mathbf{y}}_{1}\leftarrow D_{s_{1}}^{m_{1}d}$ , $\overline{\mathbf{y}}_{2}\leftarrow D_{s_{2}}^{m_{2}d}$ and replies
  
  $\displaystyle\overline{\mathbf{w}}$ $\displaystyle\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1}+\mathbf{A}_{2}% \overline{\mathbf{y}}_{2},$
  
  $\displaystyle\mathbf{v}$ $\displaystyle\leftarrow\left(\gamma\sigma_{-1}(\overline{\mathbf{r}}_{2})^{% \mathsf{T}}\mathbf{B}+\overline{\mathbf{b}}_{g}^{\mathsf{T}}\right)\overline{% \mathbf{y}}_{2}-\gamma\sigma_{-1}(\overline{\mathbf{r}}_{1})^{\mathsf{T}}% \overline{\mathbf{y}}_{1}.$
- –
  
  The verifier challenges by $\mathbf{c}\leftarrow\mathcal{C}$ defined in eq. 4.53.
- –
  
  The prover runs rejection sampling, and replies $\overline{\mathbf{z}}_{1}\leftarrow\overline{\mathbf{y}}_{1}+\mathbf{c}\cdot% \overline{\mathbf{s}}_{1}$ and $\overline{\mathbf{z}}_{2}\leftarrow\overline{\mathbf{y}}_{2}+\mathbf{c}\cdot% \overline{\mathbf{s}}_{2}$ .

•

The verifier checks shortness $\left\|\overline{\mathbf{z}}_{1}\right\|_{2}\leq s_{1}\sqrt{2m_{1}d}$ , $\left\|\overline{\mathbf{z}}_{2}\right\|_{2}\leq s_{2}\sqrt{2m_{2}d}$ ,

\begin{bmatrix}\overline{\mathbf{w}}\\ \mathbf{v}\end{bmatrix}+\mathbf{c}\cdot\begin{bmatrix}\overline{\mathbf{t}}_{A% }\\ \gamma\sigma_{-1}(\overline{\mathbf{r}}_{2})^{\mathsf{T}}\overline{\mathbf{t}}% _{B}+\mathbf{t}_{g}\end{bmatrix}+\begin{bmatrix}\overline{\boldsymbol{0}}\\ \gamma\sigma_{-1}(\overline{\mathbf{r}}_{1})^{\mathsf{T}}\overline{\mathbf{z}}% _{1}\end{bmatrix}=\begin{bmatrix}\mathbf{A}_{1}\\ \boldsymbol{0}\end{bmatrix}\overline{\mathbf{z}}_{1}+\begin{bmatrix}\mathbf{A}% _{2}\\ \gamma\sigma_{-1}(\overline{\mathbf{r}}_{2})^{\mathsf{T}}\mathbf{B}+\overline{% \mathbf{b}}_{g}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}_{2}+\mathbf{c}% \cdot\begin{bmatrix}\overline{\boldsymbol{0}}\\ \mathbf{u}^{\prime}\end{bmatrix},

and the constant term satisfies $u^{\prime}_{0}=\gamma u_{0}$ .

For multiple linear relations, apply random linear combination over $\mathbb{Z}_{q}$ under the same mask $\mathbf{g}$ , with soundness $q_{1}^{-1}$ , say any CRT slot under the split by $\mathbb{Z}_{q}=\prod\mathbb{Z}_{q_{i}}$ is wrong, the uniformly random challenges that are independently sampled can fix up that slot with probability at most $q_{1}^{-1}$ by Schwartz-Zippel. The random linear combination over multiple linear relations is similar to the style in [ALS20] for multiple product relations.

When repetitions are greater than once, a straightforward way is to make $\rho$ exactly the number of repetitions. But a closer observation would be, given that $R_{q}$ at least has 2 automorphisms, we can use the automorphism filtering from [ENS20], such that a masking can hold 2 repetitions by $\mathbf{g}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{R_{q}:g_{0}=g_{1}% =0\}$ .

We show by 1 linear relation with 2 $\gamma$ challenges setting:

•

The prover commits $\mathbf{g}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{R_{q}:g_{0}=g_{1}% =0\}$ by $\mathbf{t}_{g}\leftarrow\langle\overline{\mathbf{b}}_{g},\overline{\mathbf{s}}% _{2}\rangle+\mathbf{g}$ , and sends $\mathbf{t}_{g}$ over.
•

The verifier challenges by sampling $\gamma_{0},\gamma_{1}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{% Z}_{q}$ .
•
The prover replies

$\mathbf{u}^{\prime}\leftarrow\mathbf{g}+\frac{\gamma_{0}+\gamma_{1}X}{2}\cdot F% _{2}\left(\mathbf{u}\right),$

and starts the $\Pi_{\mathsf{lin}}$ with ABDLOP for

$\mathbf{g}+\frac{\gamma_{0}+\gamma_{1}X}{2}\cdot F_{2}\left(\langle\sigma_{-1}% (\overline{\mathbf{r}}_{1}),\overline{\mathbf{s}}_{1}\rangle+\langle\sigma_{-1% }(\overline{\mathbf{r}}_{2}),\overline{\mathbf{m}}\rangle\right),$

where $F_{2}$ is defined in eq. 4.36, by
- –
  
  The prover samples $\overline{\mathbf{y}}_{1,0},\overline{\mathbf{y}}_{1,1}\leftarrow D_{s_{1}}^{m% _{1}d}$ , $\overline{\mathbf{y}}_{2,0},\overline{\mathbf{y}}_{2,1}\leftarrow D_{s_{2}}^{m% _{2}d}$ , computes
  
  $\boldsymbol{\alpha}\leftarrow 2^{-1}\sum_{i\in[0,1]}\sigma_{d+1}^{-i}\left(% \sigma_{-1}(\overline{\mathbf{r}}_{2})^{\mathsf{T}}\mathbf{B}\overline{\mathbf% {y}}_{2,i}-\sigma_{-1}(\overline{\mathbf{r}}_{1})^{\mathsf{T}}\overline{% \mathbf{y}}_{1,i}\right),$
  
  and replies
  
  $\displaystyle\overline{\mathbf{w}}_{i}$ $\displaystyle\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1,i}+\mathbf{A}_{2% }\overline{\mathbf{y}}_{2,i},$
  
  $\displaystyle\mathbf{v}_{i}$ $\displaystyle\leftarrow(\gamma_{0}+\gamma_{1}X)\sigma_{d+1}^{i}(\boldsymbol{% \alpha})+\overline{\mathbf{b}}_{g}^{\mathsf{T}}\overline{\mathbf{y}}_{2,i},$
  
  where $\sigma_{d+1}$ is due to lemma 4.14.1 on $R_{q}$ splitting.
- –
  
  The verifier challenges by $\mathbf{c}\leftarrow\mathcal{C}$ defined in eq. 4.53.
- –
  
  The prover runs rejection sampling, and replies $\overline{\mathbf{z}}_{1,i}\leftarrow\overline{\mathbf{y}}_{1,i}+\sigma_{d+1}^% {i}(\mathbf{c})\cdot\overline{\mathbf{s}}_{1}$ and $\overline{\mathbf{z}}_{2,i}\leftarrow\overline{\mathbf{y}}_{2,i}+\sigma_{d+1}^% {i}(\mathbf{c})\cdot\overline{\mathbf{s}}_{2}$ .

•

The verifier checks shortness $\left\|\overline{\mathbf{z}}_{1,i}\right\|_{2}\leq s_{1}\sqrt{2m_{1}d}$ , $\left\|\overline{\mathbf{z}}_{2,i}\right\|_{2}\leq s_{2}\sqrt{2m_{2}d}$ , automorphism filtering checks for $\Pi_{\mathsf{lin}}$ :

\begin{bmatrix}\mathbf{A}_{1}\\ \boldsymbol{0}\\ -\dfrac{\gamma_{0}+\gamma_{1}X}{2}\sigma_{-1}(\overline{\mathbf{r}}_{1})^{% \mathsf{T}}\end{bmatrix}\overline{\mathbf{z}}_{1,i}+\begin{bmatrix}\mathbf{A}_% {2}\\ \boldsymbol{0}\\ \dfrac{\gamma_{0}+\gamma_{1}X}{2}\sigma_{-1}(\overline{\mathbf{r}}_{2})^{% \mathsf{T}}\mathbf{B}+\overline{\mathbf{b}}_{g}^{\mathsf{T}}\end{bmatrix}% \overline{\mathbf{z}}_{2,i}\\ +\begin{bmatrix}\boldsymbol{0}\\ \sigma_{d+1}^{-1}(\mathbf{A}_{1})\\ -\dfrac{\gamma_{0}+\gamma_{1}X}{2}\sigma_{d+1}^{-1}\left(\sigma_{-1}(\overline% {\mathbf{r}}_{1})^{\mathsf{T}}\right)\end{bmatrix}\sigma_{d+1}^{-1}(\overline{% \mathbf{z}}_{1,1-i})+\begin{bmatrix}\boldsymbol{0}\\ \sigma_{d+1}^{-1}(\mathbf{A}_{2})\\ \dfrac{\gamma_{0}+\gamma_{1}X}{2}\sigma_{d+1}^{-1}\left(\sigma_{-1}(\overline{% \mathbf{r}}_{2})^{\mathsf{T}}\mathbf{B}\right)\end{bmatrix}\sigma_{d+1}^{-1}(% \overline{\mathbf{z}}_{2,1-i})+\sigma_{d+1}^{i}(\mathbf{c})\cdot\begin{bmatrix% }\boldsymbol{0}\\ \boldsymbol{0}\\ \mathbf{u}^{\prime}\end{bmatrix}\\ =\begin{bmatrix}\overline{\mathbf{w}}_{i}\\ \sigma_{d+1}^{-1}(\overline{\mathbf{w}}_{1-i})\\ \mathbf{v}_{i}\end{bmatrix}+\sigma_{d+1}^{i}(\mathbf{c})\begin{bmatrix}% \overline{\mathbf{t}}_{A}\\ \sigma_{d+1}^{-1}(\overline{\mathbf{t}}_{A})\\ \dfrac{\gamma_{0}+\gamma_{1}X}{2}F_{2}\left(\sigma_{-1}(\overline{\mathbf{r}}_% {2})^{\mathsf{T}}\overline{\mathbf{t}}_{B}\right)+\mathbf{t}_{g}\end{bmatrix}

holds for each $i\in[0,1]$ , and the constant term satisfies $u^{\prime}_{i}=\gamma_{i}u_{0}$ .

Quadratic Relation Proof.

Now also consider for quadratic relation proof over ABDLOP, extending from [ALS20]. Considering the quadratic relation proof over BDLOP by the computationally indistinguishable masking in eq. 4.26, the quadratic relation can be extended to arbitrary pair of subset sums of the BDLOP messages by

\begin{split}\overline{\mathbf{f}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{f}}% &=\left(\mathbf{c}\overline{\mathbf{m}}-\mathbf{B}\overline{\mathbf{y}}_{2}% \right)^{\mathsf{T}}\mathbf{R}\left(\mathbf{c}\overline{\mathbf{m}}-\mathbf{B}% \overline{\mathbf{y}}_{2}\right)\\ &=\mathbf{c}^{2}\overline{\mathbf{m}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{% m}}-\mathbf{c}\left(\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{% \mathbf{m}}+\overline{\mathbf{m}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{y}}% \right)+\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{y}},\end% {split}

(4.58)

where $\overline{\mathbf{f}}=\mathbf{c}\overline{\mathbf{m}}-\mathbf{B}\overline{% \mathbf{y}}_{2}$ the computationally indistinguishible masked opening, and $\overline{\mathbf{y}}=\mathbf{B}\overline{\mathbf{y}}_{2}$ . Continuing on, consider the linear terms and the constant terms, we have the relation

\overline{\mathbf{m}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{m}}+\overline{% \mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{m}}+\mathbf{r}_{0}=\boldsymbol{0},

(4.59)

the corresponding masked opening should give

\begin{split}\overline{\mathbf{f}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{f}}% +\mathbf{c}\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{f}}+\mathbf% {c}^{2}\mathbf{r}_{0}&=\left(\mathbf{c}\overline{\mathbf{m}}-\mathbf{B}% \overline{\mathbf{y}}_{2}\right)^{\mathsf{T}}\mathbf{R}\left(\mathbf{c}% \overline{\mathbf{m}}-\mathbf{B}\overline{\mathbf{y}}_{2}\right)+\mathbf{c}% \overline{\mathbf{r}}_{1}^{\mathsf{T}}\left(\mathbf{c}\overline{\mathbf{m}}-% \mathbf{B}\overline{\mathbf{y}}_{2}\right)+\mathbf{c}^{2}\mathbf{r}_{0}\\ &=\mathbf{c}^{2}\left(\overline{\mathbf{m}}^{\mathsf{T}}\mathbf{R}\overline{% \mathbf{m}}+\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{m}}+% \mathbf{r}_{0}\right)-\mathbf{c}\left(\overline{\mathbf{y}}^{\mathsf{T}}% \mathbf{R}\overline{\mathbf{m}}+\overline{\mathbf{m}}^{\mathsf{T}}\mathbf{R}% \overline{\mathbf{y}}+\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{% y}}\right)+\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{y}},% \end{split}

(4.60)

such that the degree-1 term $\mathbf{g}_{0}=-\left(\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{% \mathbf{m}}+\overline{\mathbf{m}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{y}}+% \overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{y}}\right)$ is the additional garbage term to commit.

Now we consider the Ajtai part. Instead of the computationally indistinguishable opening $\overline{\mathbf{f}}=\mathbf{c}\overline{\mathbf{m}}-\overline{\mathbf{y}}$ , we have statistically indistinguishable opening $\overline{\mathbf{z}}=\mathbf{y}_{1}+\mathbf{c}\overline{\mathbf{s}}_{1}$ . Hence, the computation structure in eqs. 4.60 and 4.58 remains if we combine the masks by

\overline{\mathbf{y}}=\begin{bmatrix}-\overline{\mathbf{y}}_{1}\\ \mathbf{B}\overline{\mathbf{y}}_{2}\end{bmatrix},\quad\overline{\mathbf{s}}=% \begin{bmatrix}\overline{\mathbf{s}}_{1}\\ \mathbf{m}\end{bmatrix},

(4.61)

and $\overline{\mathbf{f}}=\mathbf{c}\cdot\overline{\mathbf{s}}-\overline{\mathbf{y}}$ , then eq. 4.60 becomes

\overline{\mathbf{f}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{f}}+\mathbf{c}% \overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{f}}+\mathbf{c}^{2}% \mathbf{r}_{0}=\mathbf{c}^{2}\left(\overline{\mathbf{s}}^{\mathsf{T}}\mathbf{R% }\overline{\mathbf{s}}+\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf% {s}}+\mathbf{r}_{0}\right)-\mathbf{c}\left(\overline{\mathbf{y}}^{\mathsf{T}}% \mathbf{R}\overline{\mathbf{s}}+\overline{\mathbf{s}}^{\mathsf{T}}\mathbf{R}% \overline{\mathbf{y}}+\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{% y}}\right)+\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{y}},

such that the degree-1 term $\mathbf{g}_{0}=-\left(\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{% \mathbf{s}}+\overline{\mathbf{s}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{y}}+% \overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{y}}\right)$ is the additional garbage term to commit.

Hence, a prototype for quadratic relation over ABDLOP commitment scheme follows:

•

The prover samples $\overline{\mathbf{y}}_{1}\leftarrow D_{s_{1}}^{m_{1}d}$ , $\overline{\mathbf{y}}_{2}\leftarrow D_{s_{2}}^{m_{2}d}$ , commits to $\mathbf{g}_{0}$ by $\mathbf{t}_{g}\leftarrow\overline{\mathbf{b}}_{g}^{\mathsf{T}}\overline{% \mathbf{s}}_{2}+\mathbf{g}_{0}$ , and replies

$\displaystyle\overline{\mathbf{w}}$ $\displaystyle\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1}+\mathbf{A}_{2}% \overline{\mathbf{y}}_{2},$

$\displaystyle\mathbf{v}$ $\displaystyle\leftarrow\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{% \mathbf{y}}+\overline{\mathbf{b}}_{g}^{\mathsf{T}}\overline{\mathbf{y}}_{2}.$
•

The verifier challenges by $\mathbf{c}\leftarrow\mathcal{C}$ defined in eq. 4.53.
•

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

The verifier checks shortness $\left\|\overline{\mathbf{z}}_{1}\right\|_{2}\leq s_{1}\sqrt{2m_{1}d}$ , $\left\|\overline{\mathbf{z}}_{2}\right\|_{2}\leq s_{2}\sqrt{2m_{2}d}$ , derives $\mathbf{f}_{g}\leftarrow\overline{\mathbf{b}}_{g}^{\mathsf{T}}\overline{% \mathbf{z}}_{2}-\mathbf{c}\mathbf{t}_{g}$ and

$\overline{\mathbf{f}}\leftarrow\begin{bmatrix}\overline{\mathbf{z}}_{1}\\ \mathbf{c}\overline{\mathbf{t}}_{B}-\mathbf{B}\overline{\mathbf{z}}_{2}\end{% bmatrix},$

and checks by

$\displaystyle\mathbf{A}_{1}\overline{\mathbf{z}}_{1}+\mathbf{A}_{2}\overline{% \mathbf{z}}_{2}$ $\displaystyle=\overline{\mathbf{w}}+\mathbf{c}\overline{\mathbf{t}}_{A}$

$\displaystyle\overline{\mathbf{f}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{f}}% +\mathbf{c}\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{f}}+\mathbf% {c}^{2}\mathbf{r}_{0}+\mathbf{f}_{g}$ $\displaystyle=\mathbf{v}.$

Addtionally, noticing the challenges from $\mathcal{C}$ has $\sigma(\mathbf{c})=\mathbf{c}$ , then the quadratic relation can be extended over all $\overline{\mathbf{s}}$ ’s automorphisms, that the message got expanded to

\overline{\mathbf{s}}=\begin{bmatrix}\{\sigma^{i}(\overline{\mathbf{s}}_{1})\}% _{i\in[0,k-1]}\\ \{\sigma^{i}(\overline{\mathbf{m}})\}_{i\in[0,k-1]}\end{bmatrix},

(4.62)

as each opening has $\sigma^{j}(\overline{\mathbf{z}}_{i})=\sigma^{j}(\overline{\mathbf{y}}_{i})+% \mathbf{c}\cdot\sigma^{j}(\overline{\mathbf{s}}_{i})$ by self-automorphism $\mathbf{c}=\sigma(\mathbf{c})$ , which is similar to the technique for automorphism filtering in eq. 4.40. Then eq. 4.61 can be changed to

\overline{\mathbf{y}}=\begin{bmatrix}\{\sigma^{i}(-\overline{\mathbf{y}}_{1})% \}_{i\in[0,k-1]}\\ \{\sigma^{i}(\mathbf{B}\overline{\mathbf{y}}_{2})\}_{i\in[0,k-1]}\end{bmatrix}% ,\quad\overline{\mathbf{s}}=\begin{bmatrix}\{\sigma^{i}(\overline{\mathbf{s}}_% {1})\}_{i\in[0,k-1]}\\ \{\sigma^{i}(\overline{\mathbf{m}})\}_{i\in[0,k-1]}\end{bmatrix}.

(4.63)

If the prover is honest, the convincing probabilty is approximately

\frac{1}{M_{1}M_{2}}=\exp\left(\frac{14}{\gamma_{1}}+\frac{14}{\gamma_{2}}+% \frac{1}{2\gamma_{1}^{2}}+\frac{1}{2\gamma_{2}^{2}}\right)^{-1}

by eq. 4.55, as we are just using [Lyu12] rejection sampling.

The knowledge soundness analysis is similar to the heavy row argument lemma 4.8.8, but the extractor behavior is described and developed in [ACK21a]. We begin by the expected draws for negative hypergeometric distribution.

Lemma 4.14.4.

Given a bin with $N$ balls of which $M$ are marked. Then the attempts to draw uniformly at random from the bin without replacement until $k\leq M$ marked balls are drawn is distributed according to the negative hypergeometric distribution. The expected number of draws is $k(N+1)/(M+1)$ .

Proof.

The sequence of draws without replacement can be viewed as a permutation of $N$ balls, and we are interested in the number of draws up to the first $k$ marked ones. For an unmarked ball, it can be in one of the $M+1$ positions separated by $M$ marked ones, and there are $k$ of them before the $k^{\mathrm{th}}$ marked one. By the linearity of expectation, the expected number of draws is

k+\left(N-M\right)\cdot\frac{k}{M+1}=\frac{k(N+1)}{M+1}.

∎

An immediate application is, let $\mathbf{H}\in\{0,1\}^{R\times N}$ be the binary matrix for $R$ rows indexed by the prover’s randomness, and the $N$ columns indexed by verifier challenges, then let the $i^{\mathrm{th}}$ row has accepting dencity $\varepsilon_{i}$ , supposing the first draw over the row is accepting, then drawing for the next 2 acceptance is expected to be $2/\varepsilon_{i}$ by lemma 4.14.4. Supposing the extractor aborts if the first draw is rejected, or otherwise it samples uniformly at random the remaining entries of the row without replacement until three acceptances or the row is exhausted, and supposing there are at least 3 acceptance on the row, then

\operatorname*{\mathbb{E}}\left[Q\mid i^{\mathrm{th}}\text{ row}\right]=1\cdot% \left(1-\varepsilon_{i}\right)+\left(1+2/\varepsilon_{i}\right)\cdot% \varepsilon_{i}=3,

and supposing there are less than 3 acceptence on the row, then

\operatorname*{\mathbb{E}}\left[Q\mid i^{\mathrm{th}}\text{ row}\right]=1\cdot% \left(1-\varepsilon_{i}\right)+N\cdot\varepsilon_{i}\leq 3.

Averaging over the prover randomness, we thus have

\operatorname*{\mathbb{E}}\left[Q\right]=\operatorname*{\mathbb{E}}\left[% \operatorname*{\mathbb{E}}\left[Q\mid i^{\mathrm{th}}\text{ row}\right]\right]% \leq 3,

(4.64)

where the success probability is

\sum_{k\in[3,N]}\frac{k}{N}\cdot\delta_{k}=\sum_{k\in[1,N]}\frac{k}{N}\cdot% \delta_{k}-\frac{\delta_{1}}{N}-\frac{2\delta_{2}}{N}=\varepsilon-\frac{\delta% _{1}+2\delta_{2}}{N},

(4.65)

where $\delta_{k}$ is the fraction of rows that have $k$ acceptances, $\varepsilon$ is the fraction of acceptance in $\mathbf{H}$ , and eq. 4.65 is at least $\varepsilon-3/N$ by a coarse analysis, and $\varepsilon-2/N$ by a finer one. Hence, if checks on an entry of $\mathbf{H}$ takes $T$ , and $\varepsilon>2/N$ , then extracting three accepting transcripts by restarting over fresh prover randomness, is at most expected $3T/(\varepsilon-2/N)$ .

Now, in expected $3T/(\varepsilon-2/N)$ time, we have 3 accepting transcripts forked from the same prover randomenss, hence the same first prover message, by $\left(\overline{\mathbf{w}},\mathbf{v},\mathbf{t}_{g},\mathbf{c}_{i},\overline% {\mathbf{z}}_{1,i},\overline{\mathbf{z}}_{2,i}\right)$ for $i\in[0,2]$ .

Let $\Delta\mathbf{c}\leftarrow\mathbf{c}_{0}-\mathbf{c}_{1}$ , $\Delta\overline{\mathbf{z}}_{1}\leftarrow\overline{\mathbf{z}}_{1,0}-\overline% {\mathbf{z}}_{1,1}$ , $\Delta\overline{\mathbf{z}}_{2}\leftarrow\overline{\mathbf{z}}_{2,0}-\overline% {\mathbf{z}}_{2,1}$ , and $\overline{\mathbf{s}}_{1}\leftarrow\Delta\overline{\mathbf{z}}_{1}\cdot\left(% \Delta\mathbf{c}\right)^{-1}$ , $\overline{\mathbf{s}}_{2}\leftarrow\Delta\overline{\mathbf{z}}_{2}\cdot\left(% \Delta\mathbf{c}\right)^{-1}$ . Further, we have $\overline{\mathbf{m}}\leftarrow\overline{\mathbf{t}}_{B}-\mathbf{B}\overline{% \mathbf{s}}_{2}$ and $\mathbf{g}_{0}\leftarrow\mathbf{t}_{g}-\overline{\mathbf{b}}_{g}^{\mathsf{T}}% \overline{\mathbf{s}}_{2}$ , then

\begin{bmatrix}\overline{\mathbf{t}}_{A}\\ \overline{\mathbf{t}}_{B}\\ \overline{\mathbf{t}}_{g}\end{bmatrix}=\begin{bmatrix}\mathbf{A}_{1}\\ \boldsymbol{0}\\ \boldsymbol{0}\end{bmatrix}\overline{\mathbf{s}}_{1}+\begin{bmatrix}\mathbf{A}% _{2}\\ \mathbf{B}\\ \overline{\mathbf{b}}_{g}^{\mathsf{T}}\end{bmatrix}\overline{\mathbf{s}}_{2}+% \begin{bmatrix}\overline{\boldsymbol{0}}\\ \overline{\mathbf{m}}\\ \mathbf{g}_{0}\end{bmatrix},

and $\left\|\Delta\mathbf{c}\right\|_{\infty}\leq 2\kappa$ by eq. 4.53, $\left\|\Delta\overline{\mathbf{z}}_{i}\right\|_{2}\leq 2s_{i}\sqrt{2m_{i}d}$ for $i\in[1,2]$ .

Continuing on, we can have $\overline{\mathbf{y}}_{1}\leftarrow\overline{\mathbf{z}}_{1,0}-\mathbf{c}_{0}% \cdot\overline{\mathbf{s}}_{1}$ , $\overline{\mathbf{y}}_{2}\leftarrow\overline{\mathbf{z}}_{2,0}-\mathbf{c}_{0}% \cdot\overline{\mathbf{s}}_{2}$ , and under the same interpolation,

	$\displaystyle\overline{\mathbf{z}}_{1,0}-\mathbf{c}_{0}\cdot\overline{\mathbf{% s}}_{1}$	$\displaystyle=\overline{\mathbf{z}}_{1,1}-\mathbf{c}_{1}\cdot\overline{\mathbf% {s}}_{1},$
	$\displaystyle\overline{\mathbf{z}}_{2,0}-\mathbf{c}_{0}\cdot\overline{\mathbf{% s}}_{2}$	$\displaystyle=\overline{\mathbf{z}}_{2,1}-\mathbf{c}_{1}\cdot\overline{\mathbf% {s}}_{2}.$

Applying the derived $\overline{\mathbf{s}}_{1}$ , $\overline{\mathbf{s}}_{2}$ , and $\mathbf{c}_{2}$ , against $\overline{\mathbf{z}}_{1,2}$ and $\overline{\mathbf{z}}_{2,2}$ , we have either $\overline{\mathbf{y}}_{1}$ and $\overline{\mathbf{y}}_{2}$ being the masking randomness, or we find a ${\mathsf{MSIS}}_{n,m_{1}+m_{2},B}$ solution for $\left[\mathbf{A}_{1}\mathbf{A}_{2}\right]$ , where $B$ was defined near eq. 4.57, that for $i\in[1,2]$ ,

\overline{\mathbf{u}}_{i}\leftarrow\Delta\mathbf{c}\left(\overline{\mathbf{z}}% _{i,2}-\mathbf{c}_{2}\overline{\mathbf{s}}_{i}-\overline{\mathbf{y}}_{i}\right% )=\Delta\mathbf{c}\left(\overline{\mathbf{z}}_{i,2}-\overline{\mathbf{z}}_{i,0% }\right)+\left(\mathbf{c}_{0}-\mathbf{c}_{2}\right)\Delta\overline{\mathbf{z}}% _{i}

solves $\left[\mathbf{A}_{1}\mathbf{A}_{2}\right]$ by $\mathbf{A}_{1}\overline{\mathbf{u}}_{1}+\mathbf{A}_{2}\overline{\mathbf{u}}_{2% }=\overline{\boldsymbol{0}}$ .

Onwards assuming the MSIS is respected, then derive eq. 4.63, $\mathbf{g}_{0}^{\prime}=-\left(\overline{\mathbf{y}}^{\mathsf{T}}\mathbf{R}% \overline{\mathbf{s}}+\overline{\mathbf{s}}^{\mathsf{T}}\mathbf{R}\overline{% \mathbf{y}}+\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{y}}\right)$ , such that

\begin{bmatrix}1&\mathbf{c}_{0}&\mathbf{c}_{0}^{2}\\ 1&\mathbf{c}_{1}&\mathbf{c}_{1}^{2}\\ 1&\mathbf{c}_{2}&\mathbf{c}_{2}^{2}\end{bmatrix}\begin{bmatrix}\overline{% \mathbf{y}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{y}}+\overline{\mathbf{b}}_% {g}^{\mathsf{T}}\overline{\mathbf{y}}_{2}-\mathbf{v}\\ \mathbf{g}_{0}^{\prime}-\mathbf{g}_{0}\\ \overline{\mathbf{s}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{s}}+\overline{% \mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{s}}+\mathbf{r}_{0}\end{bmatrix}=% \begin{bmatrix}\boldsymbol{0}\\ \boldsymbol{0}\\ \boldsymbol{0}\end{bmatrix}

must hold for the extracted variables. Since pairwise challenge differences are invertible, the Vandermonde matrix is invertible; hence every coefficient is zero, including the claimed quadratic relation.

Many Quadratic Relations Proof.

To instantiate the proof for multiple quadratc relations, we sample uniformly random $\boldsymbol{\mu}_{1},\ldots,\boldsymbol{\mu}_{N}\stackrel{{\scriptstyle\textsc% {r}}}{{\leftarrow}}R_{q}$ and apply linear combination over quadratic relations defined by eq. 4.59.

For soundness analysis, it is similar to the linear combination for multiple linear relations. Recall the soundness error $q_{1}^{-1}$ derived by $\gamma_{1},\ldots,\gamma_{\ell}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow% }}\mathbb{Z}_{q}$ , it was due to $\mathbb{Z}_{q}\cong\prod\mathbb{Z}_{q_{i}}$ , then the random linear combination over a CRT slot being fixed to 0 has probability at most $q_{1}^{-1}$ . Now consider random linear combination over $\boldsymbol{\mu}_{1},\ldots,\boldsymbol{\mu}_{N}\stackrel{{\scriptstyle\textsc% {r}}}{{\leftarrow}}R_{q}$ , over some fixed $\mathbf{e}_{1},\ldots,\mathbf{e}_{N}\in R_{q}$ that are not all zero, then by

R_{q}\cong\prod\left(\mathbb{F}_{q_{i}^{d/2}}\times\mathbb{F}_{q_{i}^{d/2}}% \right),

supposing $q_{i}\equiv 5\mod 8$ makes $R_{q_{i}}\cong\mathbb{F}_{q_{i}^{d/2}}\times\mathbb{F}_{q_{i}^{d/2}}$ , then fixing a nonzero CRT slot has probability at most $q_{1}^{-d/2}$ .

Hence, starting from the extractor that extracts for a single quadratic relation, the knowledge soundness here is $2/N+q_{1}^{-d/2}$ , where the additional term is from some relation is not satisfying.

Consider using the extractor for one quadratic relation. After the first extraction, we have an opening satisfying

\overline{\mathbf{s}}^{\mathsf{T}}\left(\sum\boldsymbol{\mu}_{i}\mathbf{R}_{i}% \right)\overline{\mathbf{s}}+\left(\sum\boldsymbol{\mu}_{i}\overline{\mathbf{r% }}_{1,i}^{\mathsf{T}}\right)\overline{\mathbf{s}}+\sum\boldsymbol{\mu}_{i}% \mathbf{r}_{0,i}=\boldsymbol{0}.

Yet, we cannot rule out the case that some subordinate quadratic relation is not satisfying.

Again, we design an extractor for multiple quadratic relations, utilizing the extractor for one quadratic relation, under the trick by [ACK21a] utilizing lemma 4.14.4. For a fixed opening violating some underlying quadratic relations, it may succeed with probability at most $q_{1}^{-d/2}$ over random linear combination by prior discussion, without breaking MSIS.

Here, the opening is fixed independently of the sampled $\overline{\boldsymbol{\mu}}$ for random linear combination, and a malicious prover capable of producing different openings for the same commitment may instead, choose an opening according to $\overline{\boldsymbol{\mu}}$ . Hence, in this case, $q_{1}^{-d/2}$ does not directly bound the probability of obtaining some invalid opening in one extraction.

We therefore seek a second successful extraction for the same commitment, forked from independently sampled $\overline{\boldsymbol{\mu}}$ . If the two extracted relaxed openings differ, the binding reduction yields an MSIS solution; otherwise, the same openings may still violate some underlying quadratic relations. Hence, a second extraction tells malicious prover being lucky from the case of finding an MSIS solution.

The new extractor invokes the extractor for one quadratic relation, if the first extraction failed, abort immediately; otherwise, restart extraction over independently sampled $\overline{\boldsymbol{\mu}}$ until a success. Let $p$ be the probability of a successful extraction for one quadratic relation, $E$ be the event that the first extraction is successful, and $X$ be the number of invocations for the extractor for one quadratic relation, then the expected number of invocations is

\operatorname*{\mathbb{E}}\left[X\right]=\operatorname*{\mathbb{E}}\left[X\mid E% \right]\Pr\left[E\right]+\operatorname*{\mathbb{E}}\left[X\mid\neg E\right]\Pr% \left[\neg E\right]=\left(1+\frac{1}{p}\right)\cdot p+1\cdot\left(1-p\right)=2.

Hence, by eq. 4.64, the expected runtime of the extractor for one quadratic relation is at most $3T$ , then the expected runtime of the extractor for multiple quadratic relations is at most $6T$ .

For the success probability of such extractor for multiple quadratic relations, there are three disjoint events:

•

$E_{0}$ : Both openings are the same, and all underlying quadratic relations are satisfied.
•

$E_{1}$ : Both openings are the same, but some underlying quadratic relations are violated.
•

$E_{2}$ : The openings are distinct, or an MSIS solution on either extraction.

A prover capable of breaking binding may choose an invalid opening by $\overline{\boldsymbol{\mu}}$ in the first extraction, yet return the same opening in the second extraction. Such an execution does not give an MSIS solution and belongs to $E_{1}$ . We therefore need to bound $\Pr\left[E_{1}\right]$ even for such provers. By the construction of the extractor for multiple quadratic relations,

\Pr\left[E_{0}\vee E_{1}\vee E_{2}\right]=p\geq\varepsilon-\frac{2}{N},

(4.66)

where $\varepsilon$ is the prover’s convincing probability, and eq. 4.66 holds by, on the first successful extration, the second extraction keeps rebooting up to another successful extraction. Hence,

\Pr\left[E_{0}\vee E_{2}\right]=p-\Pr\left[E_{1}\right]\geq\varepsilon-\frac{2% }{N}-\Pr\left[E_{1}\right].

Let $X_{0},X_{1}$ be the random variables for the output of the first and second extraction, and $h_{x}$ be the probability of an extraction gives relaxed opening $x$ , then $h_{\bot}=1-p\leq 1-\varepsilon+2/N$ , and

\Pr\left[X_{1}=x\mid X_{0}=x\right]=\sum_{r\geq 0}(1-p)^{r}h_{x}=\frac{h_{x}}{% p}.

Therefore, summing overall openings that violates some underlynig quadratic relations, we have

\Pr\left[E_{1}\right]=\sum_{x}\Pr\left[X_{1}=x\mid X_{0}=x\right]\Pr\left[X_{0% }=x\right]=\sum_{x}\frac{h_{x}}{p}\cdot h_{x}\leq\frac{q_{1}^{-d/2}}{p}\sum_{x% }h_{x}\leq q_{1}^{-d/2},

the third inequality holds by $h_{x}\leq q_{1}^{-d/2}$ for a fixed invalid opening $x$ , and the last inequality holds by the successful extraction probability, and therefore

\Pr\left[E_{0}\vee E_{2}\right]\geq\varepsilon-\frac{2}{N}-q_{1}^{-d/2}.

Vanishing Constant Coefficient Proof.

We denote the protocol for proving multiple quadratic relations by $\Pi^{2}_{\mathsf{many}}$ . We consider proving multiple quadratic relations, whose evaluations

\overline{\mathbf{s}}^{\mathsf{T}}\mathbf{R}_{i}\overline{\mathbf{s}}+% \overline{\mathbf{r}}_{1,i}^{\mathsf{T}}\overline{\mathbf{s}}+\mathbf{r}_{0,i}

(4.67)

over $\overline{\mathbf{s}}$ defined in eq. 4.62, for $i\in[1,M]$ , have constant coefficients being 0. Write $F_{i}(\overline{\mathbf{s}})$ for eq. 4.67, and extend the BDLOP commitment key by $\mathbf{B}_{g}\in R_{q}^{\lambda\times m_{2}}$ . The protocol proceeds as follows:

•

The prover samples $\overline{\mathbf{g}}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{% \mathbf{a}\in R_{q}:a_{0}=0\}^{\lambda}$ , commits $\overline{\mathbf{t}}_{g}\leftarrow\mathbf{B}_{g}\overline{\mathbf{s}}_{2}+% \overline{\mathbf{g}}$ , and sends $\overline{\mathbf{t}}_{g}$ to the verifier
•

The verifier replies $\boldsymbol{\Gamma}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{Z}% _{q}^{\lambda\times M}$ .
•

The prover computes

$\begin{bmatrix}\mathbf{h}_{1}\\ \vdots\\ \mathbf{h}_{\lambda}\end{bmatrix}\leftarrow\begin{bmatrix}\mathbf{g}_{1}\\ \vdots\\ \mathbf{g}_{\lambda}\end{bmatrix}+\boldsymbol{\Gamma}\begin{bmatrix}F_{1}(% \overline{\mathbf{s}})\\ \vdots\\ F_{M}(\overline{\mathbf{s}})\end{bmatrix},$

and sends $\mathbf{h}_{1},\ldots,\mathbf{h}_{\lambda}$ .
•

Invoke $\Pi^{2}_{\mathsf{many}}$ to prove

$\mathbf{g}_{j}+\sum_{i=1}^{M}\gamma_{j,i}F_{i}(\overline{\mathbf{s}})-\mathbf{% h}_{j}=\boldsymbol{0}$

for $j\in[1,\lambda]$ .
•

The verifier accepts if $\Pi^{2}_{\mathsf{many}}$ accepts and $h_{j,0}=0$ for $j\in[1,\lambda]$ .

Additional quadratic relations over $R_{q}$ over the original committed witness can be included in the same invocation of $\Pi^{2}_{\mathsf{many}}$ , which combines them with the above well-formedness equations.

Similar to the analysis for the multiple quadratic relation proof, the knowledge soundness here is $2/N+q_{1}^{-d/2}+q_{1}^{-\lambda}$ . The extractor rewinds at the $\boldsymbol{\Gamma}$ challenge, and invokes the extractor for multiple quadratic relations. By the [ACK21a] trick, the expected number of invocations to the extractor for multiple quadratic relations is 2, and thus the expected runtime is at most $12T$ . With the same analysis, splitting into 3 disjoint events, the probability of 2 openings being distinct is at most $q_{1}^{-\lambda}$ , completing the soundness analysis.

Proving Norm Bounds.

We begin by a lemmas from [BL17, LNS21] as a motivation. Recall the binomial distribution from fair coin, where $\mathsf{Bin}_{\kappa}$ is a distribution from

\sum_{i\in[1,\kappa]}\left(X_{i}-Y_{i}\right),

where $X_{i}$ and $Y_{i}$ are fair coins over $\{0,1\}$ . We begin with the prototype in [BL17].

Lemma 4.14.5 ( $\ell_{\infty}$ Lower-Tail Bound for Binary Compression [BL17]).

For all $\overline{s}\in\mathbb{Z}_{p}^{k}$ , $\overline{c}^{\prime}\in\{0,1\}^{k}$ , and $y\in\mathbb{Z}_{p}$ , over the randomness of $\overline{c}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{k}$ ,

\Pr\left[\left\|\langle\overline{s},\overline{c}-\overline{c}^{\prime}\rangle+% y\right\|_{\infty}<\frac{1}{2}\left\|\overline{s}\right\|_{\infty}\right]\leq% \frac{1}{2}.

Proof.

Let $F(\overline{c}):=\langle\overline{s},\overline{c}-\overline{c}^{\prime}\rangle+y$ , and $\left\|\overline{s}\right\|_{\infty}=\left|s_{i}\right|$ , then let $\overline{c}^{\prime\prime}$ has $c_{i}$ bit flipped, and

F(\overline{c})-F(\overline{c}^{\prime\prime})=(2c_{i}-1)s_{i},

and hence $\left\|F(\overline{c})-F(\overline{c}^{\prime\prime})\right\|_{\infty}=\left\|% \overline{s}\right\|_{\infty}$ . By triangle inequality, for all $\overline{c}\in\{0,1\}^{k}$ ,

\left\|\overline{s}\right\|_{\infty}\leq\left\|F(\overline{c})\right\|_{\infty% }+\left\|F(\overline{c}^{\prime\prime})\right\|_{\infty},

such that at least one of $\left\|F(\overline{c})\right\|_{\infty}$ and $\left\|F(\overline{c}^{\prime\prime})\right\|_{\infty}$ is at least $\left\|\overline{s}\right\|_{\infty}/2$ , completing the proof. ∎

With lemma 4.14.5, the following result is immediate.

Lemma 4.14.6 ( $\ell_{\infty}$ Lower-Tail Bound for Binomial Compression [BL17, LNS21]).

For all $\overline{s}\in\mathbb{Z}_{p}^{k}$ and $y\in\mathbb{Z}_{p}$ , over the randomness of $\overline{c}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathsf{Bin}_{1}^% {k}$ ,

\Pr\left[\left\|\langle\overline{s},\overline{c}\rangle+y\right\|_{\infty}<% \frac{1}{2}\left\|\overline{s}\right\|_{\infty}\right]\leq\frac{1}{2}.

Proof.

By lemma 4.14.5, we have the claim for the fixed $\overline{c}^{\prime}$ version of claim. By $\overline{c}^{\prime}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^% {k}$ ,

\Pr\left[\left\|\langle\overline{s},\overline{c}^{\prime\prime}\rangle+y\right% \|_{\infty}<\frac{1}{2}\left\|\overline{s}\right\|_{\infty}\right]=% \operatorname*{\mathbb{E}}\left[\Pr\left[\left\|\langle\overline{s},\overline{% c}-\overline{c}^{\prime}\rangle+y\right\|_{\infty}<\frac{1}{2}\left\|\overline% {s}\right\|_{\infty}~{}\middle|~{}\overline{c}^{\prime}\right]\right]\leq\frac% {1}{2},

where $\overline{c}^{\prime\prime}\leftarrow\mathsf{Bin}_{1}^{k}$ , and the inequality holds by lemma 4.14.5, as any probability in the expectation is at most $1/2$ . ∎

The range by lemma 4.14.6 gives a probability bound for the $\ell_{\infty}$ -norm in $[\left\|\overline{s}\right\|_{\infty}/2,k\left\|\overline{s}\right\|_{\infty}]$ , and by lemma 1.4.8, we can show without $y$ that

\Pr\left[\left|\langle\overline{c},\overline{s}\rangle\right|\geq C\sqrt{k}% \left\|\overline{s}\right\|_{\infty}\right]\leq 2\exp\left(-C^{2}/2\right),

and given a concretely sufficiently large $k$ , we can use a large constant $C$ . The form of $y+\langle\overline{s},\overline{c}\rangle$ is useful for the sigma protocol, yet the range of the $\ell_{\infty}$ -norm has a factor of $O(\sqrt{k})$ , which is too large.

Johnson-Lindenstrauss Lemma [JL84], conceptually shows the existence of a linear map $\mathbf{V}\in\mathbb{R}^{\ell\times m}$ sampled over continuous Gaussian distribution, such that for $k$ distinct points in $m$ -dimensional vector space be linearly embedded into $\ell$ -dimensional space, where $\ell=O(\log k)$ , and their distances over $\ell_{2}$ -norm are preserved approximately.

Lemma 4.14.7 (Johnson–Lindenstrauss [JL84]).

Let $S\subseteq\mathbb{R}^{m}$ with $\left|S\right|=k\geq 2$ , and $0<\varepsilon<1$ . There exists $\ell=O(\varepsilon^{-2}\log k)$ and a linear map $\mathbf{V}\in\mathbb{R}^{\ell\times m}$ such that, for all $\overline{x},\overline{y}\in S$ ,

(1-\varepsilon)\left\|\overline{x}-\overline{y}\right\|_{2}^{2}\leq\left\|% \mathbf{V}\overline{x}-\mathbf{V}\overline{y}\right\|_{2}^{2}\leq(1+% \varepsilon)\left\|\overline{x}-\overline{y}\right\|_{2}^{2}.

In [JL84], the lemma 4.14.7 shows the existence of such linear map, and in [IM98] we have a randomized algorithm over Gaussian matrix, such that with high probability, the linear map satisfies the conditions in lemma 4.14.7.

Lemma 4.14.8 (Gaussian Randomized Johnson–Lindenstrauss [IM98]).

Let $S\subseteq\mathbb{R}^{m}$ with $\left|S\right|=k\geq 2$ , and let $\varepsilon,\delta\in(0,1)$ . There exists a constant $C>0$ such that the following holds.

Choose a positive integer

\ell\geq C\varepsilon^{-2}\log(k/\delta),

and sample $\mathbf{V}\in\mathbb{R}^{\ell\times m}$ by independently drawing each entry from $\mathcal{N}(0,1/\ell)$ .

Then, with probability at least $1-\delta$ over $\mathbf{V}$ , simultaneously for all $\overline{x},\overline{y}\in S$ ,

(1-\varepsilon)\left\|\overline{x}-\overline{y}\right\|_{2}^{2}\leq\left\|% \mathbf{V}\overline{x}-\mathbf{V}\overline{y}\right\|_{2}^{2}\leq(1+% \varepsilon)\left\|\overline{x}-\overline{y}\right\|_{2}^{2}.

Achlioptas [Ach03] shows that the same asymptotic dimension bound and distance-preservation guarantee can be obtained using independent random signs.

Lemma 4.14.9 (Sign Randomized Johnson–Lindenstrauss [Ach03]).

The conclusion of lemma 4.14.8 remains valid for entries $V_{i,j}=X_{i,j}/\sqrt{\ell}$ , where the $X_{i,j}$ are sampled independently and uniformly over $\pm 1$ .

In our scenario, we don’t need to handle $k$ points in this case, but we do need to preserve the pairwise difference in Euclidean space. More specifically, we want the distance between a fixed vector and zero preserved approximately. The fixed vector is the witness in the Sigma protocol. We therefore study how closely its projected norm follows its original norm, with high probability.

Gentry et al. [GHL22] use an integer projection from $\mathbf{R}\leftarrow\mathsf{Bin}_{1}^{256\times m}$ to reduce the dimension of the vector whose shortness is to be proved. To obtain concrete norm estimates, they compare this projection with a Gaussian matrix $\mathbf{G}\in\mathbb{R}^{256\times m}$ whose entries are sampled independently from $\mathcal{N}(0,1/2)$ , matching the variance of $\mathsf{Bin}_{1}$ .

For a fixed nonzero vector $\overline{w}\in\mathbb{Z}^{m}$ ,

\frac{2\left\|\mathbf{G}\overline{w}\right\|_{2}^{2}}{\left\|\overline{w}% \right\|_{2}^{2}}\sim\chi^{2}_{256}.

To see this, consider the output of row $i$ :

Y_{i}:=(\mathbf{G}\overline{w})_{i}=\sum_{j=1}^{m}G_{i,j}w_{j}.

A fixed linear combination of independent Gaussian variables is Gaussian. Since $\operatorname*{\mathbb{E}}\left[G_{i,j}\right]=0$ and $\mathrm{Var}\left[G_{i,j}\right]=1/2$ ,

Y_{i}\sim\mathcal{N}\left(0,\frac{1}{2}\sum_{j\in[1,m]}w_{j}^{2}\right)=% \mathcal{N}\left(0,\frac{\left\|\overline{w}\right\|_{2}^{2}}{2}\right).

Moreover, the $Y_{i}$ are independent, since they use independently sampled rows of $\mathbf{G}$ .

Thus, normalizing each output by its standard deviation gives independent standard normal variables

Z_{i}:=\frac{\sqrt{2}}{\left\|\overline{w}\right\|_{2}}Y_{i}\sim\mathcal{N}(0,% 1).

In particular,

\left\|\mathbf{G}\overline{w}\right\|_{2}^{2}=\sum_{i\in[1,256]}Y_{i}^{2}=% \frac{\left\|\overline{w}\right\|_{2}^{2}}{2}\sum_{i\in[1,256]}Z_{i}^{2}.

The factor $\left\|\overline{w}\right\|_{2}^{2}$ therefore cancels:

\frac{2\left\|\mathbf{G}\overline{w}\right\|_{2}^{2}}{\left\|\overline{w}% \right\|_{2}^{2}}=\sum_{i=1}^{256}Z_{i}^{2}\sim\chi^{2}_{256}.

Here, the $256$ degrees of freedom count the independent standard normal variables being squared.

Let $X\sim\chi^{2}_{256}$ . Numerically evaluating its tails gives

\Pr[X<60]\approx 2^{-130.98}<2^{-128},\qquad\Pr[X>674]\approx 2^{-128.30}<2^{-% 128}.

Consequently, the normalization above yields the Gaussian bounds in [GHL22, Fact 3.1]:

\begin{split}\Pr_{\mathbf{G}}\left[\left\|\mathbf{G}\overline{w}\right\|_{2}^{% 2}<30\left\|\overline{w}\right\|_{2}^{2}\right]&=\Pr[X<60]<2^{-128},\\ \Pr_{\mathbf{G}}\left[\left\|\mathbf{G}\overline{w}\right\|_{2}^{2}>337\left\|% \overline{w}\right\|_{2}^{2}\right]&=\Pr[X>674]<2^{-128}.\end{split}

(4.68)

The constants $30$ and $337$ arise by dividing the chi-square thresholds $60$ and $674$ by $2$ .

Gentry et al. [GHL22, Corollary 3.2] then heuristically apply these same bounds to the projection over binomial distribution $\mathbf{R}\leftarrow\mathsf{Bin}_{1}^{256\times m}$ , whose entries have the same variance as those of $\mathbf{G}$ . The Gaussian bounds in eq. 4.68 are exact probability statements; their transfer to the binomial projection is heuristic.

More generally, replacing the Gaussian variance $1/2$ by $\kappa/2$ gives

\frac{2\left\|\mathbf{G}\overline{w}\right\|_{2}^{2}}{\kappa\left\|\overline{w% }\right\|_{2}^{2}}\sim\chi^{2}_{256}.

Under the same Gaussian substitution heuristic, for $\mathbf{R}\leftarrow\mathsf{Bin}_{\kappa}^{256\times m}$ and $X\sim\chi^{2}_{256}$ , LNP [LNP22, Lemma 2.8] obtains

	$\displaystyle\Pr_{\mathbf{R}}\left[\left\\|\mathbf{R}\overline{w}\right\\|_{2}^{% 2}<13\kappa\left\\|\overline{w}\right\\|_{2}^{2}\right]$	$\displaystyle\approx\Pr[X<26]\leq 2^{-256},$
	$\displaystyle\Pr_{\mathbf{R}}\left[\left\\|\mathbf{R}\overline{w}\right\\|_{2}^{% 2}>337\kappa\left\\|\overline{w}\right\\|_{2}^{2}\right]$	$\displaystyle\approx\Pr[X>674]\leq 2^{-128}.$

Here, $\approx$ denotes the heuristic comparison. The smaller lower-tail threshold gives the stronger $2^{-256}$ estimate needed in the subsequent argument.

Lemma 4.14.10 ( $\ell_{2}$ Lower-Tail Bound for Binomial Compression [LNP22]).

Fix $m,p\in\mathbb{Z}^{+}$ and a bound $0<b\leq p/(41m)$ . Let $\overline{w}\in\mathbb{Z}_{p}^{m}$ satisfy $\left\|\overline{w}\right\|_{2}\geq b$ , and $\overline{y}\in\mathbb{Z}_{p}^{256}$ is arbitrary. Norms of residue vectors use centered representatives.

For $\mathbf{R}\leftarrow\mathsf{Bin}_{1}^{256\times m}$ with independent entries, over the randomness of $\mathbf{R}$ ,

\Pr\left[\left\|\mathbf{R}\overline{w}+\overline{y}\bmod p\right\|_{2}<4b% \right]<2^{-128}.

Proof.

We begin by separating out the case where $\left\|\overline{w}\right\|_{\infty}\geq p/(4m)$ . By the given bound condition,

4b\leq\frac{4p}{41m}\leq\frac{p}{8m}.

By lemma 4.14.6, for any row $i\in[1,256]$ , over the randomness of $i^{\mathrm{th}}$ row $\overline{r}_{i}^{\mathsf{T}}$ ,

\Pr\left[\left|\langle\overline{r}_{i},\overline{w}\rangle+y_{i}\right|<\frac{% 1}{2}\left\|\overline{w}\right\|_{\infty}\right]\leq\frac{1}{2}.

All rows must satisfy such event to have the $\ell_{2}$ -norm of the projected vector be at most $4b$ , of at most $2^{-256}$ probability.

Now consider the complementary case $\left\|\overline{w}\right\|_{\infty}<p/(4m)$ . Consider all the computation over $\mathbb{Z}$ rather than $\mathbb{Z}_{p}$ , and let $X_{i}=\langle\overline{r}_{i},\overline{w}\rangle$ , then we have $\left|X_{i}\right|\leq\left\|\overline{w}\right\|_{1}<p/4$ , and thus each $X_{i}+y_{i}$ has $\left|X_{i}+y_{i}\right|<3p/4$ .

With a centered representation, a long $\left|X_{i}+y_{i}\right|>p/2$ has wrapped representation $p/4<\left|X_{i}+y_{i}\bmod p\right|<p/2$ , yet we have $4b\leq p/(8m)<p/4$ , and thus with $\left\|\overline{w}\right\|_{\infty}<p/(4m)$ ,

\Pr\left[\left\|\mathbf{R}\overline{w}+\overline{y}\bmod p\right\|_{2}<4b% \right]=\Pr\left[\left\|\mathbf{R}\overline{w}+\overline{y}\right\|_{2}<4b% \right],

as the settings with rows of large $\ell_{\infty}$ -norm wrapping into $(p/4,p/2)$ are not counted anyways.

Continuing on, we use the MGF trick in Chernoff’s bound, by

	$\displaystyle\Pr\left[\left\\|\mathbf{R}\overline{w}+\overline{y}\right\\|_{2}<4% b\right]$	$\displaystyle=\Pr\left[\sum_{i\in[1,256]}\left(X_{i}+y_{i}\right)^{2}<16b^{2}% \right]\leq\exp\left(16sb^{2}\right)\operatorname*{\mathbb{E}}\left[\prod_{i% \in[1,256]}\exp\left(-s\left(X_{i}+y_{i}\right)^{2}\right)\right]$
		$\displaystyle=\exp\left(16sb^{2}\right)\prod_{i\in[1,256]}\operatorname*{% \mathbb{E}}\left[\exp\left(-s\left(X_{i}+y_{i}\right)^{2}\right)\right]$

for any $s\geq 0$ . We observe that, for a binomial random variable $B\sim\mathsf{Bin}_{1}$ ,

\operatorname*{\mathbb{E}}\left[\exp\left(iuB\right)\right]=\frac{1}{4}\left(% \exp\left(-iu\right)+\exp\left(iu\right)\right)+\frac{1}{2}=\frac{1}{2}\left(% \cos\left(u\right)+1\right)=\cos^{2}\left(u/2\right).

With this result, we can introduce the linear shift $y$ such that

	$\displaystyle\operatorname*{\mathbb{E}}\left[\cos\left(u\left(X_{i}+y_{i}% \right)\right)\right]$	$\displaystyle=\frac{1}{2}\left(\operatorname{\mathbb{E}}\left[\exp\left(ui% \left(X_{i}+y_{i}\right)\right)\right]+\operatorname{\mathbb{E}}\left[\exp% \left(-ui\left(X_{i}+y_{i}\right)\right)\right]\right)=\cos\left(uy_{i}\right)% \prod_{j\in[1,m]}\cos^{2}\left(uw_{j}/2\right)$
		$\displaystyle\leq\prod_{j\in[1,m]}\cos^{2}\left(uw_{j}/2\right)=\operatorname*% {\mathbb{E}}\left[\cos\left(uX_{i}\right)\right].$

Another fact we are using is, let $G\sim\mathcal{N}(0,1)$ and any $t\in\mathbb{R}$ , we have $\operatorname*{\mathbb{E}}\left[\cos\left(tG\right)\right]=\exp\left(-t^{2}/2\right)$ . Taking independent $G$ of $X_{i}$ , we substitute $u=\sqrt{2s}G$ into the preceding inequality and average over $G$ . Since cosine is bounded, we can exchange the order of expectations and obtain

	$\displaystyle\operatorname*{\mathbb{E}}_{X_{i}}\left[\exp\left(-s(X_{i}+y_{i})% ^{2}\right)\right]$	$\displaystyle=\operatorname{\mathbb{E}}_{G}\operatorname{\mathbb{E}}_{X_{i}}% \left[\cos\left(\sqrt{2s}G(X_{i}+y_{i})\right)\right]$
		$\displaystyle\leq\operatorname{\mathbb{E}}_{G}\operatorname{\mathbb{E}}_{X_{% i}}\left[\cos\left(\sqrt{2s}GX_{i}\right)\right]=\operatorname*{\mathbb{E}}_{X% _{i}}\left[\exp\left(-sX_{i}^{2}\right)\right].$

Hence, the shift $y_{i}$ is removed from the upper bound.

Substituting this into the Chernoff bound, and using that the $X_{i}$ have the same distribution, gives

\Pr\left[\left\|\mathbf{R}\overline{w}+\overline{y}\right\|_{2}<4b\right]\leq% \exp\left(16sb^{2}\right)\prod_{i\in[1,256]}\operatorname*{\mathbb{E}}\left[% \exp\left(-sX_{i}^{2}\right)\right]

(4.69)

for every $s\geq 0$ . It remains to bound the expectation for a single row and then choose $s$ .

The next goal is to upper bound $\operatorname*{\mathbb{E}}\left[\exp\left(-sX_{i}^{2}\right)\right]$ such that the $X_{i}$ can be taken out, and it only matters with $\left\|\overline{w}\right\|_{2}$ . We began by the Taylor expansion for $\exp\left(-sa\right)$ over $a$ , that is

\exp\left(-sa\right)\leq 1-sa+\frac{s^{2}a^{2}}{2}.

(4.70)

By the linearity of expectation, we have

\operatorname*{\mathbb{E}}\left[\exp\left(-sX_{i}^{2}\right)\right]\leq 1-s% \operatorname*{\mathbb{E}}\left[X_{i}^{2}\right]+\frac{s^{2}}{2}\operatorname*% {\mathbb{E}}\left[X_{i}^{4}\right].

As was discussed in remark 1.6.39, we can derive the second and fourth moment of $X_{i}$ by

\begin{split}\operatorname*{\mathbb{E}}\left[X_{i}^{2}\right]&=\frac{1}{2}% \left\|\overline{w}\right\|_{2}^{2},\\ \operatorname*{\mathbb{E}}\left[X_{i}^{4}\right]&=\frac{1}{2}\sum_{j\in[1,m]}w% _{j}^{4}+3\cdot\frac{1}{4}\sum_{j\neq k}w_{j}^{2}w_{k}^{2}=\frac{3}{4}\left\|% \overline{w}\right\|_{2}^{4}-\frac{1}{4}\sum_{j\in[1,m]}w_{j}^{4}\leq\frac{3}{% 4}\left\|\overline{w}\right\|_{2}^{4}.\end{split}

(4.71)

By $b\leq\left\|\overline{w}\right\|_{2}$ in lemma, we have $\exp\left(16sb^{2}\right)\leq\exp\left(16s\left\|\overline{w}\right\|_{2}^{2}\right)$ . Writing

t=s\left\|\overline{w}\right\|_{2}^{2}\geq 0,

(4.72)

the loose upper bound is $2^{-52}$ .

To derive a tigher bound from eq. 4.70, we consider coefficients $s\geq A\geq 0,B\geq 0$ such that

\exp\left(-sa\right)\leq 1-Aa+Ba^{2}=F(a),

holds for all $a\geq 0$ , and the degree-2 series expansion upper bounds $\operatorname*{\mathbb{E}}\left[\exp\left(-sa\right)\right]$ tigher.

Averaging both sides by $a=X_{i}^{2}$ ,

	$\displaystyle\operatorname*{\mathbb{E}}\left[\exp\left(-sX_{i}^{2}\right)\right]$	$\displaystyle\leq 1-A\operatorname{\mathbb{E}}\left[X_{i}^{2}\right]+B% \operatorname{\mathbb{E}}\left[X_{i}^{4}\right]\leq 1-A\frac{\left\\|\overline% {w}\right\\|_{2}^{2}}{2}+B\frac{3\left\\|\overline{w}\right\\|_{2}^{4}}{4}$
		$\displaystyle=1-\frac{A}{3}\cdot\frac{3\left\\|\overline{w}\right\\|_{2}^{2}}{2}% +\frac{B}{3}\left(\frac{3\left\\|\overline{w}\right\\|_{2}^{2}}{2}\right)^{2}=% \frac{2}{3}+\frac{1}{3}F\left(\frac{3\left\\|\overline{w}\right\\|_{2}^{2}}{2}% \right).$

By earlier requirement, $F(a)\geq\exp\left(-sa\right)$ , then the upper bound is closest when $F(c)=\exp\left(-sc\right)$ when $c=3\left\|\overline{w}\right\|_{2}^{2}/2$ , and it is they are not intersecting at $c$ . Hence,

\begin{cases}1-Ac+Bc^{2}=\exp(-sc),\\ -A+2Bc=-s\exp(-sc).\end{cases}

(4.73)

We therefore obtain

B=\frac{1-(1+sc)\exp(-sc)}{c^{2}},\qquad A=\frac{2-(2+sc)\exp(-sc)}{c}.

We first verify $s-A\geq 0$ . Put $x=sc\geq 0$ . Then

s-A=\frac{x-2+(x+2)\exp(-x)}{c}.

(4.74)

The numerator vanishes at $x=0$ , and its derivative is

1-(1+x)\exp(-x)\geq 0,

since $\exp(x)\geq 1+x$ . Thus $A\leq s$ .

To verify the upper bound throughout the domain, let

H(a)=F(a)-\exp(-sa).

Our construction gives

H(0)=H(c)=H^{\prime}(c)=0.

If $s=0$ , then $A=B=0$ and $H$ is identically zero. Otherwise, $H^{\prime\prime\prime}(a)=s^{3}\exp(-sa)>0$ , so $H^{\prime}$ is strictly convex.

Since $H(0)=H(c)$ , Rolle’s theorem gives some $r\in(0,c)$ with $H^{\prime}(r)=0$ . Together with $H^{\prime}(c)=0$ , strict convexity implies that $H^{\prime}$ is negative between $r$ and $c$ , and positive outside this interval. Therefore, $H$ increases from $H(0)=0$ to $H(r)$ , decreases back to $H(c)=0$ , and increases thereafter. Consequently, $H(a)\geq 0$ for all $a\geq 0$ .

Again let $t=s\left\|\overline{w}\right\|_{2}^{2}$ , and we are at $2^{-96}$ for an upper bound.

To further improve the bound, we use a degree- $4$ polynomial and moments up to order $8$ . For $t=s\left\|\overline{w}\right\|_{2}^{2}\geq 0$ ,

F_{4}(a)=1-A_{4}a+B_{4}a^{2}-C_{4}a^{3}+D_{4}a^{4},

(4.75)

where

	$\displaystyle A_{4}$	$\displaystyle=\frac{1}{\left\\|\overline{w}\right\\|_{2}^{2}}\left(\frac{5}{2}-% \left(\frac{64}{27}+\frac{16t}{9}\right)\exp\left(-t\right)-\left(\frac{7}{54}% +\frac{t}{9}\right)\exp\left(-4t\right)\right),$
	$\displaystyle B_{4}$	$\displaystyle=\frac{1}{\left\\|\overline{w}\right\\|_{2}^{4}}\left(\frac{33}{16}% -\left(\frac{16}{9}+\frac{8t}{3}\right)\exp\left(-t\right)-\left(\frac{41}{144% }+\frac{t}{4}\right)\exp\left(-4t\right)\right),$
	$\displaystyle C_{4}$	$\displaystyle=\frac{1}{\left\\|\overline{w}\right\\|_{2}^{6}}\left(\frac{5}{8}-% \left(\frac{4}{9}+t\right)\exp\left(-t\right)-\left(\frac{13}{72}+\frac{t}{6}% \right)\exp\left(-4t\right)\right),$
	$\displaystyle D_{4}$	$\displaystyle=\frac{1}{\left\\|\overline{w}\right\\|_{2}^{8}}\left(\frac{1}{16}-% \left(\frac{1}{27}+\frac{t}{9}\right)\exp\left(-t\right)-\left(\frac{11}{432}+% \frac{t}{36}\right)\exp\left(-4t\right)\right).$

For all $a\geq 0$ , we have

\exp\left(-sa\right)\leq F_{4}(a).

Averaging both sides with $a=X_{i}^{2}$ and using the moments up to order $8$ ,

\operatorname*{\mathbb{E}}\left[\exp\left(-sX_{i}^{2}\right)\right]\leq% \operatorname*{\mathbb{E}}\left[F_{4}(X_{i}^{2})\right]\leq\frac{137}{256}+% \left(\frac{191}{432}+\frac{5t}{144}\right)\exp\left(-t\right)+\left(\frac{157% }{6912}-\frac{t}{576}\right)\exp\left(-4t\right).

Using $b\leq\left\|\overline{w}\right\|_{2}$ , we upper bound by $2^{-144}$ . A construction with touching points derived from the moments, including its coefficient derivation and binomial correction analysis, is given in appendix A. This is mainly AI’s work, I cannot pull it off myself. ∎

TODO: Stuffs for [LNP22].

TODO: Write a short note on rigorous replacements for the projection bounds in [LNP22, Lemmas 2.8–2.9]. Use the exact representation of $\mathsf{Bin}_{\kappa}$ as a sum of independent signs scaled by $1/2$ and [Ach03, Eq. (13)] to write up the upper-tail bound replacing $337$ by $343$ , with error below $2^{-128}$ . Combine it with the shifted modular lower-tail bound in lemma 4.14.10 and its moment analysis in appendix A, then track the resulting completeness and soundness parameters in Section 5 of [LNP22].

	$\displaystyle\overline{\mathbf{w}}+\mathbf{c}\cdot\overline{\mathbf{t}}$	$\displaystyle=\mathbf{A}_{1}\overline{\mathbf{z}}_{1},$
	$\displaystyle\overline{\mathbf{v}}+\mathbf{c}\cdot\overline{\mathbf{u}}$	$\displaystyle=\mathbf{R}\overline{\mathbf{z}}_{1}.$

	$\displaystyle\overline{\mathbf{w}}$	$\displaystyle\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1}+\mathbf{A}_{2}% \overline{\mathbf{y}}_{2},$
	$\displaystyle\mathbf{v}$	$\displaystyle\leftarrow\left(\gamma\sigma_{-1}(\overline{\mathbf{r}}_{2})^{% \mathsf{T}}\mathbf{B}+\overline{\mathbf{b}}_{g}^{\mathsf{T}}\right)\overline{% \mathbf{y}}_{2}-\gamma\sigma_{-1}(\overline{\mathbf{r}}_{1})^{\mathsf{T}}% \overline{\mathbf{y}}_{1}.$

	$\displaystyle\overline{\mathbf{w}}_{i}$	$\displaystyle\leftarrow\mathbf{A}_{1}\overline{\mathbf{y}}_{1,i}+\mathbf{A}_{2% }\overline{\mathbf{y}}_{2,i},$
	$\displaystyle\mathbf{v}_{i}$	$\displaystyle\leftarrow(\gamma_{0}+\gamma_{1}X)\sigma_{d+1}^{i}(\boldsymbol{% \alpha})+\overline{\mathbf{b}}_{g}^{\mathsf{T}}\overline{\mathbf{y}}_{2,i},$

	$\displaystyle\mathbf{A}_{1}\overline{\mathbf{z}}_{1}+\mathbf{A}_{2}\overline{% \mathbf{z}}_{2}$	$\displaystyle=\overline{\mathbf{w}}+\mathbf{c}\overline{\mathbf{t}}_{A}$
	$\displaystyle\overline{\mathbf{f}}^{\mathsf{T}}\mathbf{R}\overline{\mathbf{f}}% +\mathbf{c}\overline{\mathbf{r}}_{1}^{\mathsf{T}}\overline{\mathbf{f}}+\mathbf% {c}^{2}\mathbf{r}_{0}+\mathbf{f}_{g}$	$\displaystyle=\mathbf{v}.$

4.14 Lattice Proofs for Exact Euclidean Norm Bounds and Quadratic Relations

Challenge Set.

Lemma 4.14.1.

Proof.

Lemma 4.14.2.

Proof.

Rejection Sampling and Parameters.

Lemma 4.14.3 (Gaussian Tail Bound [Ban93]).

ABDLOP Commitment Scheme.

Quadratic Relation Proof.

Lemma 4.14.4.

Proof.

Many Quadratic Relations Proof.

Vanishing Constant Coefficient Proof.

Proving Norm Bounds.

Lemma 4.14.5 (ℓ∞ Lower-Tail Bound for Binary Compression [BL17]).

Proof.

Lemma 4.14.6 (ℓ∞ Lower-Tail Bound for Binomial Compression [BL17, LNS21]).

Proof.

Lemma 4.14.7 (Johnson–Lindenstrauss [JL84]).

Lemma 4.14.8 (Gaussian Randomized Johnson–Lindenstrauss [IM98]).

Lemma 4.14.9 (Sign Randomized Johnson–Lindenstrauss [Ach03]).

Lemma 4.14.10 (ℓ2 Lower-Tail Bound for Binomial Compression [LNP22]).

Proof.

Lemma 4.14.5 ( $\ell_{\infty}$ Lower-Tail Bound for Binary Compression [BL17]).

Lemma 4.14.6 ( $\ell_{\infty}$ Lower-Tail Bound for Binomial Compression [BL17, LNS21]).

Lemma 4.14.10 ( $\ell_{2}$ Lower-Tail Bound for Binomial Compression [LNP22]).