B-4.3 Decryption

1.

Given the ciphertext $({\{A_i\}}_{i=0}^{k-1},B)$ where $B=\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(A_i\cdot S_i)+\mathrm{\Delta }\cdot M+E\in R_{⟨n,q⟩}$, compute $B-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(A_i\cdot S_i)=\mathrm{\Delta }\cdot M+E$.

2.

Round each coefficient of the polynomial $\mathrm{\Delta }\cdot M+E\in R_{⟨n,q⟩}$ to the nearest multiple of $\mathrm{\Delta }$ (i.e., round it as a base $\mathrm{\Delta }$ number), which is denoted as $\lceil \mathrm{\Delta }\cdot M+E{\rfloor }_{\mathrm{\Delta }}$. This operation successfully eliminates $E$ and gives $\mathrm{\Delta }\cdot M$. One caveat is that $E$’s each coefficient $e_i$ has to be $e_i<{\displaystyle \frac{\mathrm{\Delta }}{2}}$ to be eliminated during the rounding. Otherwise, some of $e_i$’s higher bits will overlap the plaintext $m_i$ coefficient’s lower bit and won’t be eliminated during decryption, corrupting the plaintext $m_1$.

3.

Compute ${\displaystyle \frac{\mathrm{\Delta }\cdot M}{\mathrm{\Delta }}}$, which is equivalent to right-shifting each polynomial coefficient in $\mathrm{\Delta }\cdot M$ by ${\text{log}}_2\mathrm{\Delta }$ bits.

In summary, the GLWE decryption formula is summarized as follows:

B-4.3.1 Discussion

1.

LWE is a special case of GLWE where the polynomial ring’s degree $n=1$. That is, all polynomials in ${\{A_i\}}_{i=0}^{k-1},{\{S_i\}}_{i=0}^{k-1},E$, and $M$ are zero-degree polynomial constants. Instead, there are $k$ such constants for $A_i$ and $S_i$, so each of them forms a vector.

2.

RLWE is a special case of GLWE where $k=1$. That is, the secret key $S$ is a single polynomial $S_0$, and each encryption is processed by only a single polynomial $A_0$ as a public key.

3.

Size of $𝐧$: A large polynomial degree $n$ increases the number of the secret key’s coefficient terms (i.e., $S_i=s_{i,0}+s_{i,1}X+\cdots +s_{i,n-1}{X}^{n-1}$), which makes it more difficult to guess the complete secret key. The same applies to the noise polynomial $E$ and the public key polynomials $A_i$, thus making it harder to solve the search-hard problem (§B-1.1). Also, higher-degree polynomials can encode more plaintext terms in the same plaintext polynomial $M$, improving the throughput efficiency of processing ciphertexts.

4.

Size of $𝐤$: A large $k$ increases the number of the secret key polynomials $(S_0,S_1,\cdots ,S_k)$ and the number of the one-time public key polynomials $(A_0,A_1,\cdots ,A_k)$, which makes it more difficult for the attacker to guess the complete secret keys. Meanwhile, there is only a single $M$ and $E$ polynomials per GLWE ciphertext, regardless of the size of $k$.

5.

Reducing the Ciphertext Size: The public key ${\{A_i\}}_{i=0}^{k-1}$ has to be created for each ciphertext, which is a big size. To reduce this size, each ciphertext can instead include the seed $d$ for the pseudo-random number generation hash function $H$. Then, the public key can be lively computed $k-1$ times upon each encryption & decryption as $\{H(s),H(H(s)),H(H(H(s)),\cdots \}$. Note that $H$, by nature, generates the same sequence of numbers given the same random initial seed $d$.