# GLWE Homomorphic Addition Now that we’ve defined **GLWE ciphertexts**, we can start doing real computation on them. The first and most important basic operation is: > **Homomorphic addition:** you can add two GLWE ciphertexts component-wise, and after decryption you get the sum of the plaintext polynomials. *** ## 1) Setup: plaintext space, ciphertext space, and the scaling factor Δ ### Plaintexts live in $$\mathcal{R}\_p$$ Messages are polynomials with coefficients modulo `p`: $$M \in \mathcal{R}\_p$$ ### Ciphertexts live in $$\mathcal{R}\_q$$ Ciphertext coefficients are modulo `q` (typically much larger than `p`). ### Encoding uses a scaling factor We use a scale factor: $$\Delta = \frac{q}{p}$$ In many TFHE-style parameter sets, `p` and `q` are chosen so this is exact; otherwise, encoding involves rounding. *** ## 2) Reminder: what does a GLWE ciphertext look like? A GLWE ciphertext encrypting `M` under secret key $$\vec{S}=(S\_0,\dots,S\_{k-1})$$ is: $$C = (A\_0,\ldots,A\_{k-1},B) \in \mathcal{R}\_q^{k+1}$$ And the body polynomial is built like: $$B = \sum\_{i=0}^{k-1} A\_i \cdot S\_i ;+; \Delta M ;+; E \pmod q$$ where $E$ is a small noise polynomial. *** ## 3) The homomorphic addition rule Suppose we have two GLWE ciphertexts under the **same secret key**: $$C = (A\_0,\ldots,A\_{k-1},B) \in GLWE\_{\vec{S}}(\Delta M)$$ $$C' = (A'*0,\ldots,A'*{k-1},B') \in GLWE\_{\vec{S}}(\Delta M')$$ ### Add them component-wise in $\mathcal{R}\_q$ $$C^{(+)} = C + C' = (A\_0 + A'*0,\ldots,A*{k-1}+A'\_{k-1},; B+B')$$ The result is still a valid GLWE ciphertext, encrypting: $$\Delta(M+M')$$ So after decoding, the plaintext is: $$M^{(+)} = M + M' \quad\text{in}\quad \mathcal{R}\_p$$ *** ## 4) Why does this work? Write both bodies: $$B = \sum A\_iS\_i + \Delta M + E$$ $$B' = \sum A'\_iS\_i + \Delta M' + E'$$ Add them: $$B+B' = \sum (A\_i + A'\_i)S\_i ;+; \Delta(M+M') ;+; (E+E')$$ Now decrypt $C^{(+)}$ by computing: $$(B+B') - \sum (A\_i+A'\_i)S\_i = \Delta(M+M') + (E+E')$$ Finally, decode by dividing/rounding by $\Delta$ coefficient-wise to recover $M+M'$, as long as the noise stays small enough. Component-wise ciphertext addition becomes plaintext addition. ***

*image credit: zama

*** ## 5) Noise growth Addition is one of the cheapest operations because noise grows slowly: * before: noise is $$E$$ and $$E'$$ * after: noise becomes $$E$$ + $$E'$$ So: * repeated additions are usually safe for quite a while * but eventually noise can grow too large and decoding can fail (this is why TFHE later introduces refreshing/bootstrapping machinery) *** ## 6) Toy example idea (what to look for) To better understand GLWE addition, let's use a toy example. Note that these parameters are totally insecure and are used only to fix ideas. ### Parameters * **Moduli:** $$q = 64$$, $$p = 4$$ * **Scale:** $$\Delta = q / p = 16$$ * **Polynomial degree:** $$N = 4$$ * **Dimension:** $$k = 2$$ ### Secret Key We sample the secret key with uniform binary distribution as $k$ polynomials of degree smaller than $$N$$: $$\vec{S} = (S\_0, S\_1) = (X + X^2, 1 + X^2 + X^3) \in \mathcal{R}^2$$ ### Messages Let's encrypt two messages which are polynomials of degree smaller than $$N$$ with coefficients in {−2,−1,0,1} : $$M = -2 + X - X^3 \in \mathcal{R}\_p$$ $$M' = X + X^2 - 2X^3 \in \mathcal{R}\_p$$ Their addition in $$\mathcal{R}\_p$$is equal to: $$M^{(+)} = -2 - 2X + X^2 + X^3 \in \mathcal{R}\_p$$ ### Encryption To encrypt, we sample uniformly random polynomial masks with coefficients in roughly $$\[-q/2, q/2]$$ and discrete Gaussian errors (small coefficients). **For the first message ($M$):** * **Mask:** $$\vec{A} = (A\_0, A\_1) = (17 - 2X - 24X^2 + 9X^3, -14 - X^2 + 21X^3) \in \mathcal{R}\_q^2$$ * **Error:** $$E = -1 + X + X^3 \in \mathcal{R}\_q$$ * **Body:** $$B = A\_0 S\_0 + A\_1 S\_1 + \Delta M + E = -31 + 5X - 21X^2 + 30X^3 \in \mathcal{R}*q$$ *(Note: Operations are modulo* $$X^N + 1$$ i.e., $$X^4 + 1$$, *and modulo* $$q$$ i.e., $$64$$*)\_ * **Ciphertext:** $$C = (A\_0, A\_1, B) \in \mathcal{R}\_q^3$$ **For the second message ($M'$):** * **Mask:** $$\vec{A'} = (A'\_0, A'\_1) = (-8 + 15X + 3X^2 - 30X^3, 23 - 16X + 27X^2 - 4X^3) \in \mathcal{R}\_q^2$$ * **Error:** $$E' = X - X^2 - X^3 \in \mathcal{R}\_q$$ * **Body:** $$B' = A'\_0 S\_0 + A'\_1 S\_1 + \Delta M' + E' = -25 + 12X^2 - 12X^3 \in \mathcal{R}\_q$$ * **Ciphertext:** $$C' = (A'\_0, A'\_1, B') \in \mathcal{R}\_q^3$$ ### Homomorphic Addition We perform the addition by adding the components term-wise in $$\mathcal{R}\_q$$: 1. **Add Masks:** $$A\_0^{(+)} = A\_0 + A'\_0 = 9 + 13X - 21X^2 - 21X^3 \in \mathcal{R}\_q$$ $$A\_1^{(+)} = A\_1 + A'\_1 = 9 - 16X + 26X^2 + 17X^3 \in \mathcal{R}\_q$$ 2. **Add Bodies:** $$B^{(+)} = B + B' = 8 + 5X - 9X^2 + 18X^3 \in \mathcal{R}\_q$$ 3. **Resulting Ciphertext:** $$C^{(+)} = (A\_0^{(+)}, A\_1^{(+)}, B^{(+)}) \in \mathcal{R}\_q^3$$ ### Decryption and Verification To verify the result, we decrypt the resulting ciphertext: 1. **Phase Calculation:** $$B^{(+)} - \sum\_{i=0}^{k-1} A\_i^{(+)} \cdot S\_i = 31 - 30X + 15X^2 + 16X^3 \in \mathcal{R}\_q$$ 2. **Rescaling and Rounding:** $$\lfloor (31 - 30X + 15X^2 + 16X^3) / 16 \rceil = -2 - 2X + X^2 + X^3 \in \mathcal{R}\_p$$ This result matches exactly $$M^{(+)}$$ The decryption worked because the error coefficients were all smaller (in absolute value) than $$\Delta / 2 = 8$$. The new error was in fact equal to $$E^{(+)} = -1 + 2X - X^2$$. *** ## 7) Adding a public constant If you want to add a **public constant polynomial** $$\Sigma \in \mathcal{R}\_p$$ to an encrypted message $$M$$, you can add a **trivial GLWE ciphertext**: $$(0,\ldots,0,\Delta\Sigma)$$ to the ciphertext of $$M$$. The result encrypts $$M+\Sigma$$. This is a super common trick: treat “known values” as ciphertext-shaped objects so everything composes cleanly. *** ## 8) ELI5 summary * A GLWE ciphertext is a locked polynomial box: $$(A\_0,\ldots,A\_{k-1},B)$$. * To add two locked boxes, add each part. * When you unlock, you get the sum of the original messages plus a bit more fuzz (noise). --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://sabanaku77.gitbook.io/fhe-handbook-for-beginners/glwe-homomorphic-addition.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.