An Alternative Version of GLWE

The following is an alternative version of

⟨

Summary B-4.2

⟩

, where the sign of each

A_{i} S_{i}

is flipped in the encryption and decryption formula as follows:

$⟨$ Summary B-4.4 $⟩$ An Alternative GLWE Cryptosystem

Initial Setup: $Δ = ⌊ \frac{q}{t} ⌋$ , ${S_{i}}_{i = 0}^{k - 1} \leftarrow_{}^{$} R_{⟨ n, 𝑡𝑒𝑟𝑛 ⟩}^{k}$

Encryption Input: $M \in R_{⟨ n, t ⟩}$ , ${A_{i}}_{i = 0}^{k - 1} \leftarrow_{}^{$} R_{⟨ n, q ⟩}^{k}$ , $E \leftarrow_{}^{χ_{σ}} R_{⟨ n, q ⟩}$

1.: Scale up $M \to Δ M \in R_{⟨ n, q ⟩}$
2.: Compute $B = - \sum_{i = 0}^{k - 1} (A_{i} \cdot S_{i}) + Δ M + E \in R_{⟨ n, q ⟩}$
3.: ${𝖦𝖫𝖶𝖤}_{S, σ} (Δ M + E) = ({A_{i}}_{i = 0}^{k - 1}, B) \in R_{⟨ n, q ⟩}^{k + 1}$

Decryption Input: $𝖼𝗍 = ({A_{i}}_{i = 0}^{k - 1}, B) \in R_{⟨ n, q ⟩}^{k + 1}$

1.: ${𝖦𝖫𝖶𝖤}_{S, σ}^{- 1} (𝖼𝗍) = B + \sum_{i = 0}^{k - 1} (A_{i} \cdot S_{i}) = Δ M + E \in R_{⟨ n, q ⟩}$
2.: Scale down $⌈ \frac{Δ M + E}{Δ} ⌋ = M \in R_{⟨ n, t ⟩}$

For correct decryption, every noise coefficient $e_{i}$ of polynomial $E$ should be: $| e_{i} | < \frac{Δ}{2}$ .

Even if the

A_{i} S_{i}

terms flip their signs, the decryption stage cancels out those terms by adding their equivalent double-sign-flipped terms; thus, the same correctness of decryption is preserved as in the original version.

B-4.4 An Alternative Version of GLWE