Homomorphic Ciphertext-to-Ciphertext Multiplication

TFHE supports multiplication of two ciphertexts in the form:

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m_{1}) \cdot {𝖦𝖲𝖶}_{\vec{s}, σ}^{β, l} (m_{2})

The 1st term

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m_{1} + e_{1})

comes from one of the following:

The 2nd term

{𝖦𝖲𝖶}_{\vec{s}, σ}^{β, l} (m_{2})

comes from one of the following:

{𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m_{1} + e_{1}) = (\vec{a}, b) \in ℤ_{q}^{k + 1}

, where

b = \vec{a} \cdot \vec{s} + Δ m_{1} + e_{1}

{𝖦𝖲𝖶}_{\vec{s}, σ}^{β, l} (m_{2}) = {{{𝖫𝖾𝗏}_{\vec{s}, σ}^{β, l} (- s_{i} \cdot m_{2})}_{i = 0}^{k - 1}, {𝖫𝖾𝗏}_{\vec{s}, σ}^{β, l} (m_{2})} \in ℤ_{q}^{(k + 1) \cdot l \cdot (k^{'} + 1)}

▹

from §B-6.1

{𝖦𝖲𝖶}_{\vec{s}, σ}^{β, l} (m_{2}) = \bar{𝖼𝗍} = ({\bar{𝖼𝗍}}_{0}, . {\bar{𝖼𝗍}}_{1}, \dots {\bar{𝖼𝗍}}_{k})

{\bar{𝖼𝗍}}_{i} = {𝖫𝖾𝗏}_{\vec{s}, σ}^{β, l} (- s_{i} \cdot m_{2})

for

0 \leq i \leq (k - 1)

𝖼𝗍 = {𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m_{1} + e_{1}) = (\vec{a}, b) = (a_{0}, a_{1}, \dots, a_{k - 1}, b) = ({𝖼𝗍}_{0}, {𝖼𝗍}_{1}, \dots, {𝖼𝗍}_{k})

𝖼𝗍 \cdot \bar{𝖼𝗍} = \sum_{i = 0}^{k} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} ({𝖼𝗍}_{i}), {\bar{𝖼𝗍}}_{i} ⟩

This means that multiplying two TFHE ciphertexts (one is in LWE and another in GSW) and decrypting the resulting LWE ciphertext gives the same result as multiplying their two original plaintexts.

Proof.

1.

\sum_{i = 0}^{k} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} ({𝖼𝗍}_{i}), {\bar{𝖼𝗍}}_{i} ⟩

= ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{0}), {\bar{𝖼𝗍}}_{0} ⟩ + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{1}), {\bar{𝖼𝗍}}_{1} ⟩ + \dots + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{k - 1}), {\bar{𝖼𝗍}}_{k - 1} ⟩ + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (b), {\bar{𝖼𝗍}}_{k} ⟩

▹

expanding the dot product of two vectors

2.

For

i = k

{𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (b) = (b_{1}, b_{2}, \dots, b_{l})

, where

b = b_{1} \frac{q}{β^{1}} + b_{2} \frac{q}{β^{2}} + \dots + b_{l} \frac{q}{β^{l}}

▹

from §A-6.2

{\bar{𝖼𝗍}}_{k} = {𝖫𝖾𝗏}_{\vec{s}, σ}^{β, l} (m_{2}) = ({𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} \frac{q}{β^{1}} + e_{2, 1}), {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} \frac{q}{β^{2}} + e_{2, 2}), \dots, {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} \frac{q}{β^{l}} + e_{2, l}))

Therefore:
$⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (b), {\bar{𝖼𝗍}}_{k} ⟩$
$= b_{1} \cdot {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} \frac{q}{β^{1}} + e_{2, 1}) + b_{2} \cdot {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} \frac{q}{β^{2}} + e_{2, 2}) + \dots + b_{l} \cdot {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} \frac{q}{β^{l}} + e_{2, l})$
$= {𝖫𝖶𝖤}_{\vec{s}, σ} (b_{1} m_{2} \frac{q}{β^{1}} + b_{1} e_{2, 1}) + {𝖫𝖶𝖤}_{\vec{s}, σ} (b_{2} m_{2} \frac{q}{β^{2}} + b_{2} e_{2, 2}) + \dots + {𝖫𝖶𝖤}_{\vec{s}, σ} (b_{l} m_{2} \frac{q}{β^{l}} + b_{l} e_{2, l})$ $▹$ from §C-3
$= {𝖫𝖶𝖤}_{\vec{s}, σ} (b_{1} m_{2} \frac{q}{β^{1}} + b_{2} m_{2} \frac{q}{β^{2}} + \dots + b_{l} m_{2} \frac{q}{β^{l}} + b_{1} e_{2, 1} + \dots + b_{l} e_{2, l})$ $▹$ from §C-1
$= {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} \cdot (b_{1} \frac{q}{β^{1}} + b_{2} \frac{q}{β^{2}} + \dots + b_{l} \frac{q}{β^{l}} + e^{⟨ k ⟩}))$ $▹$ where $e^{⟨ k ⟩} = \sum_{i = 1}^{l} b_{i} e_{2, i}$
$= {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} b + e^{⟨ k ⟩})$ $▹$ from §A-6.2

3.

For

0 \leq i \leq (k - 1)

{𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{i}) = (a_{⟨ i, 1 ⟩}, a_{⟨ i, 2 ⟩}, \dots, a_{⟨ i, l ⟩})

, where

a_{i} = a_{⟨ i, 1 ⟩} \frac{q}{β^{1}} + a_{⟨ i, 2 ⟩} \frac{q}{β^{2}} + \dots + a_{⟨ i, l ⟩} \frac{q}{β^{l}}

{\bar{𝖼𝗍}}_{i} = {𝖫𝖾𝗏}_{\vec{s}, σ}^{β, l} (- s_{i} m_{2})

$= ({𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} \frac{q}{β^{1}} + e_{i, 1}), {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} \frac{q}{β^{2}} + e_{i, 2}), \dots, {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} \frac{q}{β^{l}} + e_{i, l}))$

Therefore:
$⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{0}), {\bar{𝖼𝗍}}_{0} ⟩ + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{1}), {\bar{𝖼𝗍}}_{1} ⟩ + \dots + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{k - 1}), {\bar{𝖼𝗍}}_{k - 1} ⟩$
$= \sum_{i = 0}^{k - 1} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (a_{i}), {\bar{𝖼𝗍}}_{i} ⟩$
$= \sum_{i = 0}^{k - 1} (a_{⟨ i, 1 ⟩} \cdot {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} \frac{q}{β^{1}} + e_{i, 1}) + a_{⟨ i, 2 ⟩} \cdot {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} \frac{q}{β^{2}} + e_{i, 2}) +$

$\dots + a_{⟨ i, l ⟩} \cdot {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} \frac{q}{β^{l}} + e_{i, l}))$
$= \sum_{i = 0}^{k - 1} ({𝖫𝖶𝖤}_{\vec{s}, σ} (- a_{⟨ i, 1 ⟩} s_{i} m_{2} \frac{q}{β^{1}} + a_{⟨ i, 1 ⟩} e_{i, 1}) + {𝖫𝖶𝖤}_{\vec{s}, σ} (- a_{⟨ i, 2 ⟩} s_{i} m_{2} \frac{q}{β^{2}} + a_{⟨ i, 2 ⟩} e_{i, 2}) +$

$\dots + {𝖫𝖶𝖤}_{\vec{s}, σ} (- a_{⟨ i, l ⟩} s_{i} m_{2} \frac{q}{β^{l}} + a_{⟨ i, l ⟩} e_{i, l}))$
$= \sum_{i = 0}^{k - 1} {𝖫𝖶𝖤}_{\vec{s}, σ} (- a_{⟨ i, 1 ⟩} s_{i} m_{2} \frac{q}{β^{1}} - a_{⟨ i, 2 ⟩} s_{i} m_{2} \frac{q}{β^{2}} + \dots - a_{⟨ i, l ⟩} s_{i} m_{2} \frac{q}{β^{l}} + a_{⟨ i, 1 ⟩} e_{i, 1} + \dots + a_{⟨ i, l ⟩} e_{i, l})$
$= \sum_{i = 0}^{k - 1} {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} \cdot (a_{⟨ i, 1 ⟩} \frac{q}{β^{1}} + a_{⟨ i, 2 ⟩} \frac{q}{β^{2}} + \dots + a_{⟨ i, l ⟩} \frac{q}{β^{l}}) + a_{⟨ i, 1 ⟩} e_{i, 1} + \dots + a_{⟨ i, l ⟩} e_{i, l})$
$= \sum_{i = 0}^{k - 1} {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} a_{i} + e^{⟨ i ⟩})$ $▹$ where $e^{⟨ i ⟩} = a_{⟨ i, 1 ⟩} e_{i, 1} + \dots + a_{⟨ i, l ⟩} e_{i, l}$

4.

According to step 2 and 3,

\sum_{i = 0}^{k} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} ({𝖼𝗍}_{i}), {\bar{𝖼𝗍}}_{i} ⟩

= \sum_{i = 0}^{k - 1} {𝖫𝖶𝖤}_{\vec{s}, σ} (- s_{i} m_{2} a_{i} + e^{⟨ i ⟩}) + {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} b + e^{⟨ k ⟩})

= {𝖫𝖶𝖤}_{\vec{s}, σ} (\sum_{i = 0}^{k - 1} (- s_{i} m_{2} a_{i}) + m_{2} b + \sum_{i = 0}^{k} e^{⟨ i ⟩})

▹

addition of two LWE ciphertexts

= {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} b - \sum_{i = 0}^{k - 1} m_{2} a_{i} s_{i} + \sum_{i = 0}^{k} e^{⟨ i ⟩})

= {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} (b - \sum_{i = 0}^{k - 1} a_{i} s_{i} + \sum_{i = 0}^{k} e^{⟨ i ⟩}))

= {𝖫𝖶𝖤}_{\vec{s}, σ} (m_{2} (Δ m_{1} + e_{1}) + \sum_{i = 0}^{k} e^{⟨ i ⟩})

= {𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m_{1} m_{2} + m_{2} e_{1} + \sum_{i = 0}^{k} e^{⟨ i ⟩})

\approx {𝖫𝖶𝖤}_{\vec{s}, σ} (Δ m_{1} m_{2})

▹

given

m_{2} e_{1} + \sum_{i = 0}^{k} e^{⟨ i ⟩}

is small and thus

m_{2} e_{1}

is also small

□

To reduce the noise growth, noise bootstrapping is needed (will be discussed in §D-1.8).

D-1.6.1 Generalization to GLWE-to-GGSW Multiplication

We can further generalize TFHE’s LWE-to-GSW multiplication to GLWE-to-GGSW multiplication between the following two ciphertexts:

{𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (Δ M_{1}) \cdot {𝖦𝖦𝖲𝖶}_{\vec{S}, σ}^{β, l} (M_{2})

, where

M_{1}

M_{2}

, and

S

are

(n - 1)

-degree polynomials.

The 1st term

{𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (Δ M_{1})

comes from one of the following:

The 2nd term

{𝖦𝖦𝖲𝖶}_{\vec{S}, σ}^{β, l} (M_{2})

comes from one of the following:

{𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (Δ M_{1}) = (A_{0}, A_{1}, \dots, A_{k - 1}, B) \in R_{n, q}^{k + 1}

, where

B = \sum_{i = 0}^{k - 1} (A_{i} \cdot S_{i}) + Δ M_{1} + E

▹

from §B-4.2

{𝖦𝖦𝖲𝖶}_{\vec{S}, σ}^{β, l} (M_{2}) = {{{𝖦𝖫𝖾𝗏}_{\vec{S}, σ}^{β, l} (- S_{i} \cdot M_{2})}_{i = 0}^{k - 1}, {𝖦𝖫𝖾𝗏}_{\vec{S}, σ}^{β, l} (M_{2})} \in R_{⟨ n, q ⟩}^{(k + 1) \cdot l \cdot (k^{'} + 1)}

▹

from §B-6.1

{𝖦𝖦𝖲𝖶}_{\vec{S}, σ}^{β, l} (M_{2}) = \bar{C} = (\bar{C_{0}}, . \bar{C_{1}}, \dots \bar{C_{k}})

\bar{C_{i}} = {𝖦𝖫𝖾𝗏}_{\vec{S}, σ}^{β, l} (- S_{i} \cdot M_{2})

for

0 \leq i \leq (k - 1)

𝖼𝗍 = {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (Δ M_{1}) = (C_{0}, C_{1}, \dots, C_{k}) = (A_{0}, A_{1}, \dots, A_{k - 1}, B)

𝖼𝗍 \cdot \bar{C} = \sum_{i = 0}^{k} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (C_{i}), \bar{C_{i}} ⟩

This means that multiplying two TFHE ciphertexts (one is in GLWE and another in GGSW) and decrypting the resulting GLWE ciphertext gives the same result as multiplying their two original plaintexts.

Proof.

1.: $\sum_{i = 0}^{k} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (C_{i}), \bar{C_{i}} ⟩$
$= ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{0}), \bar{C_{0}} ⟩ + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{1}), \bar{C_{1}} ⟩ + \dots + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{k - 1}), {\bar{C}}_{k - 1} ⟩ + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (B), \bar{C_{k}} ⟩$
$▹$ expanding the dot product of two vectors
2.: For $i = k$ :
${𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (B) = (B_{1}, B_{2}, \dots, B_{l})$ , where $B = B_{1} \frac{q}{β^{1}} + B_{2} \frac{q}{β^{2}} + \dots + B_{l} \frac{q}{β^{l}}$ $▹$ from §A-6.2
${\bar{C}}_{k} = {𝖦𝖫𝖾𝗏}_{\vec{S}, σ}^{β, l} (M_{2}) = ({𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} \frac{q}{β^{1}}), {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} \frac{q}{β^{2}}), \dots, {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} \frac{q}{β^{l}}))$

Therefore:
$⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (B), \bar{C_{k}} ⟩$
$= B_{1} \cdot {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} \frac{q}{β^{1}}) + B_{2} \cdot {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} \frac{q}{β^{2}}) + \dots + B_{l} \cdot {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} \frac{q}{β^{l}})$
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (B_{1} M_{2} \frac{q}{β^{1}}) + {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (B_{2} M_{2} \frac{q}{β^{2}}) + \dots + {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (B_{l} M_{2} \frac{q}{β^{l}})$ $▹$ from §C-3
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (B_{1} M_{2} \frac{q}{β^{1}} + B_{2} M_{2} \frac{q}{β^{2}} + \dots + B_{l} M_{2} \frac{q}{β^{l}})$ $▹$ from §C-1
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} \cdot (B_{1} \frac{q}{β^{1}} + B_{2} \frac{q}{β^{2}} + \dots + B_{l} \frac{q}{β^{l}}))$
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} B)$ $▹$ from §A-6.2
3.: For $0 \leq i \leq (k - 1)$ :
${𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{i}) = (A_{⟨ i, 1 ⟩}, A_{⟨ i, 2 ⟩}, \dots, A_{⟨ i, l ⟩})$ , where $A_{i} = A_{⟨ i, 1 ⟩} \frac{q}{β^{1}} + A_{⟨ i, 2 ⟩} \frac{q}{β^{2}} + \dots + A_{⟨ i, l ⟩} \frac{q}{β^{l}}$
$\bar{C_{i}} = {𝖦𝖫𝖾𝗏}_{\vec{S}, σ}^{β, l} (- S_{i} M_{2}) = ({𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} \frac{q}{β^{1}}), {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} \frac{q}{β^{2}}), \dots, {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} \frac{q}{β^{l}}))$

Therefore:
$⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{0}), \bar{C_{0}} ⟩ + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{1}), \bar{C_{1}} ⟩ + \dots + ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{k - 1}), {\bar{C}}_{k - 1} ⟩$
$= \sum_{i = 0}^{k - 1} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (A_{i}), \bar{C_{i}} ⟩$
$= \sum_{i = 0}^{k - 1} (A_{⟨ i, 1 ⟩} \cdot {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} \frac{q}{β^{1}}) + A_{⟨ i, 2 ⟩} \cdot {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} \frac{q}{β^{2}}) + \dots + A_{⟨ i, l ⟩} \cdot {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} \frac{q}{β^{l}}))$
$= \sum_{i = 0}^{k - 1} ({𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- A_{⟨ i, 1 ⟩} S_{i} M_{2} \frac{q}{β^{1}}) + {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- A_{⟨ i, 2 ⟩} S_{i} M_{2} \frac{q}{β^{2}}) + \dots + {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- A_{⟨ i, l ⟩} S_{i} M_{2} \frac{q}{β^{l}}))$
$= \sum_{i = 0}^{k - 1} {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- A_{⟨ i, 1 ⟩} S_{i} M_{2} \frac{q}{β^{1}} + - A_{⟨ i, 2 ⟩} S_{i} M_{2} \frac{q}{β^{2}} + \dots + - A_{⟨ i, l ⟩} S_{i} M_{2} \frac{q}{β^{l}})$
$= \sum_{i = 0}^{k - 1} {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} \cdot (A_{⟨ i, 1 ⟩} \frac{q}{β^{1}} + A_{⟨ i, 2 ⟩} \frac{q}{β^{2}} + \dots + A_{⟨ i, l ⟩} \frac{q}{β^{l}}))$
$= \sum_{i = 0}^{k - 1} {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} A_{i})$
4.: According to step 2 and 3,
$\sum_{i = 0}^{k} ⟨ {𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (C_{i}), \bar{C_{i}} ⟩$
$= \sum_{i = 0}^{k - 1} {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (- S_{i} M_{2} A_{i}) + {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} B)$
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (\sum_{i = 0}^{k - 1} (- S_{i} M_{2} A_{i}) + M_{2} B)$ $▹$ addition of two GLWE ciphertexts
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (B M_{2} - \sum_{i = 0}^{k - 1} M_{2} A_{i} S_{i})$
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} (B - \sum_{i = 0}^{k - 1} A_{i} S_{i}))$
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (M_{2} (Δ M_{1} + E))$
$= {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (Δ M_{1} M_{2} + M_{2} E)$
$\approx {𝖦𝖫𝖶𝖤}_{\vec{S}, σ} (Δ M_{1} M_{2})$ $▹$ given $E$ is small and thus $M_{2} E$ is also small

□

D-1.6 Homomorphic Ciphertext-to-Ciphertext Multiplication

D-1.6.1 Generalization to GLWE-to-GGSW Multiplication