< Back Home

The BGV fully homomorphic encryption scheme

This is a sister blogpost to the previous one about a similar scheme (BFV) and it's part of the series that covers fully homomorphic encryption techniques and applications.

Introduction

\gdef\can #1{\|#1\|^{\text{can}}}

In this blogpost we will focus on the encryption, decryption, relinearization and the noise analysis of the Brakerski, Gentry, Vaikuntanathan (BGV) fully homomorphic encryption scheme. A Python implementation of the aforementioned will be provided.

DISCLAIMER: This toy implementation is not meant to be secure or optimized for efficiency. It's for educational purposes only, and for us to better understand the inner workings.

What to expect from this blogpost?

  1. We briefly describe the motivations of fully homomorphic encryption.
  2. We present the BGV scheme.
  3. We offer a Python implementation for the BGV scheme, for educational purposes.

Now, let's make a short, informal, tour before starting. Fully homomorphic encryption (FHE) allows us to perform computation on encrypted data. While there are a few cryptographic schemes to achieve this, in this blogpost we explore the BGV scheme.

Firstly, this scheme allows us to encrypt messages into ciphertexts. Intuitively, a message is hidden in a ciphertext if there is no way to get to retrieve the original message from its encryption. To an attacker that sees a ciphertext, that ciphertext should look like "random garbage". In order to achieve this we hide the message by "masking" it with some noise. We say it's hard for an attacker to retrieve a message from its ciphertext if doing so is at least as hard as solving a computationally unfeasable problem. The problem the security of the BGV scheme is based on is called the Ring Learning with Errors problem.

Secondly, the scheme allows us to perform arithmetic operations (additions, multiplications) using noisy ciphertexts. However, we will encounter some problems along the way, such as the noise increasing after computations, or the size of the resulting ciphertext increasing. We'll see how to handle these using modulus switching (for the former) and relinearization (for the latter).

This post will get a bit mathematical, so before starting we introduce some notation. Any other notation will be defined when introduced.

Notations:

  • m,m,mm, m', m^* - messages.
  • c,c,cc, c', c^* - ciphertexts. If ciphertexts have more components, we denote the components with indices: c=(c0,c1)c = (c_0, c_1)
  • λ\lambda - Security parameter.
  • Zq\mathbb Z_q - the set of integers from (q/2,q/2](-q / 2, q / 2]
  • RR - Ring.
    • Ex: Z\mathbb Z - the integers.
    • Ex: Z[X]/(Xn+1)\mathbb Z[X] / (X^n + 1) - the quotient polynomial ring with integer coefficients: .
  • RqR_q - Ring modulo the ideal generated by qq.
    • Ex: Zq\mathbb Z_q - the integers mod qq.
    • Ex: Zq[X]/(Xn+1)\mathbb Z_q[X]/ (X^n + 1) - the quotient polynomial ring with coefficients being integers in (q/2,q/2](-q / 2, q / 2].
  • [a]q[a]_q - amodqa \bmod q, coefficients centered in (q/2,q/2](-q / 2, q / 2]. When applying []q[\cdot ]_q to a polynomial we mean to apply it to all its coefficients individually. When applying [][\cdot] to a vector of elements, we mean to apply it to each element individually. So [(a,b)]q=([a]q,[b]q)[(a, b)]_q = ([a]_q, [b]_q). We give the similar treatment to reduction modq\bmod q operation
  • χ=χ(λ)\chi = \chi(\lambda) - Noise distribution, parametrized by λ\lambda (usually Gaussian).
  • For simplicity, when we say we sample a polynomial from some distribution (or a polynomial comes from some distribution) we mean that its coefficients are sampled independently from that distribution.
  • eχe \leftarrow \chi - An element ee sampled from the distribution χ\chi
  • aRSa \xleftarrow R S - An element sampled uniformly from a set SS
    • Ex: aRRqa \xleftarrow R R_q An element aa sampled uniformly from the ring RqR_q
  • aba \cdot b denotes the multiplication of 2 elements from the ring RqR_q
  • tata denotes the multiplication of coefficients of aRqa \in R_q by some scalar tt.

Fully Homomorphic Encryption (FHE)

Before defining fully homomorphic encryption, let's look at some applications of it to get a better intuition:

1. Outsourcing storage and computations

  • A company wants to use a cloud provider to store data and do computational heavy lifting.
  • Task: The company wants to use the information (for example: to do machine learning, extract statistical properties) without locally retrieving it (defeating the purpose of using the cloud company services). Furthermore, the company doesn't want the cloud provider to see the sensitive data.
  • Solution: Using homomorphic encryption, the company can encrypt and send the data to the cloud provider and then the cloud provider can process the information (as requested by the company) in the encrypted form, without learning anything about the data.
  • Ex: finance, medical apps, consumer privacy in ads.

2. Private queries

  • A client wants to retrieve a query against a large database held by a provider.
  • Task: The client wants to retrieve a query without the database provider learning the query.
  • Solution: Using homomorphic encryption the client can encrypt the index of the record and then the database can use this encrypted index to fetch (the comparison operation can be done using FHE) and return the encrypted result to the client. Finally, the client can decrypt the record.

3. Private set intersection

  • A client and a server each has a set of elements. The client wants to know which elements from its set are in the server's set.
  • Task: The client wants to find out the intersection of its elements and the server's, without the server learning anything about the client's elements and vice versa.
  • Solution (Very simplified): They translate the comparison operation into a subtraction (x=yxy=0x = y \Rightarrow x - y = 0). The client encrypts its elements and sends them to the server. Then, the server evalutes these subtractions homomorphically. Because the result of the subtraction is an encrypted result, the server learns nothing. Then the server sends the comparison results back and the client decrypts the results. We have a longer, more in-depth blogpost about it here. Happy reading!
  • Examples: Client: user contacts, Server: whatsapp contacts; Client: own passwords, Server: database with breached passwords.

Intuition

  • A user has an arithmetic function ff and some inputs (m1,...mn)(m_1, ... m_n).
  • He wants to compute m=f(m1,...mn)m^* = f(m_1, ... m_n) but instead of computing it directly, he wants to encrypt (m1,...mn)(c1,...cn)(m_1, ... m_n) \to (c_1, ... c_n) and do the computation on the ciphertext, obtaining a result which eventually decrypts to m=f(m1,...mn)m^* =f(m_1, ... m_n).
  • It's helpful to view the functions as tree of operations. For example (taken from the BFV blogpost): f(m1,m2,m3,m4)=(m1×m2+m3)×m4f(m_1,m_2,m_3,m_4)= (m_1 \times m_2 + m_3) \times m_4

Homomorphic Encryption -- Definition
Let (KeyGen,Enc,Dec,Eval)(\text{KeyGen}, \text{Enc}, \text{Dec}, \text{Eval}) be a tuple of procedures.
Let fFf \in \mathcal F be a function in a family of functions. This function can also be written as a circuit from a family of circuits CCC \in \mathcal C.

  • (sk,pk)KeyGen(1λ,1d)(sk, pk) \gets \text{KeyGen}(1^\lambda, 1^d) - key generation, λ\lambda is a security parameter, dd is a functionality parameter (degree of the polynomial or depth of the circtuit).
  • ciEnc(pk,mi)c_i \gets \text{Enc}(pk, m_i) - Encryption of a message mim_i -- known as fresh ciphertexts.
  • c=Eval(pk,f,c1,...cn)c^* = \text{Eval}(pk, f, c_1, ... c_n) - Evaluate the function ff on the ciphertexts -- known as evaluated ciphertexts.

Correctness
We require the (FHE) scheme to correctly decrypt both fresh and evaluated ciphertexts: Dec(sk,c)=m=f(m1,...,mn)\text{Dec}(sk, c^*) = m^* = f(m_1, ..., m_n)

In the image above, the user with the laptop is interested evaluating a certain circuit on its data mm. Therefore it sends its data, encrypted, to the cloud so that the cloud computes the circuit. By correctness, the user indeed gets the circuit applied on its data mm.

Circuits?
The two important operations we care about are addition and multiplication, because with them we can construct any arithmetic operation! Homomorphic encryption schemes started out by encrypting bits, so the equivalent operations for additon and multiplication on bits, xor and and are used.

=+mod2=×mod2\oplus = + \bmod 2 \\ \otimes = \times \bmod 2

To convey the fact that a circuit supports both xor and and usually a nand gate is used, because nand gates are composed by 1 multiplication and 1 addition and they are logically complete (you can build any circuit with them). nand(a,b)=a×b+1mod2\text{nand}(a, b) = a \times b + 1 \bmod 2

By extending to multiple bits, with the gates we discussed above you can represent any computation using boolean circuits.

HE can be classified based on the type of functions ff that it supports:

  • Partially homomorphic encryption
    Given Enc(m1)\text{Enc}(m_1), and Enc(m2)\text{Enc}(m_2) you can do limited operations (either additions or multiplications)
  • Somewhat (leveled) homomorphic encryption
    Given Enc(m1),...,Enc(mn)\text{Enc}(m_1), ..., \text{Enc}(m_n) you can compute Enc(f(m1,...mn))\text{Enc}(f(m_1, ... m_n)) where ff is a polynomial of a limited degree. One can do limited number of multiplications (Circuits of a maximum depth).
  • Fully homomorphic encryption
    One can do unlimited multiplications and additions.

The community put a lot of effort into the analysing FHE schemes: finding good parameters, finding software and hardware optimizations, coming up with possible attacks and adjusting the schemes against them. An interesting read is the homomorphic encryption standard, which compiles good practices and techniques for developing and using existing schemes.

Ring Learning With Errors (RLWE)

In this section we'll focus on briefly introducing the Ring learning with errors (RLWE) problem. The problem is very complex and we'll only attempt to cover the basic blocks for building an intuition. For the interested reader more details can be found in this paper.

Quick recap on working with polynomials

This section is taken from the BFV blogpost, but we'll repeat it here to save you a click. For this subsection we denote with Z/qZ={0,...,q1}\mathbb Z / q\mathbb Z = \{0, ... , q - 1\}.

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 ff. This "modulo ff" 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 ff. When we do these additions and multiplications modf\bmod f, we sometimes say in a fancy way that we are working in the ring Z[x]/(f)\mathbb{Z}[x]/(f) of reduced polynomials.

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

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

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

Here nothing special happened. Let's multiply them:

a(x)b(x)modf=(x3+x2+7)(x2+11x) mod f=x5+11x4+x4+11x3+7x2+77x mod f=x111+11x3+7x2+77x mod f=11x3+7x2+76x12 mod f.\begin{aligned} 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{aligned}

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

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

[a(x)+b(x)]q=x3+x2+2+x2+x=x3+2x2+x+2[a(x) + b(x)]_q = x^3 + x^2 +2+ x^2 + x = x^3 + 2x^2 + x+2

and

[a(x)b(x)]q=(x3+x2+2)(x2+x)=x5+x4+x4+x3+2x2+2x=x11+x3+2x2+2x=x3+2x2+x+3\begin{aligned} [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{aligned}

To give a powerful visual intuition of polynomials in quotient rings, consider the following polynomial1+4x+2x3Z/5Z[x]/(x4+1)1 + 4x + 2x^3 \in \mathbb Z/5\mathbb Z[x] / (x^4+1) and its visual representation. For this grade 3 polynomial we have four pentagons, for each coefficient. Each pentagon represents Z/5Z\mathbb Z/ 5\mathbb Z. The value of the coefficient is colored with green:

poly

The security of the BGV scheme

Like we said in the introduction, our ciphertexts will be masked with some noise to look as random as possible in order to hide any information an attacker may extract about the message.

In fact it can be proven that the BGV scheme is secure as long as nobody can solve the Ring Learning With Errors (RLWE) problem described below. The parameters of the scheme must be chosen such that there are no known algorithms to solve the underlying RLWE problem in feasable time.

Formally, the idea of "ciphertexts looking like garbage" is called ciphertext indistinguishability. This concept can be formulated using a game between a challenger and an adversary:

  • The challenger receives two messages m0,m1m_0, m_1 from the adversary. Then, the challenger encrypts them into c0,c1c_0, c_1.
  • Then, the challenger secretly flips a bit b{0,1}b\in \{0, 1\} and sends the ciphertext cbc_b to the adversary.
  • The adversary must guess the bit bb. After running an efficient algorithm, it outputs a bit bb'. It wins if b=bb' = b.

sec_game

If there exists at least one adversary that can win the game with a probability significantly larger than 1/2 (a coinflip) using a computationally efficient algorithm (something that can run in our universe's lifetime), the challenger's algorithm is considered insecure. When we prove the security of a scheme, we actually show that if an adversary had such an algorithm that can win the security game, he can take that algorithm and use it to solve a problem that is considered computationally hard.

We will now describe the RLWE problem.

Consider the quotient polynomial ring Rq=Zq[X]/(Xn+1)R_q = \mathbb Z_q[X]/ (X^n + 1). This ring has polynomials with degree at most nn and integer coefficients in (q/2,q/2](-q / 2, q / 2].

The RLWE problem - decision
The problem asks to distinguish between the following two distributions:

  • (ai,bi)(a_i, b_i) with aiRRqa_i \xleftarrow R R_q, biRRqb_i \xleftarrow R R_q.
  • (ai,bi)(a_i, b_i) with aiRRqa_i \xleftarrow R R_q, eiχe_i \leftarrow \chi, and bi=ais+eib_i = a_i \cdot s + e_i for some "small" secret sRqs \in R_q sampled before.

The RLWE problem also has a search version, where given pairs (ai,bi)(a_i, b_i), bi=ais+eib_i = a_i \cdot s + e_i you need to find ss. In practice, the decision version is more widely used when proving the security of different schemes.

More details about the RLWE problem can be found in this paper. In essence, by adding some small noise eie_i, from a Gaussian distribution, we make our secret ss unrecoverable even if we have access to many RLWE samples.

The original BGV paper presents the algorithms (encryption, decryption, etc) of a HE scheme based on a more general problem, the General Learning with Errors (GLWE) problem. For simplicity, we work with the RLWE case in this blogpost.

The BGV encryption scheme

Generate the following parameters

  • nn - degree of Xn+1X^n + 1. nn is chosen as a power of 2.
  • qq - ciphertext modulus.
  • tt - plainext modulus, tqt \ll q.
  • χ\chi - the noise distribution, a discrete Gaussian.

We consider Rq=Zq[X]/(Xn+1)R_q = \mathbb Z_q[X] / (X^n + 1). This ring has polynomials with degree at most nn and integer coefficients in (q/2,q/2](-q / 2, q / 2].

Note:

  • All polynomial operations are considered modq\bmod q unless otherwise specified, to ease notation.
  • When we talk about "small" polynomials, we intuitively think about them having small coefficients.
  • Polynomials that come from the noise distribution will be colored with green (ex: e\textcolor{darkgreen}{e}) and the ones that will come from the secret key distribution will be colored with red (Ex: s,u\red{s}, \red{u}).

We will have one secret key sksk, a public key with two components pk=(pk0,pk1)pk = (pk_0, pk_1), a ciphertext with 2 components c=(c0,c1)c = (c_0, c_1) The messsage will come from the ring RtR_t.

SecretKeyGen(params) -> sk

  • Draw s\red{s} from a secret key distribution which outputs "small" elements with overwhelming probability. In practice s{1,0,1}n\red{s} \in \{-1, 0, 1\}^n, with the probability of sampling 00 specified as a parameter and the probabilities of sampling 1-1 or 11 being equal.
  • Return the secret key sk=ssk = \red{s}.

PubKeyGen(sk, params) -> (pk0, pk1)

  • Draw a random element aRRqa \xleftarrow R R_q and the noise eχ\textcolor{darkgreen}{e} \leftarrow \chi.
  • Return the public key: pk=(pk0,pk1)=(as+te,a)RLWE instance-likepk = (pk_0, pk_1) = \underbrace{(a \cdot \red{s} + t\textcolor{darkgreen}{e}, -a)}_{\text{RLWE instance-like}}.

Notice that the public key looks like a RLWE sample, but the error ee is multiplied by the plaintext modulus tt.

Encrypt(m, pk, params) -> (c0, c1)

  • Draw the noise e0,e1χ\textcolor{darkgreen}{e_0}, \textcolor{darkgreen}{e_1} \leftarrow \chi and a "small" polynomial u{1,0,1}n\red{u} \in \{-1, 0, 1\}^n in the same way as the secret.
  • Compute c0=pk0u+te0+mc_0 = pk_0 \cdot \red{u} + t\textcolor{darkgreen}{e_0} + m
  • Compute c1=pk1u+te1c_1 = pk_1 \cdot \red{u} + t\textcolor{darkgreen}{e_1}
  • Return c=(c0,c1)c = (c_0, c_1).

The ciphertext components (c0,c1)(c_0, c_1) are elements in Rq=Zq[X]/(Xn+1)R_q = \mathbb Z_q[X]/(X^n + 1).

Decrypt(c, sk, params)

  • Compute m=c0+c1smodqmodtm = c_0 + c_1 \cdot \red{s} \bmod q \bmod t
  • Return mm.
Correctness (Click for math)

Let's unroll the equations to check the correctness. All operation are modq\bmod q to ease notation, unless we specify otherwise.

The public key is:

pk0=as+tepk1=a\begin{aligned} pk_0 &= a \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e} \\ pk_1 &= -a \end{aligned}

The public key hides the secret ss as a RLWE sample.

The encryption equations unrolled are:

c0=pk0u+te0+m=(as+te)u+te0+m=asu+t(eu)+te0+mc1=pk1u+te1=au+te1\begin{aligned} c_0 = pk_0 \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e}_0 + m \\ &= (a \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e}) \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_0} + m \\ &= a \cdot \textcolor{red}{s} \cdot \textcolor{red}{u} + t(\textcolor{darkgreen}{e} \cdot \textcolor{red}{u}) + t\textcolor{darkgreen}{e_0} + m \\ c_1 &= pk_1 \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_1} \\ &= -a \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_1} \\ \end{aligned}

The decryption equation unrolled is:

c0+c1s=asu+t(eu)+te0+m+(au+te1)smodq=asu+t(eu)+te0+maus+te1s=te1s+t(eu)+te0+m=t(eu+e0+e1s)error+m\begin{aligned} c_0 + c_1 \cdot \textcolor{red}{s} &= a \cdot \textcolor{red}{s} \cdot \textcolor{red}{u} + t(\textcolor{darkgreen}{e} \cdot \textcolor{red}{u}) + t\textcolor{darkgreen}{e_0} + m + (-a \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_1}) \cdot \textcolor{red}{s} \bmod q \\ &= \cancel{a \cdot \textcolor{red}{s} \cdot \textcolor{red}{u}} + t(\textcolor{darkgreen}{e} \cdot \textcolor{red}{u}) + t\textcolor{darkgreen}{e_0} + m \cancel{-a \cdot \textcolor{red}{u} \cdot \textcolor{red}{s}} + t\textcolor{darkgreen}{e_1} \cdot \textcolor{red}{s} \\ &= t\textcolor{darkgreen}{e_1} \cdot \textcolor{red}{s} + t(\textcolor{darkgreen}{e} \cdot \textcolor{red}{u}) + t\textcolor{darkgreen}{e_0} + m \\ &= \underbrace{t(\textcolor{darkgreen}{e} \cdot \textcolor{red}{u} + \textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e_1} \cdot \textcolor{red}{s})}_{\text{error}} + m \end{aligned}

The decryption is correct as long as the error we add to mm does not wrap the coefficients of mm arond the modulus qq. The noise analysis will be offered later, in its own section.

Now, we reduce the above modt\bmod t and we get:

c0+c1s=mmodqmodtc_0+c_1 \cdot \textcolor{red}{s} = m \bmod q \bmod t

FHE Operations

Here we will explore the homomorphic properties of the scheme. We refer to the two input message and ciphertext pairs with (m,c),(m,c)(m, c), (m', c') and to the resulting message-ciphertext pair with (m,c)(m^*, c^*).

The goal is to find two functions, add,mul\text{add}, \text{mul}, that work on ciphertexts, for addition and multiplication, such that:

  • when m=m+mm^* = m + m' we have c=add(c,c)c^* = \text{add}(c, c') and Dec(c)=m\text{Dec}(c^*) = m^*
  • when m=mmm^* = m \cdot m' we have c=mul(c,c)c^* = \text{mul}(c, c') and Dec(c)=m\text{Dec}(c^*) = m^*

Recall that cc and cc' encrypt mm and mm' i.e.:

c0=pk0u+te0+mc1=pk1u+te1c0=pk0u+te0+mc1=pk1u+te1\begin{aligned} c_0 &= pk_0 \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_0} + m \\ c_1 &= pk_1 \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_1} \\ \\ c'_0 &= pk_0 \cdot \textcolor{red}{u'} + t\textcolor{darkgreen}{e'_0} + m \\ c'_1 &= pk_1 \cdot \textcolor{red}{u'} + t\textcolor{darkgreen}{e'_1} \\ \end{aligned}

FHE Addition

The image on the left performs the addition before the encryption, with the messages in clear. This is not what we want. The image on the right is the desirable outcome, where we encrypt the messages, then perform addition on the encrypted messages.

fhe_add

We define add: add(c, c') -> c*

  • c0=c0+c0c^*_0 = c_0 + c'_0
  • c1=c1+c1c^*_1 = c_1 + c'_1
  • return c=(c0,c1)c^* = (c^*_0, c^*_1)
Correctness (click for math)
c0=c0+c0=pk0u+te0+m+pk0u+te0+m=pk0(u+u)+t(e0+e0)+m+m=(as+te)(u+u)+t(e0+e0)+m+m=(as)(u+u)+te(u+u)+t(e0+e0)+m+mc1=c1+c1=pk1u+te1+pk1u+te1=pk1(u+u)+t(e1+e1)=a(u+u)+t(e1+e1)\begin{aligned} c^*_0 &= c_0 + c'_0 \\ &= pk_0 \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_0} + m + pk_0 \cdot \textcolor{red}{u'} + t\textcolor{darkgreen}{e'_0} + m' \\ &= pk_0 \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e'_0}) + m + m' \\ &= (a \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e}) \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e'_0}) + m + m' \\ &= (a \cdot \textcolor{red}{s} ) \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + t\textcolor{darkgreen}{e} \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e'_0}) + m + m' \\ \\ c^*_1 &= c_1 + c'_1 \\ &= pk_1 \cdot \textcolor{red}{u} + t\textcolor{darkgreen}{e_1} + pk_1 \cdot \textcolor{red}{u'} + t\textcolor{darkgreen}{e'_1} \\ &= pk_1(\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_1} + \textcolor{darkgreen}{e'_1}) \\ &= -a(\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_1} + \textcolor{darkgreen}{e'_1}) \end{aligned}

And by using Decrypt(c*, sk, params) we have

c0+c1s=(as)(u+u)+te(u+u)+t(e0+e0)+m+mc0++(a(u+u)+t(e1+e1))c1s=(as)(u+u)+te(u+u)+t(e0+e0)+m+m(as)(u+u)+t(e1+e1)s=te(u+u)+t(e0+e0)+t(e1+e1)s+m+m=t(e(u+u)+e0+e0+(e1+e1)s)error+m+m\begin{aligned} c^*_0 + c^*_1 \cdot \textcolor{red}{s} &= \overbrace{(a \cdot \textcolor{red}{s} ) \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + \textcolor{darkgreen}{te} \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e'_0}) + m + m'}^{c^*_0} + \\ &+ \overbrace{(-a(\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_1} + \textcolor{darkgreen}{e'_1}))}^{c^*_1} \cdot \textcolor{red}{s} \\ &= \cancel{(a \cdot \textcolor{red}{s} ) \cdot (\textcolor{red}{u} + \textcolor{red}{u'})} + t\textcolor{darkgreen}{e} \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e'_0}) + m + m' - \\ & \cancel{-(a \cdot \textcolor{red}{s}) \cdot (\textcolor{red}{u} + \textcolor{red}{u'})} + t(\textcolor{darkgreen}{e_1} + \textcolor{darkgreen}{e'_1}) \cdot \textcolor{red}{s} \\ &= t\textcolor{darkgreen}{e} \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + t(\textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e'_0}) + t(\textcolor{darkgreen}{e_1} + \textcolor{darkgreen}{e'_1}) \cdot \textcolor{red}{s} + m + m' \\ &= \underbrace{t(\textcolor{darkgreen}{e} \cdot (\textcolor{red}{u} + \textcolor{red}{u'}) + \textcolor{darkgreen}{e_0} + \textcolor{darkgreen}{e'_0} + (\textcolor{darkgreen}{e_1} + \textcolor{darkgreen}{e'_1}) \cdot \textcolor{red}{s} )}_{\text{error}} + m + m' \end{aligned}

Again, by reducing everything modt\bmod t we have

c0+c1s=m=m+mmodtc^*_0 + c^*_1 \cdot \red{s} = m^* = m + m' \bmod t

with the same remark that for the decryption to be correct the error that we add to mm^* must not wrap mm^* around qq.


The resulting ciphertext cc^* is not fresh anymore (just encrypted), and has a bigger noise than any of the previous ciphertexts that were inputs in the addition operation. In general, using non-fresh ciphertexts cc^* to perform future operations will carry over the noise from all the previous operations.

We'll analyse how the noise grows in a dedicated section at the end.

FHE Multiplication

As in the addition case, we want the multiplication to be done on the encrypted messages.

fhe_mul

Before describing how we multiply two ciphertexts we need to reinterpret the decryption equation: c0+c1smmodtc_0 + c_1 \cdot \red{s} \equiv m \bmod t as a linear equation: y=ax+by = ax + b in s\red{s}.

If we look at adding two such linear equations in ss we obtain another linear equation in s\red{s}: c0+c1s+c0+c1s=(c0+c0)c0+(c1+c1)c1sc_0 + c_1 \cdot \red{s} + c'_0 + c'_1 \cdot \red{s} = \underbrace{(c_0 + c_0')}_{c^*_0} + \underbrace{(c_1 + c'_1)}_{c^*_1} \cdot \red{s}

However, when multiplying two linear equations in s\red{s} we get a quadratic equation (ax2+bx+cax^2 + bx + c) in s\red{s}:

(c0+c1s)=mmodt(c0+c1s)=mmodt=c1c1s2+(c0c1+c1c0)s+c0c0\begin{aligned} \underbrace{(c_0 + c_1 \cdot \textcolor{red}{s} )}_{= m \bmod t} \cdot \underbrace{(c'_0 + c'_1 \cdot \textcolor{red}{s} )}_{= m' \bmod t} &= c_1 \cdot c'_1 \cdot \textcolor{red}{s}^2 + (c_0 \cdot c'_1 + c_1 \cdot c'_0) \cdot \textcolor{red}{s} +c_0 \cdot c'_0 \end{aligned}

We can define mul in the following way: mul(c, c') -> c*

  • c0=c0c0c^*_0 = c_0 \cdot c'_0
  • c1=c0c1+c1c0c^*_1 = c_0 \cdot c'_1 + c_1 \cdot c'_0
  • c2=c1c1c^*_2 = c_1 \cdot c'_1
  • return c=(c0,c1,c2)c^* = (c^*_0, c^*_1, c^*_2)

Remarks

  • Similarly, as in addition, the noise of the resulting ciphertext cc^* increases.
  • We increase the number of ciphertext components by 1. This is not sustainable.
  • Our decryption equation is linear, however after mul we have a quadratic decryption equation with 3 ciphertexts that doesn't play well with our idea of linear decryption equation.

To solve the remarks the concept of relinearization is introduced.

Relinearization

The concept was explained in the BFV blogpost as well.

Intuition: We want to transform the quadratic equation c0+c1s+c2s2c^*_0 + c^*_1 \cdot \red{s} + c^*_2 \cdot \red{s}^2 in s\red{s} into some other linear equation c^0+c^1s^\hat c_0 + \hat c_1 \cdot \red{\hat s} in some other secret key s^\red{\hat s}.

In order to do this we need to give some extra information (a "hint") about the key s\red{s} that will help us get s^\red{\hat s}.

Consider the hint to be the pair:

(ek0,ek1)=((as+te)+s2,a)(ek_0, ek_1) = ((a \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e}) + \textcolor{red}{s}^2, -a)

This is very similar to how the public key is generated and we can use the PubKeyGen -> (pk0, pk1) to generate it: (pk0+s2,pk1)(pk_0 + \red{s}^2, pk_1) Intuitively, we use a RLWE sample to hide s2\red{s}^2.

Notice that:

ek0+ek1s=as+e+s2as=s2+eek_0 + ek_1 \cdot \textcolor{red}{s} = \cancel{\textcolor{red}{a} \cdot \textcolor{red}{s}} + \textcolor{darkgreen}{e} + \textcolor{red}{s}^2 - \cancel{\textcolor{red}{a} \cdot \textcolor{red}{s}} = \textcolor{red}{s}^2 + \textcolor{darkgreen}{e}

The easiest way to get the term c2s2c^*_2 \red{s}^2 from the above equation is to multiply it by c2c^*_2. However, c2c^*_2 is a random element in RqR_q and it will yield some large noise c2ec^*_2\textcolor{darkgreen}{e}. So we have to do something smarter.

Key switching v1

Key switching is a variant of relinearization. We start with a ciphertext cc.

Idea:
Split the ciphertext into multiple "small" ciphertexts (for now think of small as the ciphertext polynomials having small coefficents). We can do this by decomposing the ciphertext coefficients into a small base TT.

Intuition:
To build an intuition, we can take the most common bases used in representing numbers:

  • Base 10: 12310=3100+2101+1102123_{10} = 3 \cdot 10^0 + 2 \cdot 10 ^1 + 1 \cdot 10^2
  • Base 2: 1210=11002=123+122+021+02012_{10} = 1100_2 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0

Programmatically, this can be done by dividing the integer by the base TT repeatedly and collecting the remainders.

In Python code:

def int2base(x: int, base: int) -> List[int]:
    digits = []
    while x > 0:
        q, r = divmod(x, base)
        digits.append(r)
        x = q
    return digits
    
print(int2base(123, 10))
# [3, 2, 1]
print(int2base(12, 2))
# [0, 0, 1, 1]

A ciphertext component cRqc \in R_q is a polynomial of degree less than nn, with coefficients in {0,1,..,q1}\{0,1,..,q-1\}, which we denote as follows: c(x)=c[0]+c[1]x+...+c[n1]xn1c(x) = c[0] + c[1]x + ... + c[n-1]x^{n-1}

We want to write the coefficients (c[0],...,c[n1])(c[0], ..., c[n-1]) in base TT. Since any coefficient is less than qq, this decomposition has at most logTq+1\lfloor \log_T q \rfloor + 1 terms. For example c[0]=i=0logTqTic[0](i)c[0] = \sum_{i=0}^{\lfloor \log_T q \rfloor} T^i c[0]^{(i)} where c[0](i)c[0]^{(i)} is the corresponding digit <T< T in the decomposition. Using these digits we can construct the polynomials c(i)c^{(i)}:

c(i)(x)=c[0](i)+c[1](i)x+...+c[n1](i)xn1c^{(i)}(x) = c[0]^{(i)} + c[1]^{(i)}x + ... + c[n-1]^{(i)}x^{n-1}

Then using these polynomials we can decompose the original polynomial cc:

c=i=0logTqTic(i)modqc = \sum_{i=0}^{\lfloor \log_T q \rfloor} T^i \cdot c^{(i)} \bmod q

The polynomials c(i)c^{(i)} are elements of RTR_T and for a reasonable small TT they have small coefficients (<T< T). For each one of them we generate the hints:

(ek0(i),ek1(i))=(ais+tei+Tis2,ai)(ek_0^{(i)}, ek_1^{(i)}) = (a_i \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e_i} + T^i\textcolor{red}{s}^2, -a_i)

with aiRRqa_i \xleftarrow{R} R_q and eiχ\textcolor{darkgreen}{e_i} \leftarrow \chi.

Now we go back to our ciphertext c=(c0,c1,c2)c^* = (c_0^*, c_1^*, c_2^*), the result of EvalMul. We decompose c2c^*_2 in the base TT and we get:

c2=i=0logTqTic2(i)modqc^*_2 = \sum_{i=0}^{\lfloor \log_T q \rfloor} T^i \cdot {c^*_2}^{(i)} \bmod q

Then we construct the new ciphertext c^\hat c with the two components:

c^0=c0+i=0logTqek0(i)c2(i)=c0+i=0logTq((ais+tei)+Tis2)c2(i)c^1=c1+i=0logTqek1(i)c2(i)=c1+i=0logTqaic2(i)\begin{aligned} \hat c_0 &= c^*_0 + \sum_{i=0}^{\lfloor \log_T q \rfloor} ek_0^{(i)} \cdot {c^*_2}^{(i)} = c^*_0 + \sum_{i=0}^{\lfloor \log_T q \rfloor} ((a_i \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e_i}) + T^i\textcolor{red}{s}^2 )\cdot {c^*_2}^{(i)}\\ \hat c_1 &= c^*_1 + \sum_{i=0}^{\lfloor \log_T q \rfloor} ek_1^{(i)} \cdot {c^*_2}^{(i)} = c^*_1 + \sum_{i=0}^{\lfloor \log_T q \rfloor} -a_i \cdot {c^*_2}^{(i)} \end{aligned}

Using the above relations, we obtain the following linear equation:

c^0+c^1s=c0+c1s+c2s2mm+i=0logTqteic2(i)relinearization error\hat c_0 + \hat c_1 \cdot \textcolor{red}{s} = \underbrace{c^*_0 + c^*_1 \cdot \textcolor{red}{s} + c^*_2 \cdot \textcolor{red}{s}^2}_{m \cdot m'} + \underbrace{ \sum_{i=0}^{\lfloor \log_T q \rfloor} t\textcolor{darkgreen}{e_i} \cdot {c^*_2}^{(i)}}_{\text{relinearization error}}

(the terms containing aisa_i \cdot \red{s} from c^0\hat c_0 and ais-a_i \cdot \red{s} from c^1s\hat c_1 \cdot \red{s} cancel out, c2c^*_2 is reconstructed and we are left with an error term).

Because the relinearization error is a multiple of tt, it goes away when we decrypt and reduce modt\bmod t as long as the relinearization error does not wrap m=mmm^* = m\cdot m' around qq.

Remarks

  • We need to relinearize after a multiplication.
  • A smaller TT means we have a smaller noise, but more relinearization keys are needed.
  • TT is chosen based on what we want to optimize. We usually want to choose TT to introduce a noise around the size of the noise in the ciphertexts. Once the noise grows we can use T2T^2 or something else. We can also choose a big TT at the start (which introduces lots of starting noise) and we don't need to change it later.

Modulus switching

Task: You want to reduce the noise that accumulates in the ciphertext, after performing homomorphic operations. The modulus switching technique allows us to decrease the noise, to ensure the decryption is still correct after performing homomorphic operations. More analysis is provided in a dedicated section below.

Idea: The technique uses two moduli Q,qQ, q with q<Qq < Q and qQq | Q. This involves changing the ring where the ciphertexts live, RQR_Q, with a ring RqR_q, that is parametrized by the smaller modulus. When you perform this change, the coefficient ring ZQ\mathbb Z_Q is "approximated" by some ring Zq\mathbb Z_q, in the intuitive sense that the numbers become smaller (the numbers are scaled down by some factor). As we will see this means that the noise will be smaller in absolute value. Although, the noise will relatively stay the same, since q<Qq < Q, we mostly care about the magnitude of the noise, especially in multiplications.

You can perform this repeatedly with many moduli {q0,q1,...,qL}\{q_0, q_1, ..., q_L\} with decreasing values to lower the noise after each multiplication.

The easiest way to do this is to scale down the ciphertext's components by q/Qq / Q and smartly round in a way to keep the decryption equation correct. To ensure this, we want the scaling to keep the following propriety: c~i=cimodt\tilde c_i = c_i \bmod t , where c~i(q/Q)ci\tilde c_i \approx (q / Q) c_i where i{0,1}i \in \{0, 1\}.

The two requirements that we want to have are

  1. The decryption should be correct (decryption mod QQ should be the same as decryption mod qq): [c0+c1s]Q=[c~0+c~1s]qmodt[c_0 + c_1 \cdot \red{s}]_Q = [\tilde c_0 + \tilde c_1 \cdot \red{s}]_q \bmod t.
  2. The noise scales down.

Rounding
In order for the decryption to be correct we must adjust cic_i before scaling by q/Qq / Q. To do this we add a small correction term δi\delta_i per component. We require δi\delta_i to:

  1. Only influence the error, hence δi0modt\delta_i \equiv 0 \bmod t (it will disappear when decrypting)
  2. Make the ciphertext to be divisible by Q/q Q / q:
    ci+δi0modQqδicimodQqc_i + \delta_i \equiv 0 \bmod \dfrac Q q \Rightarrow \delta_i \equiv -c_i \bmod \dfrac Q q

One easy choice to set the correction terms such that both properties hold is δi=t[cit1]Q/q\delta_i = t [-c_i t^{-1}]_{Q/q} where t1t^{-1} is the inverse of tt modulo Q/qQ / q.

In the end, we define the components c~i\tilde c_i of the modulus switched ciphertext: c~i=qQ(ci+δi)\tilde c_i = \dfrac q Q(c_i + \delta_i)

Correctness (Click for math)

Now, let's check the decryption equation is actually correct. For a kRk \in R:

[c~0+c~1s]q=c~0+c~1skq=qQ(c0+δ0)+qQ(c1+δ1)skq=qQ(c0+c1s+δ0+δ1s)kq=qQ([c0+c1s]Q+kQ+δ0+δ1s)kq=qQ[c0+c1s]Qmmodt+qQ(δ0+δ1s)0modt+kqkqqQmmodt\begin{aligned} [\tilde c_0 + \tilde c_1 \cdot \textcolor{red}{s}]_q &= \tilde c_0 + \tilde c_1 \cdot \textcolor{red}{s} - kq \\ &= \dfrac q Q(c_0 + \delta_0) + \dfrac q Q (c_1 + \delta_1) \cdot \textcolor{red}{s} - kq \\ &= \dfrac q Q(c_0 + c_1 \cdot \textcolor{red}{s} + \delta_0 + \delta_1 \cdot \textcolor{red}{s}) - kq \\ &= \dfrac q Q([{c_0 + c_1 \cdot \textcolor{red}{s}}]_Q + kQ + \delta_0 + \delta_1 \cdot \textcolor{red}{s}) - kq \\ &= \dfrac q Q \underbrace{[{c_0 + c_1 \cdot \textcolor{red}{s}}]_Q}_{\equiv m \bmod t} + \underbrace{\dfrac q Q (\delta_0 + \delta_1 \cdot \textcolor{red}{s})}_{\equiv 0 \bmod t} + kq - kq \\ &\equiv \dfrac q Q m \bmod t \end{aligned}

When doing c0+c1s=[c0+c1s]Q+kQc_0 + c_1 \cdot \red{s} = [c_0 + c_1 \cdot \red{s}]_Q + kQ we mention that kk is the same as in [c~0+c~1s]q=c~0+c~1skq[\tilde c_0 + \tilde c_1 \cdot \red{s}]_q = \tilde c_0 + \tilde c_1 \cdot \red{s} - kq under some conditions (see lemma 1 from here).

In the end we decrypt qQm\dfrac q Q m instead of mm. In practice this can be solved by multiplying by Q/qQ/q before encryption or after decryption, or to take Q/q1modtQ/q \equiv 1 \bmod t (however such a Q/qQ/q can be harder to find).


Key switching v2

Now that we know about modulus switching we introduce a second version to do key switching in BGV. Recall that the key switching technique is used in relinearization, for decreasing the size of the ciphertext obtained in multiplication.

Idea: Given two moduli q,Qq, Q with q<Qq < Q and qQq | Q, we start with elements in RqR_q and we make a detour in a ring RQR_Q with a bigger modulus QQ where we perform our relinearization. Then we perform modulus switching to go back to our small ring RqR_q.

We generate the hint:

(ek0,ek1)=((as+te+Qqs2),a)modQ(ek_0, ek_1) = ((a \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e} + \frac{Q}{q} \textcolor{red}{s}^2), -a) \bmod Q

Recall that c=(c0,c1,c2)c^* = (c^*_0, c^*_1, c^*_2) is the result of the mul. Then we compute the components of the new ciphertext c^\hat c:

c^0=Qqc0+c2ek0modQc^1=Qqc1+c2ek1modQ\begin{aligned} \hat c_0 &= \frac Q q c_0^* + c_2^* \cdot ek_0 \bmod Q\\ \hat c_1 &= \frac Q q c_1^* + c_2^* \cdot ek_1 \bmod Q \end{aligned}

Lastly, we scale them both using modulus switching: c^i=qQ(c^i+δi)\hat c_i = \dfrac q Q (\hat c_i + \delta_i) with δi=t[cit1]Q/q\delta_i = t[-c_i t^{-1}]_{Q/q}, like before.

The relinearization equation looks like this:

c^0+c^1s=c0+c1s+c2s2mm+qQ(tc2e+δ0+δ1s)relinearization error\hat c_0 + \hat c_1 \cdot \textcolor{red}{s} = \underbrace{c_0^* + c_1^* \cdot \textcolor{red}{s} + c_2^* \cdot \textcolor{red}{s}^2}_{m\cdot m'} + \underbrace{\dfrac q Q (t c_2^* \cdot \textcolor{darkgreen}{e} + \delta_0 + \delta_1 \cdot \textcolor{red}{s})}_{\text{relinearization error}}

Because the relinearization error is a multiple of tt (remember that we chose δi\delta_i to be multiples of tt too, to not influence the error), it will go away when we decrypt and reduce modt\bmod t as long as the relinearization error does not wrap m=mmm^* = m\cdot m' around qq.

Correctness (click for math)
c^0+c^1s=qQ(Qqc0+c2ek0+δ0)+(qQ(Qqc1+c2ek1)+δ1)s=qQ(Qqc0+c2(as+te+Qqs2)+δ0)++(qQ(Qqc1+c2(a))+δ1)s=c0+c1s+c2s2+qQ(tc2e+δ0+δ1s)=mmmodt\begin{aligned} \hat c_0 + \hat c_1 \cdot \textcolor{red}{s} &= \frac{q}{Q} \left( \frac{Q}{q} c_0^* + c_2^* \cdot ek_0 + \delta_0 \right) + \left(\frac{q}{Q} \left ( \frac{Q}{q} c_1^* + c_2^* \cdot ek_1 \right) + \delta_1 \right) \cdot \textcolor{red}{s} \\ &= \frac{q}{Q} \left( \frac{Q}{q} c_0^* + c_2^* \cdot \left( a \cdot \textcolor{red}{s} + t\textcolor{darkgreen}{e} + \frac{Q}{q} \textcolor{red}{s}^2 \right) + \delta_0 \right) + \\ &+ \left(\frac{q}{Q} \left ( \frac{Q}{q} c_1^* + c_2^* \cdot (-a)\right) + \delta_1 \right) \cdot \textcolor{red}{s} \\ &= c_0^* + c_1^* \cdot \textcolor{red}{s} + c_2^* \cdot s^2 + \frac{q}{Q} (tc_2^* \cdot \textcolor{darkgreen}{e} + \delta_0 + \delta_1 \cdot \textcolor{red}{s}) \\ &= mm' \bmod t \end{aligned}

Noise analysis

The main motivation of analysing the noise growth is because we want to set the parameters of the scheme based on it.

Relevant papers:

Measuring Noise

When doing operations (such as addition, multiplication) with noisy ciphertexts, the total noise accumulates. In the end we want our decryption to be correct. However, this can only happen if the accumulated noise does not exceed some bound.

fhe_noise

Intuition: We want to "measure" this accumulated noise by looking at "how much" a polynomial can impact an operation it's involved in. For example, we can analyze the impact of the polynomials eie_i which represent the RLWE noise or of the secret ss. We can represent the polynomial's impact with a number.

We can "measure" the impact of the polynomials using the:

  1. Infinity norm: a=maxai\|a\|_\infty = \max{|a_i|}, which is the value of the biggest coefficient in absolute value.
  2. Canonical norm: acan\can a. In order to define it we use the so called canonical embedding of the polynomial.

While the infinity norm is easy to understand, the canonical embedding is a bit more mathematically involved. Instead of searching for a way to measure the impact of a polynomial aRa \in R, we transfer the polynomial in another space, such as Cn\mathbb C^n, and we search for a better measure there.

Recall that we work with polynomials from the ring Rq=Zq[X]/(Xn+1)R_q = \mathbb Z_q[X]/(X^n + 1) with nn a power of 22.

Canonical embedding
We have the quotient polynomial Xn+1X^n + 1 of RR which has the complex roots {ζ0,,ζn1}\{\zeta_0, \dots, \zeta_{n-1}\} with ζin=1ζi2n=1\zeta_i^n = -1 \Rightarrow \zeta_i^{2n} = 1.
Then we take a polynomial aRa \in R:
a(X)=a0+a1X+...an1Xn1a(X) = a_0 + a_1X + ... a_{n-1}X^{n-1} and we evaluate aa in every root ζi\zeta_i. This leads to a vector (a(ζ0),...a(ζn1))Cn\left(a(\zeta_0), ... a(\zeta_{n-1})\right) \in \mathbb C^n. We call this vector the canonical embedding of aa.
The canonical embedding is defined as

σ:RCn,σ(a)=(a(ζ0),...a(ζn1))\sigma: R \to \mathbb C^n, \quad \sigma(a) = \left(a(\zeta_0), ... a(\zeta_{n-1})\right)

Canonical norm
Since now we have obtained a new vector in Cn\mathbb C^n we can look at its infinity norm and define the canonical norm acan=σ(a)\can a = \|\sigma(a)\|_\infty.

In practice, the canonical norm is used to compute the noise bounds, because it provides a better decryption noise bound.

  1. There is a relationship between these norms: ac2nacan\|a\|_{\infty} \leq c_{2n}\cdot \can a for some constant c2nc_{2n}, which is 11 when nn is a power of 22 (see this). With this inequality in mind, it suffices to assure correct decryption by setting the canonical norm of the noise to be less than q/2q/2.
  2. When doing multiplications, the noise bound offered by the canonical norm increases slower than the bound offered by the infinity norm. We have these two inequalities:
abγababcanacanbcan\begin{aligned} \|ab\|_\infty &\leq \gamma\|a\|_\infty \|b\|_\infty \\ \can {ab} &\leq \can a \can b \end{aligned}

where γ>1\gamma > 1 is the so-called expansion factor of the ring RR. For more details, see this.

Noise bounds
Suppose we choose aRa \in R with coefficients sampled independently from one of the distributions (discrete Gaussian, random, ternary). Let VaV_a be the variance of each coefficient (a0,...an)(a_0, ... a_n) in aa. In Ilia Iliashenko's thesis and in the Finding and Evaluating Parameters for BGV paper it's shown that we can choose a number DD such that acanDnVa \can a \leq D \sqrt{n V_a} holds with overwhelming probability. In practice, we set D=6D = 6.

When analysing the noise growth we'll make use of the following proprieties. For two polynomials a,bRa, b \in R with variances Va,VbV_a, V_b and some constant kk we have:

  • Va+b=Va+VbV_{a+b} = V_a + V_b