# Fully Homomorphic Encryption without Modulus Switching

This scheme proposed by Brakerski [1] has a number of advantages over previous candidates such as BGV. In particular, it uses the same modulus throughout the evaluation process, so there's no need for modulus switching. Security of these scheme is baed on the hardness of the GapSVP problem.

## Preliminaries

For an integer ${\displaystyle q}$, write ${\displaystyle \mathbb {Z} _{q}:=\left(-q/2,q/2\right]\cap \mathbb {Z} }$. This is not the same with the ring ${\displaystyle \mathbb {Z} /q\mathbb {Z} }$. For any ${\displaystyle x\in \mathbb {Q} }$, write ${\displaystyle [x]_{p}}$ for the unique value in ${\displaystyle \left(-q/2,q/2\right]\cap \mathbb {Z} }$ that is congruent to ${\displaystyle x}$ modulo ${\displaystyle q}$.

If ${\displaystyle v,w}$ are two ${\displaystyle n}$-dimensional vectors, then the tensor product ${\displaystyle v\otimes w}$ is the ${\displaystyle n^{2}}$ dimensional vector containing all elements of the form ${\displaystyle v[i]w[j]}$. Note that

${\displaystyle =\cdot .}$

## Building Blocks of a homomorphic encryption scheme

We start by presenting Regev's [2] basic public-key encryption scheme.

### The Regev scheme

Let ${\displaystyle q=q(n)}$ be an integer function and let ${\displaystyle \chi (n)}$ be a distribution over ${\displaystyle \mathbb {Z} }$. The scheme 'Regev' is defined as follows:

• Regev.SecretKeygen( ${\displaystyle 1^{n}}$ ): Sample ${\displaystyle s\leftarrow \mathbb {Z} _{q}^{n}}$ uniformly. Output ${\displaystyle sk=s}$.
• Regev.PublicKeygen(${\displaystyle s}$): Let ${\displaystyle N:=(n+1)(\log q+O(1))}$. Sample uniformly ${\displaystyle A\leftarrow \mathbb {Z} _{q}^{N\times n}}$ then sample ${\displaystyle e\leftarrow \chi ^{N}}$. Compute ${\displaystyle b:=[A\cdot s+e]_{q}}$. Here we apply ${\displaystyle [\cdot ]_{q}}$ to every entry in the ${\displaystyle N}$-dimensional vector ${\displaystyle A\cdot s+e}$ and define
${\displaystyle P:=[b\vert -A]\in \mathbb {Z} _{q}^{N\times (n+1)}}$.

Output ${\displaystyle pk=P}$.

• Regev.Enc(${\displaystyle pk,m}$): To encrypt a message ${\displaystyle m\in \{0,1\}}$ using ${\displaystyle pk=P}$, sample ${\displaystyle r\in \{0,1\}^{N}}$ uniformly and output the ciphertext
${\displaystyle c:=\left[P^{T}\cdot r+\left\lfloor {\frac {q}{2}}\right\rfloor \cdot {\hat {m}}\right]_{q}\in \mathbb {Z} _{q}^{n+1},}$

where ${\displaystyle {\hat {m}}:=(m,0,\dots ,0)\in \{0,1\}^{n+1}}$.

• Regev.Dec(${\displaystyle sk,c}$): To decrypt ${\displaystyle c\in \mathbb {Z} _{q}^{n+1}}$ using the secret key ${\displaystyle sk=s}$, compute
${\displaystyle m:=\left[\left\lfloor 2\cdot {\frac {[]_{q}}{q}}\right\rceil \right]_{2}.}$

In order to prove corectness, the author first shows (Lemma 3.1 in [1]) that if ${\displaystyle q,n,N}$ and ${\displaystyle \chi }$- ${\displaystyle B}$-bounded are parameters for the 'Regev' scheme described above and if ${\displaystyle c}$ is the fresh encryption of some message ${\displaystyle m\in \{0,1\}}$, then

${\displaystyle =\left\lfloor {\frac {q}{2}}\right\rfloor \cdot m+e}$

for some ${\displaystyle e}$ with ${\displaystyle |e|\leq N\cdot B}$.

Then, Lemma 3.2 in the same article asserts that if ${\displaystyle s\in \mathbb {Z} ^{n}}$ is some vector and ${\displaystyle c\in \mathbb {Z} _{q}^{n+1}}$ is such that

${\displaystyle =\left\lfloor {\frac {q}{2}}\right\rfloor \cdot m+e}$

with ${\displaystyle m\in \{0,1\}}$ and ${\displaystyle |e|<\lfloor q/2\rfloor /2}$, then

Regev.Dec(${\displaystyle s,c}$ )= ${\displaystyle m}$ .

Brakerski claims that the security of this scheme reduces to the hardness of (a decisional variant of) LWE problem by classical arguments (originally due to Regev [2]).

### Vector decompositions

Recall from BGV the procedures

${\displaystyle BitDecomp_{q}(x):\mathbb {Z} ^{n}\to \{0,1\}^{n\cdot \lceil \log q\rceil }}$

and

${\displaystyle PowersOfTwo_{q}(y):\mathbb {Z} ^{n}\to \mathbb {Z} _{q}^{n\cdot \lceil \log q\rceil }.}$

When the modulus ${\displaystyle q}$ is clear from the context we will omit its writing.

We also recall the property

${\displaystyle ={\pmod {q}}}$.

### Key switching

In the functions described below ${\displaystyle q}$ is an integer and ${\displaystyle \chi }$ is a distribution over ${\displaystyle \mathbb {Z} }$.

• ${\displaystyle SwitchKeyGen_{q,\chi }(s,t}$): For a 'source' key ${\displaystyle s\in \mathbb {Z} ^{n_{s}}}$ and target key ${\displaystyle t\in \mathbb {Z} ^{n_{t}}}$ this outputs matrix with ${\displaystyle n_{s}\cdot \lceil \log q\rceil }$ rows and ${\displaystyle (n_{t}+1)}$ columns, very similar to an encryption of ${\displaystyle PowersOfTwo_{q}(s)}$ under the secret key ${\displaystyle t}$. Let us call this matrix ${\displaystyle P_{s:t}}$.

• ${\displaystyle SwithcKey_{q}(P_{s:t},c_{s})}$: To switch a ciphertext from a secret key ${\displaystyle s}$ to ${\displaystyle (1,t)}$, output
${\displaystyle c_{t}:=[P_{s:t}^{T}\cdot BitDecomp_{q}(c_{s})]_{q}}$.

Details on the correctness and security of this scheme are given at the end of Section 3 in [1].

## A scale Invariant Homomorphic Encryption Scheme

Let ${\displaystyle q=q(n)}$ be an integer function, ${\displaystyle L=L(n)}$ a polynomial and ${\displaystyle \chi =\chi (n)}$ a distribution over the integers. The SI-HE scheme is defined as follows:

• SI-HE.Keygen(${\displaystyle 1^{L},1^{n}}$): Sample ${\displaystyle L+1}$ vectors ${\displaystyle s_{0},\dots ,s_{L}\leftarrow }$ Regev.SecretKeygen(${\displaystyle 1^{n}}$ ) and generate a Regev public key for the first one: ${\displaystyle P_{0}\leftarrow Regev.PublicKeygen(s_{0})}$. For all ${\displaystyle i\in [L]}$, define
${\displaystyle {\tilde {s_{i-1}}}:=BitDecomp((1,s_{i-1}))\otimes BitDecomp((1,s_{i-1}))\in \{0,1\}^{((n+1)\lceil \log q\rceil )^{2}}}$

and compute

${\displaystyle P_{(i-1):i}\leftarrow SwitchKeyGen({\tilde {s_{i-1}}},s_{i})}$ .

Output ${\displaystyle pk:=P_{0}}$ and ${\displaystyle evk=\{P_{(i-1):i}:i\in [L]\}}$ and ${\displaystyle sk=s_{L}}$.

• SI-HE.Enc(${\displaystyle pk,m}$): This is identical to Regev's. Just output ${\displaystyle c\leftarrow Regev.Enc(pk,m)}$.
• SI-HE.Eval(${\displaystyle evk}$): Here we describe homomorphic addition and multiplication over the field with two elements, operations that allow the evaluation of depth ${\displaystyle L}$ arithmetic circuits in a gate-by-gate manner. The convention for a gate at level ${\displaystyle i}$ of the circuit is that the operand ciphertexts are decryptable using ${\displaystyle s_{i-1}}$, and the output of the homomorphic operation is decryptable using ${\displaystyle s_{i}}$.

Recall that evk contains key switching parameters from ${\displaystyle {\tilde {s_{i-1}}}}$ to ${\displaystyle s_{i}}$, homomorphic addition and multiplication both first produce an intermediate output ${\displaystyle {\tilde {c}}}$ that corresponds to ${\displaystyle {\tilde {s_{i-1}}}}$ and then use key switching to obtain the final output.

-- SI-HE.${\displaystyle Add_{evk}(c_{1},c_{2})}$: Assume that both input ciphertexts are encrypted under the same secret key ${\displaystyle s_{i-1}}$. First compute

${\displaystyle {\tilde {c}}_{add}:=PowersOfTwo(c_{1}+c_{2})\otimes PowersOfTwo((1,0,\dots ,0))}$

and then output

${\displaystyle c_{add}:=SwitchKey(P_{(i-1):i},{\tilde {c}}_{add})\in \mathbb {Z} _{q}^{n+1}.}$

Above the ciphertexts are first added (as vectors) to obtain ${\displaystyle c_{1}+c_{2}}$, but the output of this corresponds to ${\displaystyle s_{i-1}}$ and not ${\displaystyle s_{i}}$, as required. The vector ${\displaystyle {\tilde {c}}_{add}}$ is generated by tensoring with a trivial ciphertext, the result being an encryption of the sum under the key ${\displaystyle {\tilde {s}}_{i-1}}$. This result can now be key-switched to obtain an output corresponding to ${\displaystyle s_{i}}$. The PowersOfTwo procedure is used in order to control the norm of the secret key.

-- SI-HE.${\displaystyle Mult_{evk}(c_{1},c_{2})}$: Again, we assume that both input ciphertexts are encrypted under the same secret key ${\displaystyle s_{i-1}}$.

One first computes

${\displaystyle {\tilde {c}}_{mult}:=\left\lceil {\frac {2}{q}}\cdot \left(PowersOfTwo(c_{1})\otimes PowersOfTwo(c_{2})\right)\right\rceil }$,

then output

${\displaystyle c_{mult}\leftarrow SwitchKey(P_{(i-1):i},{\tilde {c}}_{mult})\in \mathbb {Z} _{q}^{n+1}}$.

• SI-HE.${\displaystyle Dec_{sk}(c)}$: If ${\displaystyle c}$ is a ciphertext that corresponds to ${\displaystyle s_{L}}$, then decryption is identical to the one in Regev's scheme. Just output ${\displaystyle m\leftarrow Regev.Dec_{sk}(c)}$.

The author also gives a proof of its security (see Lemma 4.1), i.e. the security of these scheme is reduced to the hardness of a (decisional) LWE problem.

## The Homomorphic Properties of SI-HE

The authors prove the following theorem.

Theorem.(4.2 in [1]) The scheme SI-HE with parameters ${\displaystyle n,q,|\chi |\leq B,L}$ for which

${\displaystyle q/B\geq (O(n\log q))^{L+O(1)}}$,

is ${\displaystyle L}$-homomorphic.

The theorem is proved using a lemma whose assertion establishes bounds for the growth of the noise in gate evaluation.

To summarise, if ${\displaystyle c_{1},c_{2}}$ are two ciphertexts such that the magnitudes of their noise vectors ${\displaystyle |e_{1}|,|e_{2}|, then we have the following:

After homomorphic opperation (addition or multiplication) on ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$, the ciphertext ${\displaystyle c_{add/mult}}$ has noise ${\displaystyle |e_{add/mult}|, where ${\displaystyle B}$ is the bound on the noise distribution ${\displaystyle \chi }$.

As it is usually the case with FHE schemes, homomorphic addition increases noise much more moderately than multiplication, however the noise estimation above is sufficient for proving that the scheme is bootstrappable.

## The complexity of the decryption circuit

For all ciphertexts ${\displaystyle c}$, the function ${\displaystyle f_{c}(s)=SI-HE.Dec_{s}(c)}$ can be implemented by a circuit of depth ${\displaystyle O(\log n+\log \log {q})}$ (This result is proved in many places, see the discussion proceeding Lemma 4.4 for details).

A corollary is the following: If ${\displaystyle n,q,\chi |\leq B}$ and ${\displaystyle q/B\geq (n\log q)^{O(\log n+\log \log {q})}}$, then, under a circular security assumption, this scheme can be bootstrapped into a (non-leveled) fully homomorphic encryption scheme.

## Example of performing basic arithmetic in BFV

At the link below, one can see a quick tutorial on how to perform simple computations (a polynomial evaluation) on encrypted integers using the BFV encryption scheme.

## References

1. Z. Brakerski, Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In: Safavi-Naini R., Canetti R. (eds) Advances in Cryptology – CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_50
2. O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, STOC, pages 84–93. ACM, 2005