Repository navigation
Expand file tree
/
Copy pathc02-glwe-add-plain.tex
More file actions
59 lines (33 loc) · 2.09 KB
/
Copy pathc02-glwe-add-plain.tex
File metadata and controls
59 lines (33 loc) · 2.09 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
Suppose we have a GLWE ciphertext \textsf{ct} and a new plaintext polynomial $\Lambda$ as follows:
$\textsf{ct} = \textsf{GLWE}_{S, \sigma}(\Delta M + E) = ( A_0, A_1, \ldots, A_{k-1}, B) \in \mathcal{R}_{\langle n,q \rangle}^{k + 1}$
$\Lambda$: a new plaintext polynomial
$\Delta \Lambda$: a $\Delta$-scaled new plaintext polynomial
$ $
\noindent Let's define the following ciphertext-to-plaintext addition operation:
$\textsf{ct} + \Delta\Lambda = ( A_0, \text{ } A_1, \ldots, A_{k-1}, \text{ } B + \Delta \Lambda)$
$ $
\noindent Then, the following is true:
\begin{tcolorbox}[title={\textbf{\tboxlabel{\ref*{sec:glwe-add-plain}} GLWE Homomorphic Addition with a Plaintext}}]
$\textsf{GLWE}_{S, \sigma}(\Delta M + E) + \Delta\Lambda $
$= (\{A_i\}_{i=0}^{k-1}, \text{ } B) + \Delta\Lambda$
$= (\{A_i\}_{i=0}^{k-1}, \text{ } B + \Delta\Lambda)$
$= \textsf{GLWE}_{S, \sigma}(\Delta (M + \Lambda) + E)$
\end{tcolorbox}
This means that adding a ($\Delta$-scaled) plaintext polynomial $\Lambda$ to a GLWE ciphertext that encrypts $M$ and decrypting it yields $M + \Lambda$.
\begin{myproof}
\begin{enumerate}
\item Since $B = \sum\limits_{i=0}^{k-1}{(A_i \cdot S_i)} + \Delta \cdot M + E$,
$B + \Delta \cdot \Lambda = \sum\limits_{i=0}^{k-1}{(A_i \cdot S_i)} + \Delta \cdot M + E + \Delta \cdot \Lambda = \sum\limits_{i=0}^{k-1}{(A_i \cdot S_i)} + \Delta \cdot (M + \Lambda) + E$ \\
This means that $(A_0, A_1, ... \text{ } A_{k-1}
, B + \Delta \Lambda)$ form the ciphertext $\textsf{GLWE}_{S, \sigma}(\Delta (\Lambda + M) + E)$
\item Thus, \\
$\textsf{GLWE}_{S, \sigma}(\Delta M + E) + \Delta\Lambda$ \\
$ = (A_0, \text { } A_1, ... \text{ } A_{k-1}, \text { } B + \Delta \Lambda)$ \\
$ = (\{A_i\}_{i=0}^{k-1}, \text { } B + \Delta \Lambda)$ \\
$= \textsf{GLWE}_{S, \sigma}(\Delta (M + \Lambda) + E)$
%\begin{flushright}
%\qedsymbol{}
%\end{flushright}
\end{enumerate}
\end{myproof}
\para{Noise Growth: } Note that after decryption, the original ciphertext $\textsf{ct} +\Delta\Lambda$'s noise $E$ stays the same as before. This means that ciphertext-to-plaintext addition does not increase the noise level.