# **Homomorphic Encryption: a Toy Implementation in Python**

>**Motivation:**
We made this blog post as self-contained as possible, even though it was initially thought as a follow-up of [this tutorial given by OpenMined](https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/#buildanhomomorphicencryptionscheme). The starting point of our Python implementation is [this github gist](https://gist.github.com/youben11/f00bc95c5dde5e11218f14f7110ad289), which follows the Homomorphic Encryption scheme from [[FV12]](https://eprint.iacr.org/2012/144.pdf). The motivation behind [our implementation](https://github.com/Bitdefender-Crypto-Team/he-scheme) was for us to understand in detail the two techniques of [[FV12]](https://eprint.iacr.org/2012/144.pdf) used for ciphertext multiplication. We thought we might share this understanding through a blog post as well since it may be of interest to anyone using the [FV12] scheme in [TenSeal](https://github.com/OpenMined/TenSEAL) or [Seal](https://github.com/Microsoft/SEAL) libraries.
>
>**Disclaimer:**
Our toy implementation is not meant to be secure or optimized for efficiency. We did it to better understand the inner workings of the [FV12] scheme, so you can use it as a learning tool. Our full implementation can be found [here](https://github.com/Bitdefender-Crypto-Team/he-scheme).

In the first part of this blog post we are going to broadly explain what Homomorphic Encryption is and some closely related concepts. In the second part we will follow an example of such a scheme, namely the [[FV12]](https://eprint.iacr.org/2012/144.pdf) scheme, and discuss some of the details of our implementation.

# 1. What is Homomorphic Encryption (HE)?
Homomorphic Encryption (HE) enables a user to perform meaningful computations on sensitive data **while ensuring the privacy of the data**. This may sound paradoxical to anyone who has ever worked with encrypted data before: if you want to perform useful computations on the encrypted data (e.g. encrypted under classical algorithms like AES), you need to decrypt it first. But once decryption takes place, the privacy of the data is compromised. So how is it possible for HE to overcome this seeming contradiction? :crystal_ball: Well, the solution is highly non-trivial, as it took the cryptographic community more than 30 years to come up with a construction. The first [solution](https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf) was proposed by Craig Gentry in 2009 and was of theoretical interest only. Since then, a lot of research has been done (e.g. [[BGV11]](https://eprint.iacr.org/2011/277), [[FV12]](https://eprint.iacr.org/2012/144), [[CKKS16]](https://eprint.iacr.org/2016/421), [[FHEW]](https://github.com/lducas/FHEW), [[TFHE]](https://tfhe.github.io/tfhe/), [[GSW13]](https://eprint.iacr.org/2013/340)) to make these ideas more practical. By the end of this post you should have a basic understanding of how such a construction may work.

Besides the traditional encryption ($\mathsf{Enc}$), decryption ($\mathsf{Dec}$) and key generation ($\mathsf{Keygen}$) algorithms, an HE scheme also uses *an evaluation algorithm* ($\mathsf{Eval}$). **This is the distinguishing feature that makes computations on encrypted data possible.** :boom:
Let's consider the following example: Alice holds some personal information $m$ (e.g. her medical records and her family's medical history). There is also a company that makes very good predictions based on this kind of information, using a refined model, expressed as the functionality $F$ (e.g. a machine learning model). Alice is very interested in these predictions but is also reluctant to trust the company with her sensitive information. In the same time, the company can't just give their model to Alice to make the predictions herself. A solution using Homomorphic Encryption is given in the picture below.


Some important things to notice are:
* Alice sends her data **encrypted**, so the company never learns anything about $x$.
* Computing on the encrypted data $C$ does **not involve** Alice's secret key $sk$. Only her public key $pk$ is used.
* To obtain $C'$ as the encryption of $F(m)$, the evaluation algorithm uses the description of $F$ to do computations on $C$ (which encrypts $x$).
* By using her secret key, $sk$, Alice manages to recover the information that interests her, namely $F(m)$.

## A closer look at the Eval algorithm :mag_right:

All the existing HE constructions are *homomorphic* with respect to two basic operations: some kind of *addition* and some kind of *multiplication* (e.g. $+$ and $\times$ over the integers or the binary operations $\mathsf{XOR}$ and $\mathsf{AND}$, etc.). What we mean is that the scheme allows the efficient computation of $c_{add}$ from the individual ciphertexts $c_1=\mathsf{Enc}(pk,m_1)$ and $c_2=\mathsf{Enc}(pk,m_2)$ such that the decryption of $c_{add}$ yields $m_1+m_2$.


Analogously, the ciphertext $c_{mul}$ corresponding to multiplication, that decrypts to $m_1\times m_2$, is efficiently computable from the individual ciphertexts $c_1=\mathsf{Enc}(pk,m_1)$ and $c_2=\mathsf{Enc}(pk,m_2)$, respectively.


>There are classical examples of encryption schemes that are homomorphic with respect to only *one* operation. For instance:
>- the [**RSA**](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) encryption: $\mathsf{Enc}^{\mathsf{RSA}}_{e,N}(m):=m^e \bmod N$ is multiplicatively homomorphic as $m_1^e \cdot m_2^e \bmod N = (m_1 \cdot m_2)^{e} \bmod N$
>
>- the [**El-Gamal**](https://en.wikipedia.org/wiki/ElGamal_encryption) encryption: $\mathsf{Enc}^{\mathsf{EG}}_{g,h}(m)=(g^r,h^r\cdot m)$. It is easy to verify that the multiplicative property holds:
$$ (g^{r_1},h^{r_1}\cdot m_1)\cdot (g^{r_2},h^{r_2}\cdot m_2) =(g^{r_1+r_2},h^{r_1+r_2}\cdot (m_1\cdot m_2)).$$

All the existing HE schemes support only two types of computations on the encrypted data: some forms of addition and multiplication. This means that the $\mathsf{Eval}$ algorithm works only for functionalities $F$ that can be expressed using additions ($+$) and multiplications ($\times$). Another way of saying this is that HE schemes support only arithmetic circuits with addition/multiplication gates. Below we have the functionality $F(m_1,m_2,m_3,m_4)= m_1\times m_2\times m_4 + m_3\times m_4$ viewed as an arithmetic circuit.


### Why focus on homomorphisms with respect to *two* operations?
In principle, any functionality can be expressed using only two basic operations. For example, any binary circuit can be obtained using [NAND](https://en.wikipedia.org/wiki/NAND_gate) gates exclusively. In turn, a NAND operation consists of one addition and one multiplication: $\mathsf{NAND}(a,b)=a\times b + 1\bmod 2$, for any bits $a,b \in \{0,1\}$.

___
:bulb: Therefore it is enough to have an HE scheme that supports an unlimited number of additions and multiplications to be able to make any efficient computation we can think of on encrypted data.
___

## Homomorphic Encryption and "noisy" ciphertexts
The most practical HE constructions rely on the hardness of the [Ring Learning With Errors (RLWE)](https://en.wikipedia.org/wiki/Ring_learning_with_errors) problem for their security, as is the case with many [lattice-based cryptographic](https://en.wikipedia.org/wiki/Lattice-based_cryptography) constructions.
The inherent **"noise"** of the RLWE problem is inherited by all the schemes that are based on it. In particular, this "noise" element is present in every HE ciphertext and has a great impact on the parameters of the scheme.


___
:warning: The noise grows with every addition or multiplication we do on the ciphertexts. This is very relevant as decryption stops working correctly once the noise exceeds a certain threshold.
___

Because of this phenomenon, the number of multiplications and additions that can be carried out correctly on the ciphertext is limited. :boom: The parameters of such a scheme can be generated such that it can handle a minimum number of operations. But this minimum number must be decided in advance to set the parameters accordingly. We usually call such a scheme *Somewhat Homomorphic Encryption* (SHE) scheme. When the construction allows an unbounded number of operations we call such a scheme *Fully Homomorphic Encryption* (FHE). Even though we are not going to discuss it any further, we have to mention that it's possible to obtain FHE from SHE. In fact, Gentry [showed](https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf) how to transform any SHE (that can homomorphically evaluate its own decryption circuit) to FHE, through a computationally expensive process called *bootstrapping*. For applications that don't require many homomorphic evaluations SHE is preferred, as we want to avoid the computational overhead of the boostrapping.

# 2. A SHE scheme example

For the remaining of this blog post we will try to make the concepts that we have already presented more concrete, by discussing a *toy implementation* of the SHE scheme construction of [[FV12]](https://eprint.iacr.org/2012/144). Our main goal is to understand how *relinearization* and *modulus-switching* are used to obtain ciphertext multiplication.

**Notations:** For an integer $q$, by $\mathbb{Z}_q$ we mean the set $\{0,1,\ldots,q-1\}$. We denote by $[a]_q$ the remainder of $a$ *modulo* $q$. For example $[18]_7 = 4$. When rounding to the nearest integer, we use $\lfloor \cdot \rceil$. The basic elements we work with will not be integers, but merely *polynomials with integer coefficients*. We also work with *noisy polynomials*, whose coefficients are sampled according to some error distribution $\chi$. We bound such errors by their largest absolute value of their coefficients, denoted as $\|\cdot\|$.

## Quick recap on working with polynomials

The HE scheme we are going to describe deals with *adding and multiplying polynomials*. Here we present a quick example of how to work with polynomials, so that we all have the same starting point. If you already know how to do this, you can skip it.

First thing, let's add and multiply polynomials *modulo some polynomial $f$*. This "modulo $f$" thing simply means that we add and multiply the polynomials in the usual way, but we take the remainders of the results when divided by $f$. When we do these additions and multiplications $\bmod f$, we sometimes say in a fancy way that we are working in the *ring* $\mathbb{Z}[x]/(f)$ of reduced polynomials.:ring:

Let's take $f = x^4 +1$. If we look at $p(x) =x^5$, then $p(x) = x \cdot (x^4 + 1) - x$. Therefore, when taking the reminder we get $p(x) = -x \bmod f.$ For faster computations $\bmod f$ you can use this trick: when making $\bmod f$, simply replace $x^4$ by $-1$, $x^5$ by $-x$ and so on.

Let's consider two polynomials $a(x) = x^3 + x^2 + 7$ and $b(x) = x^2 + 11x$. Then:

$$a(x)+b(x) \bmod f = x^3 + 2x^2 + 11x + 7 \text { mod }f.$$

Here nothing special happened. Let's multiply them:

$$\begin{eqnarray}
a(x) \cdot b(x) \bmod f &=& (x^3 + x^2 + 7)\cdot (x^2 +11x) \text { mod }f \\
&=& x^5 + 11x^4 + x^4 + 11x^3 + 7x^2 + 77x \text { mod }f\\
&=& -x - 11 - 1 + 11x^3 + 7x^2 + 77x \text { mod }f \\
&=& 11x^3 + 7x^2 + 76x - 12 \text { mod }f.
\end{eqnarray}$$

These operations are implemented [here](https://github.com/Bitdefender-Crypto-Team/he-scheme/blob/main/rlwe_he_scheme_updated.py) and make use of the cool [Numpy](https://numpy.org/doc/stable/reference/routines.polynomials.html) library:

import numpy as np
from numpy.polynomial import polynomial as poly

#------Functions for polynomial evaluations mod poly_mod only------
def polymul_wm(x, y, poly_mod):
    """Multiply two polynomials
    Args:
        x, y: two polynomials to be multiplied.
        poly_mod: polynomial modulus.
    Returns:
        A polynomial in Z[X]/(poly_mod).
    """ 
    return poly.polydiv(poly.polymul(x, y), poly_mod)[1] 
def polyadd_wm(x, y, poly_mod):
    """Add two polynomials
    Args:
        x, y: two polynomials to be added.
        poly_mod: polynomial modulus.
    Returns:
        A polynomial in Z[X]/(poly_mod).
    """ 
    return poly.polydiv(poly.polyadd(x, y), poly_mod)[1] 

Now let's go one step further and see how we perform these operations of polynomials not just modulo $f$, *but also modulo some integer $q$*. As you might expect, the coefficients of these polynomials are also reduced modulo $q$, so they always take integer values from $0$ to $q-1.$ This time, we say that we are working the ring of reduced polynomials $\mathbb{Z}_q[x]/(f)$. :ring:

Let's take the previous example, $f = x^4+1$, $a(x)=x^3+x^2+7$, $b(x)=x^2+11x$ and consider $q =5$. We can think of $a$ and $b$ as already taken $\bmod f$. If we take them further modulo $q$, then $[a(x)]_q = x^3 + x^2 +2$ and $[b(x)]_q = x^2+x$. Moreover,

$$[a(x) + b(x)]_q = x^3 + x^2 +2+ x^2 + x = x^3 + 2x^2 + x+2$$

and

$$
\begin{eqnarray}
[a(x) \cdot b(x)]_q &=& (x^3 + x^2+2) \cdot (x^2 + x)\\
&=& x^5 + x^4 + x^4 +x^3+2x^2 + 2x\\
&=& -x -1 -1 + x^3 +2x^2+2x\\
&=& x^3+2x^2+x+3
\end{eqnarray}
$$

where at the last but one equality we performed modulo $f = x^4+1$ and at the last one, modulo $q=5$.

These operations already mentioned are $\texttt{polyadd}$ and $\texttt{polymul}$ implemented [here](https://github.com/Bitdefender-Crypto-Team/he-scheme/blob/main/rlwe_he_scheme_updated.py).
## The Fan-Vercauteren ([FV12]) scheme

Next, we recall the basic ($\mathsf{Keygen}$, $\mathsf{Enc}$, $\mathsf{Dec}$) algorithms of [**the [FV12] scheme**](https://eprint.iacr.org/2012/144.pdf). These (almost identical) algorithms have already been described [here](https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/#buildanhomomorphicencryptionscheme), but for the sake of completeness we present them as well. Then we will explain in detail the core of the $\mathsf{Eval}$ algorithm: the addition and multiplication of the ciphertexts. *Spoiler alert*: We will especially focus on the two *Relinearization* techniques that enable ciphertext multiplication.

>Let $n$ be power of 2. We call a positive integer $t$ the *plaintext modulus* and a positive integer $q$ as the *ciphertext modulus*. We set $\Delta = \lfloor q/t \rfloor$. The scheme involves adding and multiplying polynomials in $R_t = \mathbb{Z}_t[x]/(x^n+1)$, on the plaintext side, and adding and multiplying polynomials in $R_q = \mathbb{Z}_q[x]/(x^n+1)$, on the ciphertext side. We also denote by $R$ the ring $\mathbb{Z}[x]/(x^n+1).$

>:warning: **Disclaimer**: From now on all polynomial operations are assumed to be mod $x^n+1$, even if we don't mention it every time.

+ $\mathsf{Keygen}$: The *secret key* $sk$ is a secret binary polynomial $s$ in $R$, i.e. its coefficients are either 0 or 1. The *public key* $pk$ is created as follows: we sample $a$ uniformly over $R_q$ and an error $e$ according to some error distribution $\chi$ over $R$ and output $pk = ([-(a\cdot s+e)]_q,a) \in R_q \times R_q$.

>:exclamation: Notice that hardness of the [RLWE](https://en.wikipedia.org/wiki/Ring_learning_with_errors#The_RLWE_Problem) problem prevents the computation of the secret $s$ from the public key.

The way we generate the uniform polynomials and the binary polynomials is implemented as $\texttt{gen_uniform_poly}$ and as $\texttt{gen_binary_poly}$ respectively. The error distribution $\chi$ is usually taken as a discretized variant of the [*Normal distribution*](https://en.wikipedia.org/wiki/Normal_distribution), over $\mathbb{Z}^n$, and is implemented as $\texttt{gen_normal_poly}$. They can be found [here](https://github.com/Bitdefender-Crypto-Team/he-scheme/blob/main/rlwe_he_scheme_updated.py).

def keygen(size, modulus, poly_mod, std1):
    """Generate a public and secret keys.
    Args:
        size: size of the polynoms for the public and secret keys.
        modulus: coefficient modulus.
        poly_mod: polynomial modulus.
        std1: standard deviation of the error.
    Returns:
        Public and secret key.
    """
    s = gen_binary_poly(size)
    a = gen_uniform_poly(size, modulus)
    e = gen_normal_poly(size, 0, std1)
    b = polyadd(polymul(-a, s, modulus, poly_mod), -e, modulus, poly_mod)
    return (b, a), s

+ $\mathsf{Enc}$: To encrypt a *plaintext* $m \in R_t$, we let $p_0 = pk[0]$ and $p_1 = pk[1]$, sample $u, e_1, e_2$ according to $\chi$ over $R$ and output the *ciphertext*

$$\mathsf{Enc}(pk,m) = ([p_0 \cdot u +e_1 + \Delta \cdot m]_q,[p_1 \cdot u + e_2]_q) \in R_q \times R_q$$

>:exclamation: Due to the [RLWE](https://en.wikipedia.org/wiki/Ring_learning_with_errors#The_RLWE_Problem) assumption, the ciphertexts "look" uniformly random to a possible attacker, so they don't reveal any information about the plaintext.

In the piece of code below, the message we want to encrypt, $\mathtt{pt}$, is an integer vector of length at most $n$, with entries in the set $\{0, 1,\ldots, t-1\}$. Before we encode it as a polynomial in $m \in R_t$, we pad it with enough zeros to make it a length $n$ vector.

def encrypt(pk, size, q, t, poly_mod, pt, std1): 
    """Encrypt an integer vector pt.
    Args:
        pk: public-key.
        size: size of polynomials.
        q: ciphertext modulus.
        t: plaintext modulus.
        poly_mod: polynomial modulus.
        pt: plaintext message, as an integer vector (of length <= size) with entries mod t.
    Returns:
        Tuple representing a ciphertext.
    """
    m = np.array(pt + [0] * (size - len(pt)), dtype=np.int64) % t
    delta = q // t
    scaled_m = delta * m
    e1 = gen_normal_poly(size, 0, std1)
    e2 = gen_normal_poly(size, 0, std1)
    u = gen_binary_poly(size)
    ct0 = polyadd(
        polyadd(
            polymul(pk[0], u, q, poly_mod),
            e1, q, poly_mod),
        scaled_m, q, poly_mod
    )
    ct1 = polyadd(
        polymul(pk[1], u, q, poly_mod),
        e2, q, poly_mod
    )
    return (ct0, ct1)

+ $\mathsf{Dec}$: Given a ciphertext $ct = (ct[0], ct[1])$, we decrypt using the secret key $sk=s$ as follows:

$$\mathsf{Dec}(ct,sk) = \Bigg[ \Bigg\lfloor \frac{t\cdot [ct[0]+ct[1]\cdot s]_q}{q} \Bigg\rceil \Bigg]_t \in R_t$$

:no_entry: Let's stop for a bit and check together how the $\mathsf{Dec}$ algorithm works. The intuition behind it is that $pk[0] + pk[1]\cdot sk$ is "small". This implies that $ct[0] + ct[1]\cdot sk$ is "close" to the scaled message $\Delta \cdot m$. To recover the message $m$, we get rid of $\Delta$ $(\approx q/t)$ and then apply rounding to shave off the "small" noise. Let's check that this intuition actually works.

First, we set the notation $ct(s) := ct[0] + ct[1] \cdot s$, which we'll frequently use for the rest of the post.

If we go back to see how $ct$ and $pk$ were defined, we get:

$$
\begin{eqnarray}
[ct(s)]_q &=& [(pk[0] \cdot u + e_1 + \Delta \cdot m) + (pk[1] \cdot u + e_2) \cdot s]_q\\
&=& [-(a\cdot s + e)\cdot u+e_1 + \Delta \cdot m + a \cdot u \cdot s + e_2 \cdot s]_q\\
&=& \Delta \cdot m - e \cdot u + e_1 + e_2 \cdot s\\
&=& \Delta \cdot m + v,
\end{eqnarray}
$$

which is nothing but the scaled plaintext $m$ with some *"small" noise* $v$. Because we always have $\|\Delta m + v\| < q$, reducing it $\bmod q$ has no effect (e.g. $[4]_{7} = 4$). As long as the noise $\|v\|<\Delta/2$, we can always recover the correct $m$.


For example, in the picture above, any green point will decrypt to $2$ when we scale it by $t/q$ $(\approx 1/\Delta)$ and round it. Analogously, any dark-brown point will decrypt to $3$.

We can implement this evaluation, as $\texttt{scaled_pt}$ below, by performing polynomial operations in $R_q$. You will see that this equation,

$$[ct(s)]_q = [ct[0] + ct[1] \cdot s]_q = \Delta \cdot m + v,$$

which we will call *the decryption equation*, becomes really useful in deriving ways of computing on ciphertexts. [Here](https://github.com/Bitdefender-Crypto-Team/he-scheme/blob/main/rlwe_he_scheme_updated.py) we provide the code for the $\mathsf{Dec}$ algorithm:

def decrypt(sk, q, t, poly_mod, ct):
    """Decrypt a ciphertext.
    Args:
        sk: secret-key.
        size: size of polynomials.
        q: ciphertext modulus.
        t: plaintext modulus.
        poly_mod: polynomial modulus.
        ct: ciphertext.
    Returns:
        Integer vector representing the plaintext.
    """
    scaled_pt = polyadd(
        polymul(ct[1], sk, q, poly_mod),
        ct[0], q, poly_mod
    )
    decrypted_poly = np.round(t * scaled_pt / q) % t
    return np.int64(decrypted_poly)

### Homomorphic operations of [FV12]

As explained in the first part, the $\mathsf{Eval}$ algorithm works only for functionalities that can be expressed using addition $(+)$ or multiplication $(\times)$.

Let's take two ciphertexts $ct_1 = \mathsf{Enc}(pk,m_1)$ and $ct_2 = \mathsf{Enc}(pk,m_2)$. We want to see how to construct ciphertexts that decrypt both the addition, $m_1+m_2$, and the multiplication, $m_1\cdot m_2$. Also, keep in mind that when performing operations on $m_1$ and $m_2$, we are actually doing them *modulo $x^n+1$* and *modulo $t$*, since these are the plaintext operations from $R_t = \mathbb{Z}_t[x]/(x^n+1)$.

Let's write the decryption equations of $ct_1$ and $ct_2$:

$$[ct_1(s)]_q = \Delta \cdot m_1 + v_1 \text{ and } [ct_2(s)]_q = \Delta \cdot m_2 + v_2$$

+ **Addition** If we simply add the decryption equations, we get

$$[ct_1(s)]_q + [ct_2(s)]_q = \Delta \cdot (m_1+m_2) + v_1 + v_2.$$

But wait a sec, we need to decrypt to $m_1+m_2$ modulo $t$! Notice that $m_1 + m_2 = t \cdot \epsilon + [m_1+m_2]_t$, for some binary polynomial $\epsilon$. Using the notation $r_t(q):= q- \Delta \cdot t$ (this is just the remainder of $q$ divided by $t$) we get:

\begin{eqnarray}
[ct_1(s) + ct_2(s)]_q &=& \Delta \cdot [m_1+m_2]_t + \Delta \cdot t \cdot \epsilon + v_1 + v_2 \\
&=& \Delta \cdot [m_1+m_2]_t + (q-r_t(q)) \cdot \epsilon + v_1+v_2 \\
&\equiv& \Delta \cdot [m_1+m_2]_t + v_{add} \text{ mod }q,
\end{eqnarray}

where $v_{add} = v_1+v_2-r_t(q) \cdot \epsilon$.
This suggests to set the new ciphertext as $c_{add}=(ct_1[0]+ct_2[0], \text{ }ct_1[1]+ct_2[1])$, which can be computed without the knowledge of the secret key $s$. Therefore, $c_{+} = ct_1 + ct_2$ decrypts to the sum, $[m_1+m_2]_t$, as long as the new "noise", $v_{add}$, is smaller than $\Delta/2$.

>:bulb: The **noise growth** for **addition** is quite slow as $$
\|v_{add}\|<\|v_1\|+\|v_2\| + t < 2B+t,
$$where $B$ is an upper bound on the "noise" of the ciphertexts that were added.
This means we can probably do many additions before decryption stops working.

To add ciphertexts, it seems like we only need to add polynomials in $R_q$. So, ciphertext addition is a piece of cake :cake:.

def add_cipher(ct1, ct2, q, poly_mod):
    """Add a ciphertext and a ciphertext.
    Args:
        ct1, ct2: ciphertexts.
        q: ciphertext modulus.
        poly_mod: polynomial modulus.
    Returns:
        Tuple representing a ciphertext.
    """
    new_ct0 = polyadd(ct1[0], ct2[0], q, poly_mod)
    new_ct1 = polyadd(ct1[1], ct2[1], q, poly_mod)
    return (new_ct0, new_ct1)

+ **Multiplication** Producing a new ciphertext that decrypts the product of the two messages is not that easy. But we should still try :crossed_fingers:. The first idea that comes to mind is to simply multiply the decryption equations. It worked for addition, so maybe it works here as well.

\begin{eqnarray}
ct_1(s) \cdot ct_2(s) = \Delta^2 \cdot m_1m_2 + \Delta\cdot (m_1v_2+m_2v_1) + v_1v_2. \text{ } \ (1)
\end{eqnarray}

If we scale by $t/q$ to get rid of one $\Delta$, we get something that looks like what we want.

\begin{eqnarray}
\frac{t}{q}\cdot ct_1(s) \cdot ct_2(s) \approx \Delta \cdot m_1m_2 + (m_1v_2+m_2v_1)
\end{eqnarray}

It seems we are on the right track. Let's examine these expressions further. Recall the notations $ct_1(s) = ct_1[0] + ct_1[1]\cdot s$ and $ct_2(s) = ct_2[0] + ct_2[1]\cdot s.$ Both of them are *linear* in $s$, but their multiplication is *quadratic* in $s$:
\begin{eqnarray} ct_1\cdot ct_2(s) = ct_1[0]\cdot ct_2[0] + (ct_1[0]\cdot ct_2[1] + ct_1[1]\cdot ct_2[0])s +ct_1[1]\cdot ct_2[1]s^2,
\end{eqnarray}

which we will write, in short, as $ct_1 \cdot ct_2 (s) = c_0^\times + c_1^{\times}\cdot s + c_2^{\times} \cdot s^2.$

But what about the right hand side? Keep in mind that we work with plaintexts $m_i \in R_t$, so we should take $m_1m_2$ with *coefficients modulo $t$*. Therefore, we can apply the same trick as we did for addition: we divide by $t$ and write $m_1m_2 = tr_m + [m_1m_2]_t$, where $r_m$ is an integer polynomial. Skipping a lot of details, we end up with:

\begin{eqnarray}
t/q \cdot ct_1 \cdot ct_2(s) &=& \Delta \cdot [m_1m_2]_t + u_2
\end{eqnarray}

for $u_2$ a polynomial with *rational* coefficients. Looks like we're getting closer to obtaining the decryption equation. We can now write the original expression $(1)$ as:

$$t/q \cdot c_0^\times + t/q \cdot c_1^{\times} \cdot s + t/q \cdot c_2^{\times} \cdot s^2 = \Delta \cdot [m_1 m_2]_t + u_2$$

Hm.. these coefficients look *rational polynomials*. Recall that the ciphertext has as elements *integer polynomials*. So we round each coefficient appearing in the left hand side to their nearest integers and then reduce the whole equation modulo $q$:
$$[\lfloor t/q \cdot c_0^{\times} \rceil]_q + [\lfloor t/q \cdot c_1^{\times}\rceil]_q \cdot s + [\lfloor t/q \cdot c_2^{\times}\rceil]_q \cdot s^2 = \Delta \cdot [m_1 m_2]_t + u_3 \text{ } \ (2)$$

where $u_3$ is a "small" integer polynomial, that represents the "noise" after one multiplication.

>:bulb: The **noise growth** for **multiplication** grows a lot faster:
$$
\|u_3\| \leq 2 \cdot n \cdot t \cdot B \cdot (2n+1)\cdot (n+1) + 8t^2 \cdot n^2.
$$
>
>where $B$ is an upper bound for the "noise" of the ciphertexts that were multiplied. We refer the enthusiastic reader for more details to [[[FV12] Lem. 2]](https://eprint.iacr.org/2012/144.pdf).

Phew, seems like we are done: we can consider as a ciphertext decrypting to $[m_1m_2]_t$ the tuple of scaled and rounded coefficients mod $q$ from left hand side of $(2)$, denoted by $(c_0, c_1, c_2)$. Of course, for a correct decryption, $u_3$ should have small enough coefficients. You can see below how these coefficients are computed in Python:

def multiplication_coeffs(ct1, ct2, q, t, poly_mod):
    """Multiply two ciphertexts.
        Args:
            ct1: first ciphertext.
            ct2: second ciphertext
            q: ciphertext modulus.
            t: plaintext modulus.
            poly_mod: polynomial modulus.
        Returns:
            Triplet (c0,c1,c2) encoding the multiplied ciphertexts.
        """

    c_0 = np.int64(np.round(polymul_wm(ct1[0], ct2[0], poly_mod) * t / q)) % q
    c_1 = np.int64(np.round(polyadd_wm(polymul_wm(ct1[0], ct2[1], poly_mod), polymul_wm(ct1[1], ct2[0], poly_mod), poly_mod) * t / q)) % q 
    c_2 = np.int64(np.round(polymul_wm(ct1[1], ct2[1], poly_mod) * t / q)) % q
    return c_0, c_1, c_2

But, as a popular movie character would say, **"Houston, we have a problem"**. This tuple of coefficients has size 3, **not 2 as the usual ciphertext**. Moreover, the size of such tuple will grow linearly in the number of further multiplications performed on the ciphertexts. In order to restore the size of the ciphertext as 2, we will make use of the so called *relinearization technique*. :boom:

## Relinearization
>:bulb: The idea of **Reliniarization** is to reduce the triplet $(c_0,c_1,c_2)$ to a ciphertext pair $(c_0',c_1') \in R_q \times R_q$ that recovers $[m_1\cdot m_2]_t$ when decrypted with the usual decryption algorithm. We would like to produce a pair $(c_0',c_1')$, without using the secret $s$, such that:
>
>
>$\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ :heavy_check_mark: $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$$\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $[c_0' + s\cdot c_1']_q = [c_0 + c_1\cdot s + c_2 \cdot s^2 + r ]_q$,
>
>where $r$ is a "small" error. The correct decryption will be possible, as the "small" error $r$ will vanish because of the rounding in decryption.

As the name suggests it, we transform the degree 2 polynomial, $c_0+c_1\cdot s+c_2 \cdot s^2$ into a linear polynomial, i.e. of degree 1. This involves giving extra info about $s^2$. Using a special public key, called *relinearization key*, we can *linearize* $c_2 \cdot s^2$ (up to some small error) as

$$[c_{20}+c_{21} \cdot s]_q = [c_2\cdot s^2 + e_{relin}]_q.$$

Therefore, by Equation $(2)$, we can get a standard ciphertext pair as
\begin{eqnarray}
c_{mul} =(c_0+c_{20}, c_1+c_{21}),
\end{eqnarray}

that correctly decrypts to $[m_1m_2]_t$, as you can see below:
\begin{eqnarray}
[c_0 + c_{20} + s\cdot (c_1 + c_{21})]_q = [c_0 + c_1 \cdot s + c_2 \cdot s^2 + e_{relin}]_q = \Delta \cdot [m_1m_2]_t + v_{mult},
\end{eqnarray}

where $v_{mult} = u_3 + e_{relin}.$ Therefore, $c_{mul}$ decrypts correctly to $[m_1m_2]_t$ if $\|v_{mult}\|$ is less than $\Delta/2$. So yay! we finally know how to get a ciphertext encoding multiplication!

## Different versions of relinearization

To complete this discussion, we need to see how to construct the linear approximation of $c_2 \cdot s^2$ and find out what the relinearization key is about. For this, we will go a bit deeper into (technical) details. Don't panic, we'll take you step by step. :smile:

We are going to present two versions of linearizing $c_2\cdot s^2$. First, keep in mind that $s^2$ should not be known, so we give the relinearization key as a *masked version* of $s^2$.
Let's think of the following situation: say we include in the public key the following *relinearization* key:

\begin{eqnarray}
rlk = ([-(a\cdot s+e)+s^2]_q,a),
\end{eqnarray}

for some uniform $a$ in $R_q$ and a small error $e$.

:exclamation: Intuitively, the secret $s^2$ is hidden by something that looks like an [RLWE](https://en.wikipedia.org/wiki/Ring_learning_with_errors#The_RLWE_Problem) sample. Notice that,

$$rlk[0] + rlk[1] \cdot s = s^2 + e.$$

To obtain the approximation of $c_2\cdot s^2$ we should multiply the above expression by $c_2$. By doing so, we end up with the rather large-norm term $c_2\cdot e$, due to the size of the coefficients of $c_2$. We cannot allow such a large "noise" as it will interfere with decryption. To avoid this "noise" blow-up we will employ two techniques described below.

### :boom: Relinearization: Version 1

One strategy is to use base $T$ decomposition of the coefficients of $c_2$ to slice $c_2$ into components of small norm. To do this, we pick a base $T$ and write each coefficient of $c_2$ in this base. Recall that $c_2$ is a integer polynomial, modulo $x^n+1$, so of degree at most $n-1$. If we write $c_2$ as a polynomial:

$$ c_2(x) = c_2[0] + c_2[1]\cdot x+\ldots+c_2[1]\cdot x^{n-1}$$

then we can decompose each coefficient $c_2[i]$ in base $T$. Notice that since $c_2$ has coefficients in $[0,q-1]$, the maximum power appearing in these representations is $T^{\ell}$, where $\ell = \lfloor \log_T(q)\rfloor$. For base decomposition we use the function $\texttt{int2base}$:

def int2base(n, b):
    """Generates the base decomposition of an integer n.
    Args:
        n: integer to be decomposed.
        b: base.
    Returns:
        array of coefficients from the base decomposition of n
        with the coeff[i] being the coeff of b ^ i.
    """
    if n < b:
        return [n]
    else:
        return [n % b] + int2base(n // b, b)  

The relinearisation key, $rlk$ in this version, consists of masked variants of $T^i \cdot s^2$, instead of $s^2$. More precisely, for $0 \leq i \leq \ell$, this is defined as follows:

$$(rlk0[i], rlk1[i]) = ([-(a_i \cdot s + e_i) + T^i\cdot s^2]_{q}, a_i)$$

for $a_i$ chosen uniformly in $R_q$ and $e_i$ chosen according to the distribution $\chi$ over $R$ (yep, same error distribution as in the description of the scheme). Below you can find the implementation of the function that generates the evaluation (relinearization) key $(rlk0[i],rlk1[i])_{0\leq i\leq\ell}$.

def evaluate_keygen_v1(sk, size, modulus, T, poly_mod, std2):
    """Generate a relinearization key using version 1.
        Args:
            sk: secret key.
            size: size of the polynomials.
            modulus: coefficient modulus.
            T: base.
            poly_mod: polynomial modulus.
            std2: standard deviation for the error distribution.
        Returns:
            rlk: relinearization key.

        """
    n = len(poly_mod) - 1
    l = np.int(np.log(modulus) / np.log(T))
    rlk0 = np.zeros((l + 1, n), dtype=np.int64)
    rlk1 = np.zeros((l + 1, n), dtype=np.int64)
    for i in range(l + 1):
        a = gen_uniform_poly(size, modulus)
        e = gen_normal_poly(size, 0, std2)
        secret_part = T ** i * poly.polymul(sk, sk)
        b = np.int64(polyadd(
        polymul_wm(-a, sk, poly_mod),
        polyadd_wm(-e, secret_part, poly_mod), modulus, poly_mod))

        b = np.int64(np.concatenate( (b, [0] * (n - len(b)) ) )) # pad b 
        a = np.int64(np.concatenate( (a, [0] * (n - len(a)) ) )) # pad a    

        rlk0[i] = b
        rlk1[i] = a
    return rlk0, rlk1

Now, given $rlk$, let's look at how we compute the linear approximation of $c_2 \cdot s^2$. Let the polynomials $c_2(i)$ be the base $T$ decomposition of $c_2$, such that:

$$c_2 = \displaystyle \sum_{i=0}^{\ell} c_2(i)\cdot T^i.$$

We can get the linear approximation given by $(c_{20}, c_{21})$, where:

$$c_{20} = \sum_{i=0}^{\ell} rlk0[i]\cdot c_2(i) \text{ and } c_{21} = \sum_{i=0}^{\ell} rlk1[i]\cdot c_2(i).$$

Therefore, $c_{20} + c_{21} \cdot s = c_2 \cdot s^2 + e_{\text{relin_v1}},$ where $e_{\text{relin_v1}}$ is an error term from $R_q$, since

$$
\begin{eqnarray}
c_{20} + c_{21}
\cdot s^2 &=& \sum_{i=0}^{\ell} [-(a_i\cdot s+e_i)+T^i\cdot s^2] c_2(i) + \sum_{i=0}^{\ell} a_i \cdot s \cdot c_2(i)\\
&=& -\sum_{i=0}^{\ell} e_i \cdot c_2(i) + c_2 \cdot s^2.
\end{eqnarray}
$$

>:bulb: By doing base $T$ decomposition we get a "small" **relinearization noise**:
\begin{eqnarray}
\|e_{\text{relin_v1}}\| \leq (\ell+1)\cdot B \cdot T \cdot n/2
\end{eqnarray}
>
>where $B$ is an upper bound on the errors $e_i$.

:question: Now the question is how to compute the polynomials $c_2(i)$: So far, we have stored the representations of each coefficient of $c_2$, $c_2[i]$, let's say as rows in an $n \times (\ell+1)$ matrix $\mathtt{Reps}$. Therefore

$$c_2[i] = \mathtt{Reps}[i][0] + \mathtt{Reps}[i][1] \cdot T+ \ldots + \mathtt{Reps}[i][\ell] \cdot T^{\ell}.$$

If we multiply this by $x^i$, we get:

$$c_2[i] \cdot x^i = \mathtt{Reps}[i][0] \cdot x^i + \mathtt{Reps}[i][1] \cdot x^i \cdot T+ \ldots + \mathtt{Reps}[i][\ell] \cdot x^i \cdot T^{\ell}.$$

Summing up all these for each $0\leq i \leq n-1$, on the left hand side we actually get $c_2$:

$$c_2 = \displaystyle \sum_{i=0}^{n-1} \mathtt{Reps}[i][0] \cdot x^i + (\sum_{i=0}^{n-1}\mathtt{Reps}[i][1] \cdot x^i) \cdot T+ \ldots + (\sum_{i=0}^{n-1} \mathtt{Reps}[i][\ell] \cdot x^i) \cdot T^{\ell}.$$

So, if we denote the above sums by polynomials $c_2(j)$, we simply get

$$c_2 = \displaystyle \sum_{j=0}^{\ell} c_2(j)\cdot T^j.$$

Phew, what a relief! Notice that the coefficients for each polynomial $c_2(j)$ are given by the $j$-th column of $\mathtt{Reps}$.

So after all this math, we finally got the linear approximation of $c_2 \cdot s^2$ and thus, we can derive the standard ciphertext encoding the multiplication of the plaintexts. Here comes the code:

def mul_cipher_v1(ct1, ct2, q, t, T, poly_mod , rlk0 , rlk1):
    """Multiply two ciphertexts.
    Args:
        ct1: first ciphertext.
        ct2: second ciphertext
        q: ciphertext modulus.
        t: plaintext modulus.
        T: base
        poly_mod: polynomial modulus.
        rlk0, rlk1: output of the EvaluateKeygen_v1 function.
    Returns:
        Tuple representing a ciphertext.
    """
    n = len(poly_mod) - 1
    l = np.int64(np.log(q) / np.log(T))  #l = log_T(q)

    c_0, c_1, c_2 = multiplication_coeffs(ct1, ct2, q, t, poly_mod)
    c_2 = np.int64(np.concatenate( (c_2, [0] * (n - len(c_2))) )) #pad
   
    #Next, we decompose c_2 in base T: 
    #more precisely, each coefficient of c_2 is decomposed in base T such that c_2 = sum T**i * c_2(i)
    Reps = np.zeros((n, l + 1), dtype = np.int64)
    for i in range(n):
        rep = int2base(c_2[i], T)
        rep2 = rep + [0] * (l + 1 - len(rep)) #pad with 0
        Reps[i] = np.array(rep2, dtype=np.int64)
    # Each row Reps[i] is the base T representation of the i-th coefficient c_2[i].
    # The polynomials c_2(j) are given by the columns Reps[:,j].

    c_20 = np.zeros(shape=n)
    c_21 = np.zeros(shape=n)
    # Here we compute the sums: rlk[j][0] * c_2(j) and rlk[j][1] * c_2(j) 
    for j in range(l + 1):
        c_20 = polyadd_wm(c_20, polymul_wm(rlk0[j], Reps[:,j], poly_mod), poly_mod)
        c_21 = polyadd_wm(c_21, polymul_wm(rlk1[j], Reps[:,j], poly_mod), poly_mod)

    c_20 = np.int64(np.round(c_20)) % q
    c_21 = np.int64(np.round(c_21)) % q

    new_c0 = np.int64(polyadd_wm(c_0, c_20, poly_mod)) % q
    new_c1 = np.int64(polyadd_wm(c_1, c_21, poly_mod)) % q

    return (new_c0, new_c1)

### :boom: Relinearization: Version 2

This version is much simpler and cleaner than the previous one (yay!) and uses the so-called *modulus switching* technique. Recall that if we try to naively mask $s^2$ in the reliniarization key, then there is a large blow-up in the noise because of the $c_2$ multiplication. We want to avoid this to get a correct decryption.

In this version we mask $s^2$ modulo a a different modulus, $p\cdot q$, with a much larger $p\gg q$, as shown below.

\begin{eqnarray}
rlk = ([-(a' \cdot s + e') + p\cdot s^2]_{p\cdot q}, a'),
\end{eqnarray}

for a uniform $a'$ in $R_{p\cdot q}$ and $e'$ drawn according to an error distribution $\chi'$ over $R$.
Remember that our goal is to produce an approximation of $[c_2\cdot s^2]_q$. The idea is that when we scale from $p\cdot q$ back to $q$, the noise gets divided by the large integer $p$, significantly reducing its size.

>:exclamation: In a safe implementation the distribution $\chi'$ should be distinct from $\chi$ and its parameters should be carefully chosen for security reasons. Since security is not our main goal in this blog post, you can check the paper for further details.

def evaluate_keygen_v2(sk, size, modulus, poly_mod, extra_modulus, std2):
    """Generate a relinearization key using version 2.
        Args:
            sk: secret key
            size: size of the polynomials.
            modulus: coefficient modulus.
            poly_mod: polynomial modulus.
            extra_modulus: the "p" modulus for modulus switching.
            st2: standard deviation for the error distribution.
        Returns:
            rlk0, rlk1: relinearization key.
        """
    new_modulus = modulus * extra_modulus
    a = gen_uniform_poly(size, new_modulus)
    e = gen_normal_poly(size, 0, std2)
    secret_part = extra_modulus * poly.polymul(sk, sk)

    b = np.int64(polyadd_wm(
        polymul_wm(-a, sk, poly_mod),
        polyadd_wm(-e, secret_part, poly_mod), poly_mod)) % new_modulus
    return b, a

The linear approximation of $[c_2 \cdot s^2]_q$ can be computed from the pair:

$$(c_{20}, c_{21}) = \Big(\Big[\Big\lfloor\frac{c_2 \cdot rlk[0]}{p}\Big\rceil\Big]_q, \Big[\Big\lfloor\frac{c_2 \cdot rlk[1]}{p}\Big\rceil\Big]_q\Big).$$

Indeed, $[c_{20} + c_{21} \cdot s]_q = [c_2 \cdot s^2]_q + e_{\text{relin_v2}},$ for a "small" error, $e_{\text{relin_v2}} \in R_q$. Skipping some details, this holds true because of the following simple computation:

\begin{eqnarray}
\frac{c_2 \cdot rlk[0]}{p} + \frac{c_2 \cdot rlk[1]}{p} \cdot s &=& \frac{c_2\cdot [-(a'\cdot s+e') + p\cdot s^2]_{p\cdot q}+c_2 \cdot a' \cdot s}{p}\\
&=& c_2\cdot s^2 +\frac{-c_2\cdot e'}{p} + q \cdot K,
\end{eqnarray}

where $K \in R$ such that $[-(a'\cdot s+e') + p\cdot s^2]_{pq} = -(a'\cdot s+e') + p\cdot s^2 + pq\cdot K$.
We're cheating a bit here, since the pair involves the *roundings of the terms to their nearest integers*. Still, we're not far from the truth, since for any real number $a$, $\lfloor a \rceil$ differs from $a$ by a small quantity $\varepsilon \in [-\frac{1}{2},\frac{1}{2}]$. (we can also extend this coefficient-wise to polynomials).
>:bulb: We get a "small" **relinearization noise**, $e_{\text{relin_v2}} \approx (c_2\cdot e')/p$, for large $p:$
$$\|e_{\text{relin_v2}}\| \leq \frac{q \cdot B' \cdot n}{p}+\frac{n+1}{2}.$$

Next, we provide the easy code implementation for multiplying ciphertexts using this version.

def mul_cipher_v2(ct1, ct2, q, t, p, poly_mod, rlk0, rlk1):
    """Multiply two ciphertexts.
    Args:
        ct1: first ciphertext.
        ct2: second ciphertext.
        q: ciphertext modulus.
        t: plaintext modulus.
        p: modulus-swithcing modulus.
        poly_mod: polynomial modulus.
        rlk0, rlk1: output of the EvaluateKeygen_v2 function.
    Returns:
        Tuple representing a ciphertext.
    """
    c_0, c_1, c_2 = multiplication_coeffs(ct1, ct2, q, t, poly_mod)

    c_20 = np.int64(np.round(polymul_wm(c_2, rlk0, poly_mod) / p)) % q
    c_21 = np.int64(np.round(polymul_wm(c_2, rlk1, poly_mod) / p)) % q

    new_c0 = np.int64(polyadd_wm(c_0, c_20, poly_mod)) % q
    new_c1 = np.int64(polyadd_wm(c_1, c_21, poly_mod)) % q
    return (new_c0, new_c1)

## Version 1 vs. Version 2 :boxing_glove:

Recall that we can derive a fresh standard ciphertext that decrypts to $[m_1m_2]_t$ as $c_{mul} =(c_0+c_{20}, c_1+c_{21})$, since

$$c_0 + c_{20} + s\cdot (c_1 + c_{21}) = c_0 + c_1 \cdot s + c_2 \cdot s^2 + e_{\text{relin}} = \Delta \cdot [m_1m_2]_t + v_{mult},$$

where $v_{mult} = u_3 + e_{\text{relin}}$ and $e_{\text{relin}} \in \{e_{\text{relin_v1}}, e_{\text{relin_v2}}\}$.

We need to make sure that $c_{mul}$ decrypts *correctly* to $[m_1m_2]_t$. For this, it suffices to choose the parameters such that $\|u_3\| + \|e_{\text{relin}}\| \leq \Delta/2.$

Now that we have **two** versions of relinearization, which help us in deriving $c_{mul}$, we may wonder which one we can use:

| Relinearization | Size of $rlk$ (in bits) | Bound of $e_{\text{relin}}$|
| ----------------- |:--------------|------------|
| **Version 1** | $2(\ell+1)\cdot n \cdot \log q$ |$(\ell+1)\cdot B \cdot T \cdot n/2$ |
| **Version 2** | $2n \cdot \log pq$ |$\frac{q \cdot B' \cdot n}{p}+\frac{n+1}{2}$ |

+ **size of $rlk$:** **Version 1** gives a relinearization key as $\ell+1$ pairs of polynomials in $R_q,$ whereas **Version 2** gives just one such pair. Recall that $\ell=\lfloor \log_T{q}\rfloor$ and see that this decreases as long as the base $T$ increases.

+ **bound of $e_{\text{relin}}$:** The upper bounds of $e_{\text{relin}}$ for both versions are according to [[FV12], Lem. 3](https://eprint.iacr.org/2012/144.pdf). We consider $B$ as a bound taken so that the error distribution $\chi$ takes values in $[-B,B]$ with high probability. We similarly define $B'$ for the case of the error distribution $\chi'$, used in **Version 2**. Notice that for **Version 1**, a larger $T$ leads to more noise (but smaller $rlk$), whereas in **Version 2**, a larger $p$ leads to smaller noise (but larger $rlk$). For choosing the parameters in safe implementation, we refer the reader to [[FV12] Sec. Realinearisation Version 2.](https://eprint.iacr.org/2012/144.pdf)

## Setting the parameters

We set the parameters for our toy implementation just to make sure it always correctly decrypts at least one ciphertext multiplication. For that, we made sure that $\|u_3\| + \|e_{\textsf{relin}}\|< \Delta /2$. In practice, for the current choice it seems that decryption always works for $3$ ciphertext multiplications when using V2 relinearization, for example. This is due to the fact that the theoretical bounds are worst-case bounds. For the same parameters we can make hundreds of addition (in practice it seems that decryption works even for $1000$ additions :open_mouth:). Ciphertext addition is almost for free in terms of noise growth! :boom: We invite you to play around with the parameters and the bounds and try to see how many multiplications you can get (as they are the costly operations).

## Let's play! :tada:

Now we can multiply ciphertexts, as we have implemented two versions of this: $\texttt{mul_cipher_v1}$ and $\texttt{mul_cipher_v2}$, using relinearization. We can further add ciphertexts by using $\texttt{add_cipher}$. So yay! we can finally perform computations on encrypted data.

**Bonus:** if you're curious, you can try computing more complex (polynomial) operations on encrypted data, such as *multiplying three ciphertexts*? Here we only wanted to show how to perform one multiplication. For more levels of multiplications, you should set the parameters as in [[FV12, Thm 1]](https://eprint.iacr.org/2012/144.pdf) so that you decrypt correctly :wink:.

**Bonus2:** you can also perform *plain operations*, such as adding or multiplying plaintexts to ciphertexts, by using $\texttt{add_plain}$ and $\texttt{mul_plain},$ (with a *reduced noise growth*) both from [here](https://github.com/Bitdefender-Crypto-Team/he-scheme/blob/main/rlwe_he_scheme_updated.py). For further details on how these work, you should check [this](https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/#buildanhomomorphicencryptionscheme). :nerd_face:

So what are you waiting for? Go check this out!

import rlwe_he_scheme_updated as rlwe_updated
import numpy as np

if __name__ == '__main__':
    # Scheme's parameters
    # polynomial modulus degree
    n = 2 ** 2
    # ciphertext modulus
    q = 2 ** 14
    # plaintext modulus
    t = 2
    # base for relin_v1
    T = int(np.sqrt(q)) 
    #modulusswitching modulus
    p = q ** 3

    # polynomial modulus
    poly_mod = np.array([1] + [0] * (n - 1) + [1])
    
    #standard deviation for the error in the encryption
    std1 = 1
    #standard deviation for the error in the evaluateKeyGen_v2
    std2 = 1

    # Keygen
    pk, sk = rlwe_updated.keygen(n, q, poly_mod, std1)

    #EvaluateKeygen_version1
    rlk0_v1, rlk1_v1 = rlwe_updated.evaluate_keygen_v1(sk, n, q, T, poly_mod, std1)

    #EvaluateKeygen_version2
    rlk0_v2, rlk1_v2 = rlwe_updated.evaluate_keygen_v2(sk, n, q, poly_mod, p, std2)
 
    # Encryption
    pt1, pt2 = [1, 0, 1, 1], [1, 1, 0, 1]
    cst1, cst2 = [0, 1, 1, 0], [0, 1, 0, 0]

    ct1 = rlwe_updated.encrypt(pk, n, q, t, poly_mod, pt1, std1)
    ct2 = rlwe_updated.encrypt(pk, n, q, t, poly_mod, pt2, std1)

    print("[+] Ciphertext ct1({}):".format(pt1))
    print("")
    print("\t ct1_0:", ct1[0])
    print("\t ct1_1:", ct1[1])
    print("")
    print("[+] Ciphertext ct2({}):".format(pt2))
    print("")
    print("\t ct1_0:", ct2[0])
    print("\t ct1_1:", ct2[1])
    print("")

    # Evaluation
    ct3 = rlwe_updated.add_plain(ct1, cst1, q, t, poly_mod)
    ct4 = rlwe_updated.mul_plain(ct2, cst2, q, t, poly_mod)
    #ct5 = (ct1 + cst1) + (cst2 * ct2)
    ct5 = rlwe_updated.add_cipher(ct3, ct4, q, poly_mod)
    # ct6 = ct1 * ct2
    ct6 = rlwe_updated.mul_cipher_v1(ct1, ct2, q, t, T, poly_mod, rlk0_v1, rlk1_v1)
    ct7 = rlwe_updated.mul_cipher_v2(ct1, ct2, q, t, p, poly_mod, rlk0_v2, rlk1_v2)
    # Decryption
    decrypted_ct3 = rlwe_updated.decrypt(sk, q, t, poly_mod, ct3)
    decrypted_ct4 = rlwe_updated.decrypt(sk, q, t, poly_mod, ct4)
    decrypted_ct5 = rlwe_updated.decrypt(sk, q, t, poly_mod, ct5)
    decrypted_ct6 = rlwe_updated.decrypt(sk, q, t, poly_mod, ct6)
    decrypted_ct7 = rlwe_updated.decrypt(sk, q, t, poly_mod, ct7)
    
    print("[+] Decrypted ct3=(ct1 + {}): {}".format(cst1, decrypted_ct3))
    print("[+] Decrypted ct4=(ct2 * {}): {}".format(cst2, decrypted_ct4))
    print("[+] Decrypted ct5=(ct1 + {} + {} * ct2): {}".format(cst1, cst2, decrypted_ct5))
    print("[+] pt1 + {} + {} * pt2): {}".format(cst1, cst2, rlwe_updated.polyadd(
                                                rlwe_updated.polyadd(pt1, cst1, t, poly_mod),
                                                rlwe_updated.polymul(cst2, pt2, t, poly_mod),
                                                t, poly_mod)))
    print("[+] Decrypted ct6=(ct1 * ct2): {}".format(decrypted_ct6))
    print("[+] Decrypted ct7=(ct1 * ct2): {}".format(decrypted_ct7))
    print("[+] pt1 * pt2: {}".format(rlwe_updated.polymul(pt1, pt2, t, poly_mod)))