Decryption

B-3.3 Decryption

1.: Given the ciphertext $(A, B)$ where $B = A \cdot S + Δ \cdot M + E \in R_{⟨ n, q ⟩}$ , compute $B - A \cdot S = Δ \cdot M + E$ .
2.: Round each coefficient of the polynomial $Δ \cdot M + E \in R_{⟨ n, q ⟩}$ to the nearest multiple of $Δ$ (i.e., round it as a base $Δ$ number), which is denoted as $⌈ Δ \cdot M + E ⌋_{Δ}$ . This rounding operation successfully eliminates $E$ and gives $Δ \cdot M$ . One caveat is that the noise $E$ ’s each coefficient $e_{i}$ should be small enough to be $e_{i} < \frac{Δ}{2}$ in order to be eliminated during the rounding. Otherwise, some of $e_{i}$ ’s higher bits will overlap and corrupt the plaintext $m_{i}$ coefficient’s lower bits and won’t be blown away.
3.: Compute $\frac{Δ \cdot M}{Δ}$ , which is equivalent to scaling down each polynomial coefficient in $Δ \cdot M$ by $Δ$ (or right-shifting each coefficient by ${log}_{2} Δ$ bits if $Δ$ is a power of 2).

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

$⟨$ Summary B-3.3 $⟩$ RLWE Decryption

Decryption Input: $𝖼𝗍 = (A, B) \in R_{⟨ n, r ⟩}^{2}$

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

For correct decryption, every noise coefficient $e_{i}$ of polynomial $E$ should be: $e_{i} < \frac{Δ}{2}$ . And in case $t$ does not divide $q$ , $q$ should be sufficiently larger than $t$ .

[prev][parent]