Difference between revisions of "Fully Homomorphic Encryption without Modulus Switching"

From certFHE Community KB
Jump to navigation Jump to search
 
(28 intermediate revisions by the same user not shown)
Line 13: Line 13:
 
We start by presenting Regev's <ref name='Regev'> O. Regev. On lattices, learning with errors, random linear codes, and cryptography.
 
We start by presenting Regev's <ref name='Regev'> 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 </ref> basic public-key encryption scheme.
 
In Harold N. Gabow and Ronald Fagin, editors, STOC, pages 84–93. ACM, 2005 </ref> basic public-key encryption scheme.
 +
 +
=== The Regev scheme ===
  
 
Let <math> q= q(n) </math> be an integer function and let <math>\chi(n) </math> be a distribution over <math>\mathbb Z </math>. The scheme 'Regev' is defined as follows:
 
Let <math> q= q(n) </math> be an integer function and let <math>\chi(n) </math> be a distribution over <math>\mathbb Z </math>. The scheme 'Regev' is defined as follows:
Line 24: Line 26:
  
 
* Regev.Enc(<math>pk, m </math>): To encrypt a message <math> m \in \{0,1 \} </math> using <math>pk=P </math>, sample <math>r \in \{ 0,1\}^N </math> uniformly and output the ciphertext
 
* Regev.Enc(<math>pk, m </math>): To encrypt a message <math> m \in \{0,1 \} </math> using <math>pk=P </math>, sample <math>r \in \{ 0,1\}^N </math> uniformly and output the ciphertext
<math>c := \left[ P^T \cdot r+ \left\lceil \frac{q}{2} \right\rceil \cdot m \right]_q \in \mathbb Z_q^{n+1} </math>
+
 
 +
<center><math>c := \left[ P^T \cdot r+ \left\lfloor \frac{q}{2} \right\rfloor \cdot \hat m \right]_q \in \mathbb Z_q^{n+1},</math> </center>
 +
where <math> \hat m := (m,0,\dots, 0) \in \{0,1 \}^{n+1} </math>.
 +
 
 +
* Regev.Dec(<math>sk, c </math>): To decrypt <math>c \in \mathbb Z_q^{n+1}</math> using the secret key <math>sk=s</math>, compute
 +
 
 +
<center><math> m := \left[ \left\lfloor 2 \cdot \frac{[<c,(1,2)>]_q}{q} \right\rceil \right]_2.</math></center>
 +
 
 +
In order to prove corectness, the author first shows (Lemma 3.1 in [1]) that if <math>q,n,N</math> and <math>\chi</math>- <math> B</math>-bounded are parameters for the 'Regev' scheme described above and if <math>c</math> is the fresh encryption of some message <math>m \in \{0,1 \} </math>, then
 +
 
 +
<center><math><c,(1,s)> = \left\lfloor \frac{q}{2} \right\rfloor \cdot m + e </math>  </center>
 +
 
 +
for some <math>e </math> with <math>|e| \leq N \cdot B</math>.
 +
 
 +
Then, Lemma 3.2 in the same article asserts that if <math>s \in \mathbb Z^n </math> is some vector and <math>c \in \mathbb Z_q^{n+1} </math> is such that
 +
 
 +
<center><math><c,(1,s)> = \left\lfloor \frac{q}{2} \right\rfloor \cdot m + e </math>  </center>
 +
 
 +
with <math>m \in \{ 0,1\} </math> and <math>|e| < \lfloor q/2 \rfloor/2 </math>, then
 +
 
 +
<center> Regev.Dec(<math>s,c </math> )= <math>m</math> .</center>
 +
 
 +
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
 +
 
 +
<center> <math> BitDecomp_q(x) : \mathbb Z^n \to \{0,1 \}^{n \cdot \lceil \log q \rceil} </math> </center>
 +
 
 +
and
 +
 
 +
<center><math>  PowersOfTwo_q(y) : \mathbb Z^n \to \mathbb Z_q^{n \cdot \lceil \log q  \rceil}. </math> </center>
 +
 
 +
When the modulus <math>q </math> is clear from the context we will omit its writing.
 +
 
 +
We also recall the property
 +
 
 +
<center><math><x,y> = <BitDecomp_q(x), PowersOfTwo_q(y)> \pmod{q} </math>.</center>
 +
 
 +
===Key switching===
 +
 
 +
In the functions described below <math>q </math> is an integer and <math> \chi </math> is a distribution over <math>\mathbb Z </math>.
 +
 
 +
*<math> SwitchKeyGen_{q, \chi}(s,t </math>): For a 'source' key <math> s \in \mathbb Z^{n_s} </math> and target key <math>t \in \mathbb Z^{n_t} </math> this outputs matrix with <math>n_s \cdot \lceil \log q \rceil </math> rows and <math>(n_t+1) </math> columns, very similar to an encryption of <math>PowersOfTwo_q(s)</math> under the secret key <math>t </math>. Let us call this matrix <math>P_{s:t} </math>.
 +
 
 +
 
 +
* <math>SwithcKey_{q}(P_{s:t}, c_s) </math>: To switch a ciphertext from a secret key <math> s </math> to <math>(1,t) </math>, output
 +
 
 +
<center><math> c_t := [P_{s:t}^T \cdot BitDecomp_q(c_s) ]_q </math>.</center>
 +
 
 +
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 <math>q = q(n) </math> be an integer function, <math>L = L(n) </math> a polynomial and <math> \chi= \chi(n) </math>  a distribution over the integers. The SI-HE scheme is defined as follows:
 +
 
 +
* SI-HE.Keygen(<math>1^L, 1^n </math>): Sample <math> L+1 </math> vectors <math>s_0, \dots, s_L \leftarrow </math> Regev.SecretKeygen(<math>1^n </math> ) and generate a Regev public key for the first one: <math>P_0 \leftarrow Regev.PublicKeygen(s_0) </math>. For all <math> i \in [L] </math>, define
 +
 
 +
<center><math>\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} </math></center>
 +
 
 +
and compute
 +
 
 +
<center> <math>P_{(i-1):i} \leftarrow SwitchKeyGen(\tilde{s_{i-1}}, s_i)</math>  .</center>
 +
 
 +
Output <math>pk := P_0 </math> and <math>evk = \{P_{(i-1):i}: i \in [L] \} </math> and <math>sk = s_L</math>.
 +
 
 +
* SI-HE.Enc(<math>pk, m </math>): This is identical to Regev's. Just output <math>c \leftarrow Regev.Enc(pk,m)</math>.
 +
 
 +
* SI-HE.Eval(<math>evk </math>): Here we describe homomorphic addition and multiplication over the field with two elements, operations that allow the evaluation of depth <math> L </math>  arithmetic circuits in a gate-by-gate manner. The convention for a gate at level <math> i </math> of the circuit is that the operand ciphertexts are decryptable using <math>s_{i-1} </math>, and the output of the homomorphic operation is decryptable using <math>s_i </math>.
 +
 
 +
Recall that evk contains key switching parameters from <math>\tilde{s_{i-1}} </math> to <math>s_i</math>, homomorphic addition and multiplication both first produce an intermediate output <math>\tilde c </math> that corresponds to <math>\tilde{s_{i-1}} </math> and then use key switching to obtain the final output.
 +
 
 +
-- SI-HE.<math>Add_{evk}(c_1,c_2)</math>: Assume that both input ciphertexts are encrypted under the same secret key <math>s_{i-1} </math>. First compute
 +
 
 +
<math>\tilde{c}_{add} := PowersOfTwo(c_1+c_2) \otimes PowersOfTwo((1,0,\dots, 0)) </math>
 +
 
 +
and then output
 +
 
 +
<math>c_{add} := SwitchKey(P_{(i-1):i}, \tilde{c}_{add}) \in \mathbb Z_q^{n+1}.</math>
 +
 
 +
Above the ciphertexts are first added (as vectors) to obtain <math>c_1+c_2 </math>, but the output of this corresponds to <math>s_{i-1} </math> and not <math>s_i </math>, as required. The vector <math>\tilde{c}_{add} </math> is generated by tensoring with a trivial ciphertext, the result being an encryption of the sum under the key <math>\tilde{s}_{i-1} </math>. This result can now be key-switched to obtain an output corresponding to <math>s_i </math>. <b>The PowersOfTwo procedure is used in order to control the norm of the secret key. </b>
 +
 
 +
-- SI-HE.<math>Mult_{evk}(c_1,c_2)</math>: Again, we assume that both input ciphertexts are encrypted under the same secret key <math>s_{i-1} </math>.
 +
 
 +
One first computes
 +
 
 +
<math>\tilde{c}_{mult} := \left\lceil \frac{2}{q} \cdot \left( PowersOfTwo(c_1) \otimes PowersOfTwo(c_2) \right) \right\rceil </math>,
 +
 
 +
then output
 +
 
 +
<math>c_{mult} \leftarrow SwitchKey(P_{(i-1):i}, \tilde{c}_{mult}) \in \mathbb Z_{q}^{n+1} </math>.
 +
 
 +
* SI-HE.<math>Dec_{sk}(c)</math>: If <math>c</math> is a ciphertext that corresponds to <math>s_L </math>, then decryption is identical to the one in Regev's scheme. Just output <math>m \leftarrow Regev.Dec_{sk}(c)</math>.
 +
 
 +
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.
 +
 
 +
<b> Theorem.</b>(4.2 in [1]) The scheme SI-HE with parameters <math>n, q, |\chi| \leq B, L</math> for which
 +
 
 +
<center><math>  q/B \geq (O(n \log q))^{L+O(1)} </math>,</center>
 +
 
 +
is <math>L</math>-homomorphic.
 +
 
 +
The theorem is proved using a lemma whose assertion establishes bounds for the growth of the noise in gate evaluation.
 +
 
 +
To summarise, if <math> c_1,c_2 </math> are two ciphertexts such that the magnitudes of their noise vectors <math>  |e_1|, |e_2| < E < q/2</math>, then we have the following:
 +
 
 +
After homomorphic opperation (addition or multiplication) on <math>c_1 </math> and <math> c_2 </math>, the ciphertext <math>c_{add/mult}</math> has noise <math>|e_{add/mult}| < O(n \log q) \cdot \max\{E,  (n \log^2{q} \cdot B)\} </math>, where <math>B</math> is the bound on the noise distribution <math> \chi</math>.
 +
 
 +
 
 +
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 <math>c </math>, the function <math>f_c(s) = SI-HE.Dec_{s}(c) </math> can be implemented by a circuit of depth <math>O(\log n + \log \log{q}) </math> (This result is proved in many places, see the discussion proceeding Lemma 4.4 for details).
 +
 
 +
A corollary is the following: If <math>n,q, \chi| \leq B </math> and <math>q/B \geq (n \log q)^{O(\log n+ \log \log{q})} </math>, 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
  
 
==References==
 
==References==

Latest revision as of 16:10, 7 February 2021

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 , write . This is not the same with the ring . For any , write for the unique value in that is congruent to modulo .

If are two -dimensional vectors, then the tensor product is the dimensional vector containing all elements of the form . Note that

Building Blocks of a homomorphic encryption scheme

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

The Regev scheme

Let be an integer function and let be a distribution over . The scheme 'Regev' is defined as follows:

  • Regev.SecretKeygen( ): Sample uniformly. Output .
  • Regev.PublicKeygen(): Let . Sample uniformly then sample . Compute . Here we apply to every entry in the -dimensional vector and define
.

Output .

  • Regev.Enc(): To encrypt a message using , sample uniformly and output the ciphertext

where .

  • Regev.Dec(): To decrypt using the secret key , compute

In order to prove corectness, the author first shows (Lemma 3.1 in [1]) that if and - -bounded are parameters for the 'Regev' scheme described above and if is the fresh encryption of some message , then

for some with .

Then, Lemma 3.2 in the same article asserts that if is some vector and is such that

with and , then

Regev.Dec( )= .

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

and

When the modulus is clear from the context we will omit its writing.

We also recall the property

.

Key switching

In the functions described below is an integer and is a distribution over .

  • ): For a 'source' key and target key this outputs matrix with rows and columns, very similar to an encryption of under the secret key . Let us call this matrix .


  • : To switch a ciphertext from a secret key to , output
.

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 be an integer function, a polynomial and a distribution over the integers. The SI-HE scheme is defined as follows:

  • SI-HE.Keygen(): Sample vectors Regev.SecretKeygen( ) and generate a Regev public key for the first one: . For all , define

and compute

.

Output and and .

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

Recall that evk contains key switching parameters from to , homomorphic addition and multiplication both first produce an intermediate output that corresponds to and then use key switching to obtain the final output.

-- SI-HE.: Assume that both input ciphertexts are encrypted under the same secret key . First compute

and then output

Above the ciphertexts are first added (as vectors) to obtain , but the output of this corresponds to and not , as required. The vector is generated by tensoring with a trivial ciphertext, the result being an encryption of the sum under the key . This result can now be key-switched to obtain an output corresponding to . The PowersOfTwo procedure is used in order to control the norm of the secret key.

-- SI-HE.: Again, we assume that both input ciphertexts are encrypted under the same secret key .

One first computes

,

then output

.

  • SI-HE.: If is a ciphertext that corresponds to , then decryption is identical to the one in Regev's scheme. Just output .

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 for which

,

is -homomorphic.

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

To summarise, if are two ciphertexts such that the magnitudes of their noise vectors , then we have the following:

After homomorphic opperation (addition or multiplication) on and , the ciphertext has noise , where is the bound on the noise distribution .


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 , the function can be implemented by a circuit of depth (This result is proved in many places, see the discussion proceeding Lemma 4.4 for details).

A corollary is the following: If and , 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

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