4 Various Papers 4.13 Practical Exact Proofs from Lattices 4.15 LaBRADOR

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},

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.62)

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,

where the sucess 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.63)

where $\delta_{k}$ is the fraction of rows that have $k$ acceptances, $\varepsilon$ is the fraction of acceptance in $\mathbf{H}$ , and eq. 4.63 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.62, $\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}

should 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}$ .

TODO: soundness proof for multiple quad relation.

Proving Norm Bounds.

Johnson-Lindenstrauss stuffs

TODO: Stuffs for [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}.$