# GLWE Homomorphic Multiplication by a Large Constant

Earlier, we saw that multiplying a **GLWE ciphertext** by a **small** public constant polynomial works by multiplying every ciphertext component by that polynomial. The catch is that **noise grows proportionally to the size of the constant’s coefficients**.

**So what happens if the constant is large?**

If you naively multiply every ciphertext component by a large constant $$\gamma$$, the noise gets multiplied by $$\gamma$$ too. This noise can become so large that it compromises the result and decoding fails.

TFHE solves this with an elegant trick:

> **Decompose the large constant into small digits using a base** $$\beta$$**, then recombine them using an inner product with a GLev ciphertext.**

This operation is used mainly as a **building block** for more complex procedures (like key switching and ciphertext-ciphertext multiplication), rather than as a standalone “multiply-by-large-constant” API.

***

## 1) Why the Naive Approach Fails

Let a GLWE ciphertext encrypt $$M \in \mathcal{R}\_p$$(encoded as$$\Delta M$$) under a secret key $$\vec{S}$$:

$$
C=(A\_0,\ldots,A\_{k-1},B) \quad\text{with}\quad B=\sum\_i A\_iS\_i+\Delta M+E \pmod q
$$

If you multiply by a large constant $$\gamma \in \mathbb{Z}\_q$$ naively:

$$
\gamma\cdot C = (\gamma A\_0,\ldots,\gamma A\_{k-1},\gamma B)
$$

After decryption, the noise becomes $$\gamma E$$. When $$\gamma$$ is large, $$\gamma E$$ often becomes too big for correct rounding and decoding.

<figure><img src="/files/3JETlsCy0IuSikw6HVm0" alt=""><figcaption><p>*image credit: <a href="https://www.zama.org/post/tfhe-deep-dive-part-3">zama</a></p></figcaption></figure>

***

## 2) The Trick: Decompose $$\gamma$$ in a Small Base $$\beta$$

Pick:

* A small base $$\beta$$ (typically a power of 2).
* A number of levels $$\ell$$.

Decompose $$\gamma$$ as:

$$
\gamma = \gamma\_1 \frac{q}{\beta^1} + \gamma\_2 \frac{q}{\beta^2} + \cdots + \gamma\_\ell \frac{q}{\beta^\ell}
$$

Here, each decomposed digit $$\gamma\_j$$ is **small** (e.g., in $$\mathbb{Z}\_\beta$$, or a signed small range depending on the decomposition variant).

***

## 3) Where GLev Enters the Story

A **GLev** ciphertext of $$M$$is conceptually a list of GLWE ciphertexts that encrypt the *same* message$$M$$, but scaled at different powers of the decomposition base:

$$
\text{GLev}(M) = \left(\text{GLWE}\left(\frac{q}{\beta^1}M\right),; \text{GLWE}\left(\frac{q}{\beta^2}M\right),;\ldots,;\text{GLWE}\left(\frac{q}{\beta^\ell}M\right)\right)
$$

This “multi-scale” structure is exactly what we need to invert the decomposition and recombine the digits.

***

## 4) Multiplying by a Large Constant Using Decomposition & Inner Product

### Inputs

* A large constant $$\gamma$$.
* A **GLev** ciphertext:

  $$
  \text{GLev}(M) = (C^{(1)},\ldots,C^{(\ell)})
  $$

  where each $$C^{(j)}$$is a GLWE encryption of$$\frac{q}{\beta^j}M$$.

### Step 1: Decompose $$\gamma$$

Compute the digits:

$$
(\gamma\_1,\ldots,\gamma\_\ell) = \text{Decomp}^{\beta,\ell}(\gamma)
$$

such that:

$$
\gamma \approx \sum\_{j=1}^{\ell}\gamma\_j\frac{q}{\beta^j}
$$

### Step 2: Recombine with an Inner Product

Compute the output ciphertext:

$$
C\_{\text{out}} = \sum\_{j=1}^{\ell} \gamma\_j \cdot C^{(j)}
$$

* Each $$\gamma\_j$$ is **small**, so computing  $$\gamma\_j \cdot C^{(j)}$$  is only a “small-constant multiplication” where noise stays under control.
* Summing the $$\ell$$ ciphertexts causes noise to add up, but it remains strictly manageable.

### What Does It Encrypt?

Because $$C^{(j)}$$ encrypts $$\frac{q}{\beta^j}M$$, the resulting sum encrypts:

$$
\sum\_{j=1}^{\ell} \gamma\_j \cdot \frac{q}{\beta^j}M \approx \gamma \cdot M
$$

You successfully obtain an encryption of $$\gamma M$$ without ever multiplying the noise by the full magnitude of $$\gamma$$.

<figure><img src="/files/9bCTPhI9ospOAkyR75ED" alt=""><figcaption><p>*image credit: <a href="https://www.zama.org/post/tfhe-deep-dive-part-3">zama</a></p></figcaption></figure>

***

## 5) Important Caveat: The Output Has No More $$\Delta$$

A subtle but vital point is that the result of this operation is an encryption of $$M \cdot \gamma$$ without the standard $$\Delta$$ encoding. Because the original GLev layers encrypted unscaled fragments of $$M$$, the resulting summation directly yields $$\gamma M$$.

After this operation, the resulting message can **occupy the whole** $$\mathbb{Z}\_q$$ space (i.e., it is no longer neatly housed in the $$\Delta\cdot\mathcal{R}\_p$$  MSB-encoded format).

Because of this:

* You generally **do not use this operation alone** as a standard “multiply by constant” API in applications.
* Instead, it serves as the **fundamental building block** for internal operations like **key switching** and ciphertext multiplication.

***

## 6) Approximate Decomposition

In many practical implementations, you don't need full-precision decomposition (meaning you don't need $$\beta^\ell = q$$).

You can choose $$\beta^\ell < q$$, which involves:

* **Rounding** the value in the LSB part before decomposing.
* Decomposing only up to the fixed precision you care about.

**Why this is safe:** The LSBs already occupy "noisy space." For MSB-style encodings, the meaningful information lives exclusively in the MSBs. Therefore, rounding away some LSB precision typically doesn’t harm correctness if parameters are chosen correctly.

***

## 7) Large Polynomial Multiplication

The concepts described above for a scalar constant $$\gamma$$ apply identically to a **large polynomial**.

For a large polynomial:

$$
\Lambda(X)=\sum\_{i=0}^{N-1}\Lambda\_i X^i
$$

You follow the same coefficient-wise footprint:

$$
\text{Decomp}^{\beta,\ell}(\Lambda) = (\Lambda^{(1)},\ldots,\Lambda^{(\ell)})
$$

yielding small-digit polynomials $$\Lambda^{(j)}$$ such that:

$$
\Lambda \approx \Lambda^{(1)}\frac{q}{\beta^1} + \cdots + \Lambda^{(\ell)}\frac{q}{\beta^\ell}
$$

You then simply perform a **polynomial inner product** with the GLev.

***

## 8) Detailed Toy Example: Decomposition

The goal of this example is to solidify the mechanics of decomposition. We will decompose a large polynomial using **approximate signed decomposition**, which is standard in practice.

We use parameters: $$q = 64$$, $$p = 4$$, $$\Delta = q/p = 16$$, $$N = 4$$, and $$k = 2$$.

Let's choose a random large polynomial in $$\mathcal{R}\_q$$(degree$$< N=4$$, coefficients in $$\[-32, 31]$$):

$$
\Lambda = 28 - 5X - 30X^2 + 17X^3
$$

Choose a decomposition base $$\beta = 4$$and levels$$\ell = 2$$, meaning $$\beta^\ell = 16$$. We will decompose the $$4$$MSBs of each coefficient. First, we round all coefficients by assessing the$$2$$ LSBs.

Writing them in binary (MSB on the left, LSB on the right) and rounding:

* $$\Lambda\_0 = 28 \longmapsto (0, 1, 1, 1 \mid 0, 0) \implies \Lambda'\_0 = (0, 1, 1, 1)$$
* $$\Lambda\_1 = -5 \longmapsto (1, 1, 1, 0 \mid 1, 1) \implies \Lambda'\_1 = (1, 1, 1, 1)$$ (rounded up due to carry)
* $$\Lambda\_2 = -30 \longmapsto (1, 0, 0, 0 \mid 1, 0) \implies \Lambda'\_2 = (1, 0, 0, 1)$$ (rounded up due to carry)
* $$\Lambda\_3 = 17 \longmapsto (0, 1, 0, 0 \mid 0, 1) \implies \Lambda'\_3 = (0, 1, 0, 0)$$

For a **signed decomposition** in base $$\beta=4$$, we want coefficients strictly in $${-2, -1, 0, 1}$$. Working from LSB to MSB in 2-bit blocks:

* Value `0` $$(0, 0)$$or `1`$$(0, 1)$$: record as is.
* Value `2` $$(1, 0)$$or `3`$$(1, 1)$$: subtract $$4$$, record the negative value, and add a $$+1$$ carry to the next block. Any carry extending beyond the MSB is discarded.

**Decomposing** $$\Lambda'\_0 \longmapsto (0, 1, 1, 1)$$**:**

* LSB block $$(1, 1)$$ is $$3$$. Subtract $$4 \implies -1$$(first element). Carry$$+1$$.
* Next block $$(0, 1)$$ is $$1$$. Add carry $$\implies 2$$. Subtract $$4 \implies -2$$ (second element). Carry discarded.

**Decomposing** $$\Lambda'\_1 \longmapsto (1, 1, 1, 1)$$**:**

* LSB block $$(1, 1)$$ is $$3$$. Subtract $$4 \implies -1$$(first element). Carry$$+1$$.
* Next block $$(1, 1)$$ is $$3$$. Add carry $$\implies 4$$(or$$0$$with carry). Value is$$0$$ (second element).

**Decomposing** $$\Lambda'\_2 \longmapsto (1, 0, 0, 1)$$**:**

* LSB block $$(0, 1)$$ is $$1$$. Record $$1$$ (first element).
* Next block $$(1, 0)$$ is $$2$$. Subtract $$4 \implies -2$$ (second element).

**Decomposing** $$\Lambda'\_3 \longmapsto (0, 1, 0, 0)$$**:**

* LSB block $$(0, 0)$$ is $$0$$. Record $$0$$ (first element).
* Next block $$(0, 1)$$ is $$1$$. Record $$1$$ (second element).

Writing the decomposed polynomials explicitly:

$$
\begin{cases}
\Lambda^{(1)} = -2 - 2X^2 + X^3 \\
\Lambda^{(2)} = -1 - X + X^2
\end{cases}
$$

*(Note: The coefficients of* $$\Lambda^{(2)}$$ *are the first elements mapping to weight* $$4$$*, while the coefficients of* $$\Lambda^{(1)}$$ *are the second elements mapping to weight* $$16$$*)*.

To verify, invert the decomposition:

$$
\Lambda^{(1)} \cdot 16 + \Lambda^{(2)} \cdot 4 = (-2 - 2X^2 + X^3) \cdot 16 + (-1 - X + X^2) \cdot 4 = 28 - 4X - 28X^2 + 16X^3
$$

This precisely approximates the original polynomial $$\Lambda$$ within $$\mathcal{R}\_q$$.

***

## 9) Extending the Toy Example: The Inner Product

To see the full homomorphic multiplication in action, let's perform the inner product between our decomposed polynomial $$\Lambda$$ and a toy **GLev** ciphertext.

Let's assume we want to multiply $$\Lambda$$ by a simple plaintext message polynomial$$M = 1 + X \in \mathcal{R}\_p$$.

A GLev ciphertext of $$M$$consists of $$\ell = 2$$ standard GLWE ciphertexts, each encrypting $$M$$scaled by $$\frac{q}{\beta^j}$$. Using our parameters ($$q=64$$, $$\beta=4$$):

* $$C^{(1)}$$encrypts$$\frac{q}{\beta^1}M = 16M = 16 + 16X$$
* $$C^{(2)}$$encrypts$$\frac{q}{\beta^2}M = 4M = 4 + 4X$$

Let's represent these GLWE ciphertexts abstractly as tuples of polynomials (since $$k=2$$, they have a mask portion and a body portion):

* $$C^{(1)} = (A\_0^{(1)}, A\_1^{(1)}, B^{(1)})$$
* $$C^{(2)} = (A\_0^{(2)}, A\_1^{(2)}, B^{(2)})$$

### The Homomorphic Evaluation

To compute the multiplication $$C\_{\text{out}} \approx \Lambda \cdot \text{GLev}(M)$$, we compute the inner product of our decomposed digits $$(\Lambda^{(1)}, \Lambda^{(2)})$$with the GLev ciphertexts $$(C^{(1)}, C^{(2)})$$:

$$
C\_{\text{out}} = \Lambda^{(1)} \cdot C^{(1)} + \Lambda^{(2)} \cdot C^{(2)}
$$

Because scalar/polynomial multiplication on a ciphertext is linear, we apply it component-wise:

$$
C\_{\text{out}} = \left( \Lambda^{(1)}A\_0^{(1)} + \Lambda^{(2)}A\_0^{(2)}, \quad \Lambda^{(1)}A\_1^{(1)} + \Lambda^{(2)}A\_1^{(2)}, \quad \Lambda^{(1)}B^{(1)} + \Lambda^{(2)}B^{(2)} \right)
$$

By multiplying the ciphertexts by the **small** polynomials $$\Lambda^{(1)}$$and$$\Lambda^{(2)}$$(whose coefficients are strictly in$${-2, -1, 0, 1}$$), the noise growth within $$B^{(1)}$$and$$B^{(2)}$$ is kept strictly bounded.

### Verifying the Underlying Phase (Decryption)

To prove this worked, let's look at the "phase" (the unencrypted mathematical value inside the body $$B$$minus the secret key masking) of$$C\_{\text{out}}$$.

The phase of $$C\_{\text{out}}$$will be the linear combination of the phases of$$C^{(1)}$$and$$C^{(2)}$$:

$$
\text{Phase}(C\_{\text{out}}) = \Lambda^{(1)} \cdot (16M) + \Lambda^{(2)} \cdot (4M)
$$

Factoring out $$M$$:

$$
\text{Phase}(C\_{\text{out}}) = M \cdot \left( \Lambda^{(1)} \cdot 16 + \Lambda^{(2)} \cdot 4 \right)
$$

Notice that the term in the parentheses is exactly the recomposition of our approximated large polynomial from earlier!

$$
\text{Phase}(C\_{\text{out}}) = M \cdot \Lambda\_{\text{approx}}
$$

$$
\text{Phase}(C\_{\text{out}}) = (1 + X) \cdot (28 - 4X - 28X^2 + 16X^3)
$$

Now, we perform standard polynomial multiplication in $$\mathcal{R}\_q$$(modulo$$q=64$$and modulo$$X^4 + 1$$):

$$
(1 + X)(28 - 4X - 28X^2 + 16X^3) = 28 - 4X - 28X^2 + 16X^3 + 28X - 4X^2 - 28X^3 + 16X^4
$$

Because we are in the cyclotomic ring $$X^4 + 1 = 0$$, we substitute $$X^4 = -1$$:

$$
\= 28 - 4X - 28X^2 + 16X^3 + 28X - 4X^2 - 28X^3 - 16
$$

Grouping the terms:

$$
\= (28 - 16) + (-4 + 28)X + (-28 - 4)X^2 + (16 - 28)X^3
$$

$$
\= 12 + 24X - 32X^2 - 12X^3
$$

**The Result:** $$C\_{\text{out}}$$successfully encrypts$$12 + 24X - 32X^2 - 12X^3 \pmod{64}$$.

Most importantly, notice that this output is **not** scaled by $$\Delta$$(which would be$$16$$). It occupies the full space of $$\mathbb{Z}\_q$$, perfectly illustrating the caveat from Section 5: this building block yields an unscaled result, which is exactly the format required to feed into a Key Switching operation.

***

## 10) Next Steps: Applications in Key Switching

While the lack of $$\Delta$$ prevents this from being a standard homomorphic multiplication function, this math is the central engine for **Key Switching**. By treating a secondary secret key as the "large constant" and applying this decomposition strategy, TFHE successfully transitions a ciphertext from one key (LWE or RLWE) to another without catastrophic noise growth.

***

## 11) Summary Checklist

* Naively multiplying a ciphertext by a **large** constant blows up noise.
* **Fix:** Decompose the large constant in base $$\beta$$ and recombine via an inner product with a **GLev** ciphertext.
* You can execute this exactly or approximately (rounding LSB before decomposition).
* This remains strictly a **building block** for later TFHE operations because the output fundamentally drops the neat $$\Delta$$-encoded format.


---

# 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-multiplication-by-a-large-constant.md?ask=<question>
```

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.