Fully Homomorphic Encryption without Modulus Switching

This scheme proposed by Brakerski 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 $q$, write $\mathbb {Z} _{q}:=\left(-q/2,q/2\right]\cap \mathbb {Z}$. This is not the same with the ring $\mathbb {Z} /q\mathbb {Z}$. For any $x\in \mathbb {Q}$, write $[x]_{p}$ for the unique value in $\left(-q/2,q/2\right]\cap \mathbb {Z}$ that is congruent to $x$ modulo $q$.

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

$<v\otimes w,x\otimes y>=<v,x>\cdot <w,y>.$

Building Blocks of a homomorphic encryption scheme

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

The Regev scheme

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

• Regev.SecretKeygen( $1^{n}$ ): Sample $s\leftarrow \mathbb {Z} _{q}^{n}$ uniformly. Output $sk=s$.

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

$P:=[b\vert -A]\in \mathbb {Z} _{q}^{N\times (n+1)}$.

Output $pk=P$.

• Regev.Enc($pk,m$): To encrypt a message $m\in \{0,1\}$ using $pk=P$, sample $r\in \{0,1\}^{N}$ uniformly and output the ciphertext

$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 ${\hat {m}}:=(m,0,\dots ,0)\in \{0,1\}^{n+1}$.

• Regev.Dec($sk,c$): To decrypt $c\in \mathbb {Z} _{q}^{n+1}$ using the secret key $sk=s$, compute

$m:=\left[\left\lfloor 2\cdot {\frac {[<c,(1,2)>]_{q}}{q}}\right\rceil \right]_{2}.$

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

$<c,(1,s)>=\left\lfloor {\frac {q}{2}}\right\rfloor \cdot m+e$

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

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle <c,(1,s)> = \left\lfloor \frac{q}{2} \right\rfloor \cdot m + e }

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

Regev.Dec($s,c$ )= $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

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

and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle PowersOfTwo_q(y) : \mathbb Z^n \to \mathbb Z_q^{n \cdot \lceil \log q \rceil}. }

When the modulus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q } is clear from the context we will omit its writing.

We also recall the property

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle <x,y> = <BitDecomp_q(x), PowersOfTwo_q(y)> \pmod{q} } .

Key switching

In the functions described below Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q } is an integer and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \chi } is a distribution over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb Z } .

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle SwitchKeyGen_{q, \chi}(s,t } ): For a 'source' key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \in \mathbb Z^{n_s} } and target key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t \in \mathbb Z^{n_t} } this outputs matrix with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n_s \cdot \lceil \log q \rceil } rows and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (n_t+1) } columns, very similar to an encryption of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle PowersOfTwo_q(s)} under the secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t } . Let us call this matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_{s:t} } .

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle SwithcKey_{q}(P_{s:t}, c_s) } : To switch a ciphertext from a secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s } to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1,t) } , output

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q = q(n) } be an integer function, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L = L(n) } a polynomial and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \chi= \chi(n) } a distribution over the integers. The SI-HE scheme is defined as follows:

• SI-HE.Keygen(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1^L, 1^n } ): Sample Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L+1 } vectors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_0, \dots, s_L \leftarrow } Regev.SecretKeygen(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1^n } ) and generate a Regev public key for the first one: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_0 \leftarrow Regev.PublicKeygen(s_0) } . For all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i \in [L] } , define

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_{(i-1):i} \leftarrow SwitchKeyGen(\tilde{s_{i-1}}, s_i)} .

Output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle pk := P_0 } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle evk = \{P_{(i-1):i}: i \in [L] \} } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle sk = s_L} .

• SI-HE.Enc(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle pk, m } ): This is identical to Regev's. Just output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c \leftarrow Regev.Enc(pk,m)} .

• SI-HE.Eval(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle evk } ): Here we describe homomorphic addition and multiplication over the field with two elements, operations that allow the evaluation of depth Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L } arithmetic circuits in a gate-by-gate manner. The convention for a gate at level Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i } of the circuit is that the operand ciphertexts are decryptable using Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_{i-1} } , and the output of the homomorphic operation is decryptable using Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_i } .

Recall that evk contains key switching parameters from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde{s_{i-1}} } to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_i} , homomorphic addition and multiplication both first produce an intermediate output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde c } that corresponds to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde{s_{i-1}} } and then use key switching to obtain the final output.

-- SI-HE.Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Add_{evk}(c_1,c_2)} : Assume that both input ciphertexts are encrypted under the same secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_{i-1} } . First compute

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

and then output

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1+c_2 } , but the output of this corresponds to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_{i-1} } and not Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_i } , as required. The vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde{c}_{add} } is generated by tensoring with a trivial ciphertext, the result being an encryption of the sum under the key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde{s}_{i-1} } . This result can now be key-switched to obtain an output corresponding to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_i } . The PowersOfTwo procedure is used in order to control the norm of the secret key.

-- SI-HE.Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Mult_{evk}(c_1,c_2)} : Again, we assume that both input ciphertexts are encrypted under the same secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_{i-1} } .

One first computes

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \tilde{c}_{mult} := \left\lceil \frac{2}{q} \cdot \left( PowersOfTwo(c_1) \otimes PowersOfTwo(c_2) \right) \right\rceil } ,

then output

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_{mult} \leftarrow SwitchKey(P_{(i-1):i}, \tilde{c}_{mult}) \in \mathbb Z_{q}^{n+1} } .

• SI-HE.Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Dec_{sk}(c)} : If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c} is a ciphertext that corresponds to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_L } , then decryption is identical to the one in Regev's scheme. Just output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n, q, |\chi| \leq B, L} for which

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q/B \geq (O(n \log q))^{L+O(1)} } ,

is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1,c_2 } are two ciphertexts such that the magnitudes of their noise vectors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |e_1|, |e_2| < E < q/2} , then we have the following:

After homomorphic opperation (addition or multiplication) on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1 } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_2 } , the ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_{add/mult}} has noise Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |e_{add/mult}| < O(n \log q) \cdot \max\{E, (n \log^2{q} \cdot B)\} } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} is the bound on the noise distribution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c } , the function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f_c(s) = SI-HE.Dec_{s}(c) } can be implemented by a circuit of depth Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n,q, \chi| \leq B } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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.

https://github.com/microsoft/SEAL/blob/main/native/examples/1_bfv_basics.cpp