4 Various Papers 4.18 Lattice-Based Succinct Arguments for NP with Polylog Verification References

4.19 Greco

So the motivation of Greco [Bot24] is to prove the validity of some RLWE ciphertext, more specifically BFV ciphertext [Bra12, FV12] whose ciphertext is improved with CRT [HPS19, KPZ21]. The main idea of Greco is from [dLS19].

Throughout, coefficients in $\mathbb{Z}_{q}$ are lifted to their centered integer representation, unless stated otherwise.

Start with BFV ciphertext [Bra12, FV12] from ${\mathsf{RLWE}}$ over $R_{q}^{2}$ , where $R_{q}=\mathbb{Z}_{q}[X]/\left(X^{n}+1\right)$ . We have

\left(\mathsf{ct}_{0},\mathsf{ct}_{1}\right)=\left(\mathbf{a}\cdot\mathbf{s}+% \mathbf{e}+k,-\mathbf{a}\right),

where $\mathbf{a}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}R_{q}$ , $\mathbf{s}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{-1,0,1\}^{n}$ , $\mathbf{e}\leftarrow\chi^{n}$ , all the computation are carried over $R_{q}$ , and

k=\left\lfloor\frac{q}{t}\left\lfloor m\right\rceil_{t}\right\rceil=\frac{q}{t% }\left\lfloor m\right\rceil_{t}-\frac{1}{t}\left\lfloor mq\right\rceil_{t}\in% \left[-\frac{q}{2},\frac{q}{2}\right)\cap\mathbb{Z},

where $\left\lfloor\cdot\right\rceil$ means rounding to the nearest integer, $\left\lfloor z\right\rceil_{t}$ means centered remainder of $z$ modulo $t$ , and $t$ is the plaintext modulus. With the requirement that $q$ and $t$ are coprime, then

k\equiv-t^{-1}\left\lfloor mq\right\rceil_{t}\mod q,

which was described in [KPZ21]. With a composite ciphertext modulus $q=\prod q_{i}$ , we have CRT splitting such that

\left(\mathsf{ct}_{0},\mathsf{ct}_{1}\right)\cong\left(\left(\mathsf{ct}_{0,0}% ,\mathsf{ct}_{1,0}\right)\mod q_{0},\ldots,\left(\mathsf{ct}_{0,\ell-1},% \mathsf{ct}_{1,\ell-1}\right)\mod q_{\ell-1}\right),

and thus for the plaintext encoding,

k\equiv k_{0,i}k_{1}\mod q_{i},

where $k_{0,i}\equiv-t^{-1}\mod q_{i}$ , and $k_{1}=\left\lfloor mq\right\rceil_{t}$ .

Greco [Bot24] extends from [dLS19] in the CRT modulus splitting setting. The gain is not taking advantage of the parallelism in BFV, but subtly allowing for the circuit arithmetic be simulated over $\mathbb{Z}_{p}$ as if it is over $\mathbb{Z}$ , where $p$ is the order of elliptic curve commitment group, used by for example [KZG10].

Lifting all the polynomial arithmetics from $R_{q_{i}}$ over $\mathbb{Z}[X]$ , then we have

\mathbf{a}_{i}\cdot\mathbf{s}+\mathbf{e}+k_{0,i}k_{1}+\mathbf{r}_{1,i}q_{i}+% \mathbf{r}_{2,i}\left(X^{n}+1\right)=\mathsf{ct}_{0,i}

(4.76)

for all $i\in[0,\ell-1]$ , such that for all $\boldsymbol{\alpha},\boldsymbol{\beta}\in\mathbb{Z}[X]$ ,

\boldsymbol{\alpha}q_{i}+\boldsymbol{\beta}\left(X^{n}+1\right)\equiv% \boldsymbol{0}\mod\left(q_{i},\left(X^{n}+1\right)\right).

(4.77)

Given a sufficiently large modulus $p$ such that the $\ell_{\infty}$ -norm does not wrap around over $\mathbb{Z}_{p}$ , namely the summation of the $\ell_{\infty}$ -norms of both sides of eq. 4.76 is strictly less than $p$ , we can simulate eq. 4.76 over $\mathbb{Z}_{p}[X]$ .

Too Many Range Checks.

We now show how to decrease the number range checks in [Bot24]. Over $\mathbb{Z}[X]$ , let

\mathbf{d}_{i}=\mathsf{ct}_{0,i}-\left(\mathbf{a}_{i}\cdot\mathbf{s}+\mathbf{e% }+k_{0,i}k_{1}\right)\in\mathbb{Z}[X],

(4.78)

which must be of form $\boldsymbol{\alpha}_{i}\left(X^{n}+1\right)+\boldsymbol{\beta}_{i}$ , as $X^{n}+1$ is monic, division over $\mathbb{Z}[X]$ gives unique quotient and remainder $\boldsymbol{\alpha}_{i},\boldsymbol{\beta}_{i}\in\mathbb{Z}[X]$ , $\deg\boldsymbol{\alpha}_{i}\leq n-2$ , and $\deg\boldsymbol{\beta}_{i}\leq n-1$ . For accepting relations, namely vaild ciphertexts, we have

\mathbf{d}_{i}\equiv\boldsymbol{0}\mod\left(q_{i},\left(X^{n}+1\right)\right),

then by eq. 4.77, $\boldsymbol{\beta}_{i}=q_{i}\boldsymbol{\gamma}_{i}$ for some $\boldsymbol{\gamma}_{i}\in\mathbb{Z}[X]$ where $\deg\boldsymbol{\gamma}_{i}\leq n-1$ . Therefore, $\mathbf{d}_{i}=\boldsymbol{\alpha}_{i}\left(X^{n}+1\right)+q_{i}\boldsymbol{% \gamma}_{i}$ .

Greco let $\mathbf{r}_{2,i}$ be center reprepresented over $\mathbb{Z}_{q_{i}}[X]$ . We thus write $\boldsymbol{\alpha}_{i}=\left\lfloor\boldsymbol{\alpha}_{i}\right\rceil_{q_{i}% }+q_{i}\mathbf{u}_{2,i}$ for some $\mathbf{u}_{2,i}\in\mathbb{Z}[X]$ , then

	$\displaystyle\mathbf{d}_{i}$	$\displaystyle=\boldsymbol{\alpha}_{i}\left(X^{n}+1\right)+q_{i}\boldsymbol{% \gamma}_{i}=\left(\left\lfloor\boldsymbol{\alpha}_{i}\right\rceil_{q_{i}}+q_{i% }\mathbf{u}_{2,i}\right)\left(X^{n}+1\right)+q_{i}\boldsymbol{\gamma}_{i}$
		$\displaystyle=\left\lfloor\boldsymbol{\alpha}_{i}\right\rceil_{q_{i}}\left(X^{% n}+1\right)+q_{i}\left(\mathbf{u}_{2,i}\left(X^{n}+1\right)+\boldsymbol{\gamma% }_{i}\right).$

Essentially, the identity exhibits a witness pair with $\mathbf{r}_{2,i}$ centered modulo $q_{i}$ , and the compensating multiple of $X^{n}+1$ in $\mathbf{r}_{1,i}$ . Therefore, their $\deg\mathbf{r}_{1,i}$ is upper bounded by $2n-2$ .

It means for the $\mathbf{r}_{1,i}$ and $\mathbf{r}_{2,i}$ , there are $3n-2$ elements range checked per $q_{i}$ by Greco, which is the same as [dLS19]. As of the ranges,

•

For $\mathbf{r}_{2,i}$ with centered representation modulo $q_{i}$ , we have

$\left\|\mathbf{r}_{2,i}\right\|_{\infty}\leq\frac{q_{i}-1}{2}.$ (4.79)
•

For $\mathbf{r}_{1,i}$ , we consider the following over $\mathbb{Z}[X]$ :

$\mathbf{r}_{1,i}=q_{i}^{-1}\left(\mathsf{ct}_{0,i}-\left(\mathbf{a}_{i}\cdot% \mathbf{s}+\mathbf{e}+k_{0,i}k_{1}\right)-\mathbf{r}_{2,i}\left(X^{n}+1\right)% \right),$

and let $\mathbf{e}$ be $B$ -bounded. The $\mathsf{ct}_{0,i}-\left(\mathbf{a}_{i}\cdot\mathbf{s}+\mathbf{e}+k_{0,i}k_{1}\right)$ has $\ell_{\infty}$ -norm bounded by

$D_{i}=\frac{q_{i}-1}{2}+n\frac{q_{i}-1}{2}+B+\left|k_{0,i}\right|\cdot\frac{t-% 1}{2},$ (4.80)

as $k_{0,i}$ can be publicly derived, $\mathbf{a}_{i}$ and $k_{1}$ are centered represented, $\mathbf{e}$ is not long enough to wrap back, and

$\left\|\mathbf{r}_{2,i}\left(X^{n}+1\right)\right\|_{\infty}=\left\|\mathbf{r}% _{2,i}\right\|_{\infty}\leq\frac{q_{i}-1}{2}$

as $\deg\mathbf{r}_{2,i}\leq n-2$ . Hence,

$\left\|\mathbf{r}_{1,i}\right\|_{\infty}\leq q_{i}^{-1}\left(\frac{q_{i}-1}{2}% +n\frac{q_{i}-1}{2}+B+\left|k_{0,i}\right|\cdot\frac{t-1}{2}+\frac{q_{i}-1}{2}% \right)=q_{i}^{-1}\left((n+2)\cdot\frac{q_{i}-1}{2}+B+\left|k_{0,i}\right|% \cdot\frac{t-1}{2}\right).$ (4.81)

To ensure that $p$ is sufficiently large for the relation over $\mathbb{Z}[X]$ , such that the polynomial relation is simulatable over $\mathbb{Z}_{p}[X]$ , we require the summation of the $\ell_{\infty}$ -norms of both sides of the equation to be not exceeding $p$ by

p>2\left((n+2)\cdot\frac{q_{i}-1}{2}+B+\left|k_{0,i}\right|\cdot\frac{t-1}{2}% \right).

(4.82)

To sum up, we have bounds for $\mathbf{r}_{1,i}$ and $\mathbf{r}_{2,i}$ in eqs. 4.81 and 4.79 from eq. 4.82 for [Bot24, dLS19].

It is worth noticing the following fact about polynomial product over $\mathbb{Z}[X]$ and modulo $X^{n}+1$ .

Lemma 4.19.1.

Let $\mathbf{f},\mathbf{g}\in\mathbb{Z}[X]$ have $\deg\mathbf{f}\leq n-1$ and $\deg\mathbf{g}\leq n-1$ , then

	$\displaystyle\left\\|\mathbf{f}\mathbf{g}\right\\|_{\infty}$	$\displaystyle\leq n\left\\|\mathbf{f}\right\\|_{\infty}\left\\|\mathbf{g}\right\\|% _{\infty},$
	$\displaystyle\left\\|\mathbf{f}\mathbf{g}\mod\left(X^{n}+1\right)\right\\|_{\infty}$	$\displaystyle\leq n\left\\|\mathbf{f}\right\\|_{\infty}\left\\|\mathbf{g}\right\\|% _{\infty}.$

Proof.

For $\mathbf{f}\mathbf{g}$ product over $\mathbb{Z}[X]$ ,

\left\|\mathbf{f}\mathbf{g}\right\|_{\infty}\leq\sum_{j\in[0,n-1]}\left|f_{j}% \right|\left\|X^{j}\mathbf{g}\right\|_{\infty}=\sum_{j\in[0,n-1]}\left|f_{j}% \right|\left\|\mathbf{g}\right\|_{\infty}\leq n\left\|\mathbf{f}\right\|_{% \infty}\left\|\mathbf{g}\right\|_{\infty}.

For $\mathbf{f}\mathbf{g}\mod\left(X^{n}+1\right)$ product over $\mathbb{Z}[X]$ ,

\left\|\mathbf{f}\mathbf{g}\mod\left(X^{n}+1\right)\right\|_{\infty}\leq\sum_{% j\in[0,n-1]}\left|f_{j}\right|\left\|X^{j}\mathbf{g}\mod\left(X^{n}+1\right)% \right\|_{\infty}=\sum_{j\in[0,n-1]}\left|f_{j}\right|\left\|\mathbf{g}\right% \|_{\infty}\leq n\left\|\mathbf{f}\right\|_{\infty}\left\|\mathbf{g}\right\|_{% \infty}.

∎

We use independently supplied witnesses $\mathbf{r}_{1,i},\mathbf{r}_{2,i}$ with $\deg\mathbf{r}_{1,i}\leq n-1$ and $\deg\mathbf{r}_{2,i}\leq n-2$ . It suffices to check the full polynomial relation eq. 4.76 over $\mathbb{Z}[X]$ by

•

checking $q_{i}\mathbf{r}_{1,i}\equiv\mathbf{d}_{i}\mod(X^{n}+1)$ ,
•

and checking $\mathbf{r}_{2,i}=\boldsymbol{\alpha}_{i}$ , where $\boldsymbol{\alpha}_{i}$ is decomposed from $\mathbf{d}_{i}$ .

By lemma 4.19.1, for eq. 4.78, $\left\|\mathbf{d}_{i}\right\|_{\infty}$ and $\left\|\mathbf{d}_{i}\mod(X^{n}+1)\right\|_{\infty}$ share the same $\ell_{\infty}$ -norm bound eq. 4.80, as all other terms have degree at most $n-1$ , while lemma 4.19.1 applies to $\mathbf{a}_{i}\cdot\mathbf{s}$ over $\mathbb{Z}[X]$ . Hence,

\left\|\mathbf{r}_{1,i}\right\|_{\infty}\leq q_{i}^{-1}\left((n+1)\cdot\frac{q% _{i}-1}{2}+B+\left|k_{0,i}\right|\cdot\frac{t-1}{2}\right)=q_{i}^{-1}D_{i}

by eq. 4.80, as $\mathbf{r}_{2,i}(X^{n}+1)$ is filtered out. Then over $\mathbb{Z}[X]/(X^{n}+1)$ , if we relation is simulatable over $\mathbb{Z}_{p}[X]/(X^{n}+1)$ , we need

p>2D_{i}=2\left((n+1)\cdot\frac{q_{i}-1}{2}+B+\left|k_{0,i}\right|\cdot\frac{t% -1}{2}\right).

We pause by a philosophical question: Why do we need range checks here? We are essentially checking a $\mathbb{Z}[X]$ relation over $\mathbb{Z}_{p}[X]$ , and thus all the computation over $\mathbb{Z}$ is within $[-(p-1)/2,(p-1)/2]$ ²⁸²⁸28 Greco [Bot24, dLS19] range checks both $\mathbf{r}_{1,i}$ and $\mathbf{r}_{2,i}$ to instantiate the $p$ lower bound, but it confuses me about the point of range checks. .

•

For $\mathbf{r}_{1,i}$ case, it carries a scalar $q_{i}$ , and thus it needs to be range checked ²⁹²⁹29 Think of an counterexample where $p=101$ , $q_{i}=7$ , and $r=29$ not range checked, for invalid $d=1$ . .
•

But for $\mathbf{r}_{2,i}$ , multiplying with a $X^{n}+1$ , which is monic (highest degree coefficient being 1), and does not scale up the $\ell_{\infty}$ -norm for the coefficients of terms with degree at least $n$ . Hence, for a sufficiently large $p$ by

$p>2D_{i}>2n\left\|\mathbf{a}_{i}\right\|_{\infty}\left\|\mathbf{s}\right\|_{% \infty},$

the equality between $\mathbf{r}_{2,i}$ and $\boldsymbol{\alpha}_{i}$ over $\mathbb{Z}_{p}[X]$ can be lifted to $\mathbb{Z}[X]$ in centered representation without range check.

Therefore, there are only $n$ range checks need to be performed over $\mathbf{r}_{1,i}$ , bounded by $q_{i}^{-1}D_{i}$ , assuming that $p>2D_{i}$ .

Degree-3 Trick Like [BLS19].

Inducing a lookup-based range check for entries in $\mathbf{s}$ is a bit costly. Say $\mathbf{s}\in\{-1,0,1\}^{n}$ , then each entries can be made into

\left(s_{i}-1\right)s_{i}\left(s_{i}+1\right)=0,

which is not exactly the same, but in the same spirit as [BLS19].

TODO: … [Bot24]

	$\displaystyle\left\\|\mathbf{f}\mathbf{g}\right\\|_{\infty}$	$\displaystyle\leq n\left\\|\mathbf{f}\right\\|_{\infty}\left\\|\mathbf{g}\right\\|% _{\infty},$
	$\displaystyle\left\\|\mathbf{f}\mathbf{g}\mod\left(X^{n}+1\right)\right\\|_{\infty}$	$\displaystyle\leq n\left\\|\mathbf{f}\right\\|_{\infty}\left\\|\mathbf{g}\right\\|% _{\infty}.$