# Proof of Encryption

#### BFV setup

Let $Q$ be the ciphertext modulus and $t$ be plaintext modulus. Let $R_Q$ denote the polynomial ring $Z_Q[X]/X^N+1$. In practice we leverage RNS and set $Q = \prod{q_i}$ where $\log q_i < 61$ and the $q_i$ factor are pairwise coprimes. This modiication was suggested by [Bayard et al., 2016](https://eprint.iacr.org/2016/510.pdf) to make arithmetic operations faster as these no longer need to be work with Big integer arithmetic. Note that $Q$ and $t$ are co-prime.

Using the Chinese Remainder Theorem (CRT), an integer $x ∈ Z_Q$ can be represented
by its CRT components $\{ x_i = x \mod q_i \in \mathbb{Z}_{q_i} \}_i$, and operations on $x$ in $Z_Q$ can be implemented by applying the same operations to each CRT component $x_i$ in its own ring $Z_{q_{i}}$.

#### BFV secret key encryption

$$Ct = (Ct_0, Ct_1) = ([A \cdot S + E + K]_Q, A)$$
Where $A \in R_Q, S \in \chi_{key}, E \in \chi_{error}$ and $K = \lceil \frac{Q [M]_t}{t} \rfloor$ **[1]**.

Given that $Q$ and $t$ are co-prime **[2]**, one can calculate $K$ directly in RNS using the equality
$$\lceil \frac{Q [M]_t}{t} \rfloor = \frac{Q[M]_t - [QM]_t}{t} = -t^{-1}[QM]_t \mod q_i$$

We will denote $-t^{-1}$ with $K^{0}$ as the negative of the multplicative inverse of $t \mod q_i$ mod and $[QM]_t$ with $K^1$.

Therefore,
$$Ct_0 = A\cdot S + E + K^{0}K^1 \mod {R_{q_i}}$$

Therefore,
$$Ct_0 = A\cdot S + E + K^{0}K^1$$

#### Proof of valid encryption

*TODO*: Encryption works over rings. Explain the challenges of performing such operations inside a zkSNARK

Let $p$ be the order of group $G$. Recall that $Q = \prod q_i$ where $\log{q_i} < 61$ and $\forall q_i, q_i << p$ **[3]**. We will denote polynomial ring $Z_{q_i}[X]/X^N+1$ as $R_{q_i}$. Any polynomial $H \in R_Q$ is represented as $H_i \in R_{q_i}$.

Let's denote $Ct_{0,q_i}$ with $T_i$. Then,

$$A_i \cdot S + E + K_i = T_i \mod {R_{q_i}}$$

*Trick 1*: Embed the ring reduction inside the polynomial definition so the operation doesn't need to be performed inside the circuit.

Let $V_i = A_i \cdot S + E + K_i$. One can express the equation above $\mod{Z_{q_i}}$ as:
$$V_i = T_i - R_2 (X^N+1) \mod {Z_{q_i}}$$
One can further express the equation in $Z[X]$ as:
$$V_i = T_i - R_2 (X^N+1) - R_1q_i$$

Since $q_i << p$, the equation stays unchanged in $Z_p$:

$$V_i + R_2 (X^N+1) + R_1q_i = T_i \mod{Z_p}$$

To prove that $Ct_{0,q_i}$ is correctly formed we need to prove that the equation above holds.

*Trick 2*: Prove polynomial multiplication using Schwartz Zippel Lemma so the polynomial multiplication doesn't have to be performed inside the circuit. Only the evaluation of a polynomial is performed inside the circuit.

Recall $A_i, K^0_{i}, T_i$ are public. To prove correctness of $Ct_{0,q_i}$ we need to

1. Prove LHS matches RHS. We will do so by evaluating right hand side and left hand side of the equation at $\alpha$ and show that they are matching.
2. Prove the coefficient of private polynomials $S$, $E$, $K^1$, $R_1$, and $R_2$ are in expected bounded range.

> Note: One can easily modify the circuit for any of the RLWE encryption.

#### Calculating $R_1$ and $R_2$ and their range

Since,
$$V_i = T_i - R_2 (X^N+1) \mod {Z_{q_i}}$$
$$R_2 = \frac{T_i - V_i}{(X^N+1)} \mod {Z_{q_i}}$$
Since $deg(X^N+1) = N$ and $deg(V_i) = 2(N-1)$, $deg(R_2)= 2(N-1) - N = N-2$.

- $R_2 = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$ since the operation is performed $\mod {Z_{q_i}}$

Since,
$$V_i = T_i - R_2 (X^N+1) - R_1$$
$$R_1 = \frac{T_i - V_i - R_2 (X^N+1)}{q_i}$$

- $A_i = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$
- $S = [-1, 1]$
- $deg(A_i)=N-1$.
- $deg(S)=N-1$.
- $A_i S = [-N \cdot \frac{q_i - 1}{2}, N \cdot \frac{q_i - 1}{2}]$. **[4]**
- $E = [-B, B]$
- $A_i S + E = [- (N \cdot \frac{q_i - 1}{2} + B), N \cdot \frac{q_i - 1}{2} + B]$
- $K^{1} = [-\frac{t - 1}{2}, \frac{t - 1}{2}]$
- $K_i^{0} = -(t^{-1} \mod q_i)$. Note: this is a (negative) scalar, not a polynomial
- $K_i^{0}K^{1} = K_i = [-\frac{t - 1}{2} \cdot |K_i^{0}|, \frac{t - 1}{2} \cdot |K_i^{0}|]$
- $A_i S + E + K_i = V_i = [- (N \cdot \frac{q_i - 1}{2} + B +\frac{t - 1}{2} \cdot |K_i^{0}|), N \cdot \frac{q_i - 1}{2} + B + \frac{t - 1}{2} \cdot |K_i^{0}|]$
- $deg(V_i)=2N - 2$.
- $T_i = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$
- $R_2 = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$
- $R_2 (X^N+1)=[-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$ **[5]**
- $T_i - V_i = [- ((N+1) \cdot \frac{q_i - 1}{2} + B +\frac{t - 1}{2} \cdot |K_i^{0}|), (N+1) \cdot \frac{q_i - 1}{2} + B + \frac{t - 1}{2} \cdot |K_i^{0}|]$
- $T_i - V_i - R_2 (X^N+1) = [- ((N+2) \cdot \frac{q_i - 1}{2} + B +\frac{t - 1}{2} \cdot |K_i^{0}|), (N+2) \cdot \frac{q_i - 1}{2} + B + \frac{t - 1}{2} \cdot |K_i^{0}|]$
- $R_1 = \frac{T_i - V_i - R_2 (X^N+1)}{q_i} = [\frac{- ((N+2) \cdot \frac{q_i - 1}{2} + B +\frac{t - 1}{2} \cdot |K_i^{0}|)}{q_i}, \frac{(N+2) \cdot \frac{q_i - 1}{2} + B + \frac{t - 1}{2} \cdot |K_i^{0}|}{q_i}]$

## Circuit Design

To prove that the ciphertext was correctly formed, the prover:
1. Proves that the coefficients of the private polynomials are in the expected range
2. Commits to each private polynomial (end of phase 1).
3. Draw a random point $\alpha \in Z_p$ using the commitment as a source of randomness (Fiat-Shamir Heuristic)
4. Proves that $LHS(\alpha) = RHS(\alpha)$ (phase 2).

#### Assignment - Phase 1

The private polynomials are passed to the circuit in their coefficients form. These are $S$, $E$, $K^1$, $R_1$, and $R_2$.

We also assign to the circuit the public inputs $qi$, $t$, $K^0_{i}$ and $B$. Since these values are passed by the prover at proof generation, it follows that the same circuit can be reused for different RLWE parameters. On the contrary, $N$ is a constant value inside the circuit and needs to be defined at key generation time, so it cannot be dinamically tuned by the prover.

#### Range check of private polynomials - Phase 1

Perform range check on the coefficients of the private polynomials according to the rules defined above.

At the end of Phase 1, the prover commits to the witness and draws a random point $\alpha \in Z_p$ starting from the committed witness (Fiat–Shamir heuristic).

Note that when assigned to the circuit, the coefficients of the polynomial must be in the prime field $[0, p)$. Negative coefficients $-z$ are assigned as field elements $p - z$.

Let's take as example the polynomial $E$. The coefficients of $E$ live in the range $[-B, B]$. This mean that when assigned to the circuit, the coefficients of $E$ must live in the ranges $[0, B]$ or $[-B, p)$. Enforcing the range check in this manner has a the downside of requiring to perform 2 range checks and add an addition OR constrain to that. A more efficient way to perform such range check is to normalize the coefficients such that the coefficients of $E$ must live in the range $[0, 2B]$. The normalization is constrained inside the circuit by adding $B$ to each coefficient.

#### Assignment - Phase 2

*Trick 3*: Since certain polynomials are public, we don't need to perform their evaluation inside the circuit. Instead this can be performed efficiently outside the circuit. The verification of the correct evaluation of these polynomials is offloaded to the verifier on top of the zk proof verification.

Since $A_i, T_i$ and the cyclotomic polynomial $X^N+1$ are public, we can directly pass as public input to the circuit their evaluation at $\alpha$: $A_i(\alpha)$, $T_i(\alpha)$, $\alpha^N+1$.

#### Correct Encryption Constraint - Phase 2

We need to prove that

$$T_i(\alpha) = A_i(\alpha) \cdot S(\alpha) + E(\alpha) + K^0K^1_{i}(\alpha) + R_1(\alpha)q_i + R_2(\alpha) (\alpha^N+1) \mod{Z_p}$$

First, constrain the evaluation of the private polynomials $S$, $E$, $K^1$, $R_1$, and $R_2$ at $\alpha$. After, all the elements are ready to enforce the equality $LHS(\alpha) = RHS(\alpha)$.

#### Proof verification

Up to this point the proof of correct encryption is generated. The user performing the verification would need to:
- verify that the proof is valid via the `verify` API provided by the prover system
- perform further checks on the public inputs
- $qi$ should be co-prime with the other moduli
- $B$ should be equal to 6 * sigma
- $t$ should ...
- $qi$, $B$ and $t$ should match the security requirement of the application
- $K^0_{i}$ should be equal to the multiplicative inverse of $t \mod q_i$
- $T_i(\alpha)$ should be equal to the evaluation of $T_i$ at $\alpha$
- $A_i(\alpha)$ should be equal to the evaluation of $A_i$ at $\alpha$
- $\alpha^N+1$ should be equal to the evaluation of the cyclotomic polynomial at $\alpha$

#### Extending to BFV Public Key Encryption

BFV Public Key Encryption is built, similarly to Secret Key Encryption, using RLWE. The public key is generated as

$$Pk = (Pk_0, Pk_1) = ([A \cdot S + E]_Q, -A)$$

Or, if operating in RNS setting,

$$Pk_{q_i} = (Pk_{0,q_i}, Pk_{1, q_i}) = ([A_i \cdot S + E]_{q_i}, -A_i)$$

Where $A_i \in R_{q_i}, S \in \chi_{key}, E \in \chi_{error}$

Encryption is performed as follows:

$$Ct_{q_i} = (Ct_{0,q_i}, Ct_{1,q_i}) = ([Pk_{0,q_i} \cdot U + E_{0} + K_i]_{q_i}, [Pk_{1,q_i} \cdot U + E_{1}]_{q_i})$$

Where $U \in \chi_{key}$ and $E_{0}, E_{1} \in \chi_{error}$

As you can notice, generating $Ct_{0,q_i} = [Pk_{0,q_i} \cdot U + E_{0} + K_i]_{q_i}$ resembles the ciphertext $Ct_{0,q_i}$ generated during BFV secret key encryption $Ct_{0,q_i} = [A_i \cdot S + E + K]_{qi}$. We can therefore, utilize the exact same technique described above by replacing $A_i, S$ and $E$, with $Pk_{0,q_i}, U$ and $E_{0}$ to prove the correct formation of $Ct_{0,q_i}$ as result of public key BFV encryption.

On top of that, further checks need to performed on $Ct_{1,q_i}$ specifically that:

- $E_{1}$ lives in the expected range
- $[Pk_{1,q_i} \cdot U + E_{1}]_{q_i} = Ct_{1,q_i}$

To prove the second, we follow the same technique described above.

Let's denote $Ct_{1,q_i}$ with $J_i$. Then,

$$Pk_{1,q_i} \cdot U + E_1 = J_i \mod {R_{q_i}}$$

Let $Y_i = Pk_{1,q_i} \cdot U + E_1$. One can express the equation above $\mod{Z_{q_i}}$ as:
$$Y_i = J_i - P_2 (X^N+1) \mod {Z_{q_i}}$$
One can further express the equation in $Z[X]$ as:
$$Y_i = J_i - P_2 (X^N+1) - P_1q_i$$

Since $q_i << p$, the equation stays unchanged in $Z_p$:

$$Y_i + P_2 (X^N+1) + P_1q_i = J_i \mod{Z_p}$$

To prove that $Ct_{1,q_i}$ is correctly formed we need to prove that the equation above holds.

Since,
$$Y_i = J_i - P_2 (X^N+1) \mod {Z_{q_i}}$$
$$P_2 = \frac{J_i - Y_i}{(X^N+1)} \mod {Z_{q_i}}$$
Since $deg(X^N+1) = N$ and $deg(J_i) = 2(N-1)$, $deg(P_2)= 2(N-1) - N = N-2$.

- $P_2 = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$ since the operation is performed $\mod {Z_{q_i}}$

Since,
$$Y_i = J_i - P_2 (X^N+1) - P_1$$
$$P_1 = \frac{J_i - Y_i - P_2 (X^N+1)}{q_i}$$

When applied to the circuit the differences are:

- $E_{1}$, $P_1$ and $P_2$ are private input assigned to the circuit during Phase 1
- The range check on $E_{1}$ is performed in Phase 1. Its bounds are the same as the ones of $E$ from the secret key encryption example.
- The range check on $P_1$ and $P_2$ is performed in Phase 1
- $Pk_{1,q_i}(\alpha)$ and $Ct_{1,q_i}(\alpha)$ are passed as public input during Phase 2
- The evaluation of $E_{1}(\alpha)$, $P_{1}(\alpha)$, $P_{2}(\alpha)$ is performed inside the circuit during Phase 2.
- During Phase 2 in necessary to prove that

$$J_i(\alpha) = Pk_{1,q_i}(\alpha) \cdot U(\alpha) + E_1(\alpha) + P_1(\alpha)q_i + P_2(\alpha) (\alpha^N+1) \mod{Z_p}$$

Note that the bounds of $P1$ are:

- $Pk_{1,q_i} = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$
- $U = [-1, 1]$
- $deg(Pk_{1,q_i})=N-1$.
- $deg(U)=N-1$.
- $Pk_{1,q_i} U = [-N \cdot \frac{q_i - 1}{2}, N \cdot \frac{q_i - 1}{2}]$. **[4]**
- $E_1 = [-B, B]$
- $Pk_{1,q_i} U + E_1 = Y_i = [- (N \cdot \frac{q_i - 1}{2} + B), N \cdot \frac{q_i - 1}{2} + B]$
- $deg(Y_i)=2N - 2$.
- $J_i = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$
- $P_2 = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$
- $P_2 (X^N+1)=[-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$ **[5]**
- $J_i - Y_i = [- ((N+1) \cdot \frac{q_i - 1}{2} + B), (N+1) \cdot \frac{q_i - 1}{2} + B]$
- $J_i - Y_i - P_2 (X^N+1) = [- ((N+2) \cdot \frac{q_i - 1}{2} + B), (N+2) \cdot \frac{q_i - 1}{2} + B]$
- $P_1 = \frac{T_i - V_i - R_2 (X^N+1)}{q_i} = [\frac{- ((N+2) \cdot \frac{q_i - 1}{2} + B)}{q_i}, \frac{(N+2) \cdot \frac{q_i - 1}{2} + B}{q_i}]$

#### Proving that encoded message is correct

Above we assumed that $K$ is correct. However , in practice we require the user to prove that the message satisfies some constraints. First let's see how message encoding works:

Let message vector $M_v \in Z^N_t$ be a vector of size $N$ with each element in $Z_t$. To encode the message as message polynomial $M \in R_t$, we take a inverse NTT transformation of message vector $M$:
$$M = INTT(M_v)$$

To prove that the message is encoded correctly we first need to prove:
1. All elements in $M$ and $M_v$ are in bounded range $[-t/2, ...,0, ..., t/2)$.
2. $[QM]_t = K_1 \in Z^N_t$
3. Inverse NTT transformation is done correctly.

#### Proving INTT

I still have to figure this out. But a naive way this could work is to evaluate $M \in R_q$ at following points $[\zeta, \zeta^3, ..., \zeta^{2N-1}]$, where $\zeta$ is $2N^{th}$ root of unity in $Z_t$ and show that it equals to corresponding slot in $M_v$. This works because doing so performs NTT on $M$, which must equal $M_v$.

The problem with this way of proving INTT is that it has complexity $O(N^2)$ operations in $Z_t$ (we evaluate the polynomial of degree $N-1$ on $N$ values). We can use delay reduction trick to only reduce in the end since $t << q << p$ and we multiply each element once and add at most $2^{15}$ times (i.e. N will be atmost $2^{15}$ usually).

#### RNS and Proof of Encryption

As stated above $Q = \prod q_i$ where $\log{q_i} < 61$ and $\forall q_i, q_i << p$, where $p$ is the prime modulo of the circuit in which we are operating. This feature is introduced in [2018/117](https://eprint.iacr.org/2018/117) as an optimization for BFV scheme: working with coefficients in $Q$ requires expensive multi-precision modular arithmetic. Instead, working with coefficients defined in $q_i$ allows the encryption to be performed more efficiently by performing single-precision integers arithmetic operations. In particular, considering the encryption operation, small integers such as noise and key coefficients are drawn from $\chi_{error}$ and $\chi_{key}$ as single-precision integers, while uniform elements in $a ← Z_{q}$ are chosen directly in the CRT basis by drawing uniform values $a_i ← Z_{q_{i}}$ for all $i$. All the operations that are supposed to be performed in $Z_{q}$ are performed in $Z_{q_{i}}$ for each $i$ decomposition.

The RNS technique becomes useful when working with ZK circuits. In particular using polynomial coefficients within the range of 61 bits allows us to perform arithmetic operations within the circuit without having to worry about applying non-native field operations, which might occur if the size of $q$ is larger than the size of the circuit prime field $p$.

To prove the correct computation of a ciphertext starting from a message, we need to prove the computation of each ciphertext $Ct_{q_i}$. There are two ideas that can be expored here:

#### 1. Parallel Proof Generation

This means that a π of correct encryption needs to be generate for each $i$. The good news is that these proofs can be generated in parallel. Furthermore these proofs (for each $Z_{qi}$) can be eventually aggregated in a single proof that verifies the encryption for each smaller modulus. In this way, the user only has to verify a single proof.


When performing (1st level) of recursion, it is important to check whether the input message is the same and whether the other public inputs are matching.

#### 2. Proving the correctness of multiple ciphertexts in the same proof

Apparently, this approach seems to be the naive version of approach 1. In reality, there's some benefit in this apporach given by the fact that many operations (constraints) can be performed once and then recycled for any ciphertext $i$.

For example the private polynomials $S$, $E$ and $K^1$ are reused across the ciphertext generation for each RNS basis. Therefore it is needed to perform the range checks and the evaluation at $\alpha$ only once no matter the number of CRT decompositions of the ciphertext.

#### Composability with Application-Specific circuit

An application developer might need to prove further properties about the message being encrypted.

To be compatible with other proving frameworks that developers more familiar with, we can use the following technique:

- Prover produces a proof that $H$ is generated correctly from $H = hash(message+salt)$, where $H$ is a public output and $m$ satisfies application specific constraint. (This proof can be generated using a circuit written in circom or any other language).
- Prover produces a proof of correct encryption of the message using the above mentioned circuit. On top of that the circuit also outputs $H = hash(message+salt)$

The business logic of the application should include a check that the two public outputs match.

#### Qs

1. How expensive is it to prove evaluations of polynomial degree in range
2^11 - 2^15?
2. As we are targeting user-side proof generation, will they be able to generate such proofs in parallel on their browser?
3. Do we need to aggregate the proofs $π_{0}, π_{1}, π_{i}, π_{n}$ and the ciphertexts represented in the CRT basis $ct_{0}, ct_{1}, ct_{i}, ct_{n}$ to reconstruct the ciphertext $c_{t}$ defined in $Z_{q}$? Alternatively, we can move this cost to the verifier that would need to: 1) verify each individual proof 2) reconstruct $ct$ using the CRT.

#### As

1. (Enrico) It's $O(n)$ where $n$ is the degree of the polynomial. In other words, each coefficient results in an additional constraint.
2. Yes
3. No, we don't need to reconstruct the ciphertext in Q

#### References

1. https://eprint.iacr.org/2019/057.pdf

#### Notes

**[1]** - As described in section 3.1 of [2021/204](https://eprint.iacr.org/2021/204.pdf)

**[2]** - The fact that $Q$ and $t$ are co-prime guarantees that the multiplicative inverse of $t$ modulo $Q$ exists. If $Q$ and $t$ are co-prime, it means their greatest common divisor (GCD) is 1, i.e. $gcd(Q,t)=1$. The existance of the multiplicative inverse of $t \mod{Q}$ can be understood using the Bezout's Identity which states that for two integers $a$ and $b$ for which $gcd(a,b)=d$, then there exists integers such that $ax + by = d$. In this case $Qx + ty = 1$, $ty = 1 - Qx$, $ty = 1 \mod{Q}$. $y$ in this case is the multiplicative inverse of $t$ modulo $Q$ and this guarantees its existance.
The fact that $Q$ and $t$ are co-prime guarantee that the division has a remainder. That remainder is actually equal to $[QM]_t$. In this way we can cancel out the $\lceil \rfloor$ notation.

**[4]** Let's consider the multiplation of two polynomials $F(x) * G(x) = H(x)$. $F$ and $G$ are polynomial of equal degree $n$. Assume that the coefficients of $F$ and $G$ are in the range $[0, Q)$

$F(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_0$
$G(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_{1}x + b_0$

- Polynomial $H$ will have degree $2n$

$H(x) = c_nx^{2n} + c_{n-1}x^{2n - 1} + ... + c_{1}x + c_0$

- The coefficients of $H$ are calculate as follows: $c_k = \sum_{i+j=k} a_i \cdot b_j$The sum is taken over all the pairs $a_i$ and $b_j$ such that the sum of the indexes is equal to $k$

Now, let's determine which $c_k$ will have the most elements in its sum.

- For values of $k$ such that $k < n$ the number of pairs $(i, j)$ such that $i + j = k$ increseas as $k$ increases. This is intuitive because there are more ways to partition a number into two non-negative integers as the number increases.
- For values of $k$ such that $k > n$ the number of pairs $(i, j)$ such that $i + j = k$ decreases as $k$ increases. This is because the maximum value that $i$ and $j$ can take is $n$. So the number of pairs start to decrease. Think of $k = 2n$, in that case there's only one pair which is $(i=n, j=n)$
- At $k=n$ there's the maximum number of pairs $(i, j)$ such that $i + j = k$. Specifically, there are $n+1$ pairs that satisfy this condition.

Given the case in which:

- $A_i = [-\frac{q_i - 1}{2}, \frac{q_i - 1}{2}]$
- $S = [-1, 1]$
- $deg(A_i)=N-1$.
- $deg(S)=N-1$.

When performing the polynomial multiplication, let's consider the case in which the coefficients of $A_i$ are all $(q_i - 1)/2$ and the coefficients of $S_i$ are all $1$, $c_{n} = \sum_{j=0}^{n-1} a_j * s_{n - j}$

$max(c_n) = \frac{q_i - 1}{2} \cdot 1 \cdot N$ and $min(c_n) = \frac{q_i - 1}{2} \cdot -1 \cdot N$

**[5]** Polynomial Multiplication between
- $R_2 = [-(q_i - 1)/2, (q_i - 1)/2]$.
- $deg(X^N+1) = N$
- $deg(R_2)= 2(N-1) - N = N-2$
- $deg(R_2 * X^N+1 )= 2N - 2$

When performing the polynomial multiplication, let's consider the case in which the coefficients of $R2$ are all $(q_i - 1)/2$ and let's define the polynomial $(X^N+1)$ as $f$.

The results of the multiplication between any coefficient of $R2$ with the leading coefficient of $f$ (=1) will contribute to the summation of the resulting polynomial coefficients of degree from $2N - 2$, when the leading coefficient of $R2$ is multiplied with the leading coefficient of $f$, to $N$, when the constant term of $R2$ is multiplied with the leading coefficient of $f$.

The results of the multiplication between any coefficient of $R2$ with the constant term of $f$ (=1) will contribute to the summation of the resulting polynomial coefficients of degree from $N - 2$, when the leading coefficient of $R2$ is multiplied with the constant term of $f$, to $0$, when the constant term of $R2$ is multiplied with constant term of $f$.

Given that all the other coefficients of $f$ are equal to 0, the multiplication between the coefficients of $R2$ and these coefficients of $f$ won't contribute to the summation of any of the resulting polynomial coefficients.

We also note that the results of the multiplication between any coefficient of $R2$ with the leading coefficient of $f$ and the results of the multiplication between any coefficient of $R2$ with the constant term of $f$ (=1) won't ever be added together in the summation to calculate one of the resulting polynomial coefficients.

Therefore, it can be conclued that the range of the resulting polynomial is the same as the range of the $R_2$ polynomial.