Fully Homomorphic Encryption without Modulus Switching - Revision history

Gturcas: /* The complexity of the decryption circuit */

2021-02-07T16:10:35Z

The complexity of the decryption circuit

Gturcas: /* The Homomorphic Properties of SI-HE */

2021-01-24T16:56:06Z

The Homomorphic Properties of SI-HE

Gturcas: /* The Homomorphic Properties of SI-HE */

2021-01-24T16:43:32Z

The Homomorphic Properties of SI-HE

Gturcas: /* The Homomorphic Properties of SI-HE */

2021-01-24T16:41:33Z

The Homomorphic Properties of SI-HE

Gturcas: /* The Homomorphic Properties of SI-HE */

2021-01-24T16:16:07Z

The Homomorphic Properties of SI-HE

Gturcas: /* The Homomorphic Properties of SI-HE */

2021-01-24T16:15:49Z

The Homomorphic Properties of SI-HE

Gturcas: /* A scale Invariant Homomorphic Encryption Scheme */

2021-01-24T16:12:55Z

A scale Invariant Homomorphic Encryption Scheme

Gturcas: /* A scale Invariant Homomorphic Encryption Scheme */

2021-01-18T14:59:15Z

A scale Invariant Homomorphic Encryption Scheme

Gturcas: /* A scale Invariant Homomorphic Encryption Scheme */

2021-01-18T14:49:02Z

A scale Invariant Homomorphic Encryption Scheme

Gturcas: /* A scale Invariant Homomorphic Encryption Scheme */

2021-01-18T14:48:18Z

A scale Invariant Homomorphic Encryption Scheme

← Older revision		Revision as of 16:10, 7 February 2021
Line 148:		Line 148:

	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.		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==

← Older revision		Revision as of 16:56, 24 January 2021
Line 142:		Line 142:

	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.		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.

	==References==		==References==

@@ Line 136: / Line 136: @@
 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</math>, then we have the following:
+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>.
 ==References==

← Older revision		Revision as of 16:41, 24 January 2021
Line 133:		Line 133:

	is <math>L</math>-homomorphic.		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</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>.

	==References==		==References==

@@ Line 130: / Line 130: @@
 <b> Theorem.</b>(4.2 in [1]) The scheme SI-HE with parameters <math>n, q, |\chi| \leq B, L</math> for which
-<center>q/B \geq (O(n \log q))^{L+O(1)},</center>
+<center><math>  q/B \geq (O(n \log q))^{L+O(1)} </math>,</center>
 is <math>L</math>-homomorphic.
 ==References==

← Older revision		Revision as of 16:15, 24 January 2021
Line 125:		Line 125:

	== The Homomorphic Properties of SI-HE ==		== 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>q/B \geq (O(n \log q))^{L+O(1)},</center>
		+
		+	is <math>L</math>-homomorphic.

	==References==		==References==

@@ Line 124: / Line 124: @@
 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.
-@TODO: Write the homomorphic properties from Section 4.1!
+== The Homomorphic Properties of SI-HE ==
 ==References==

← Older revision		Revision as of 14:59, 18 January 2021
Line 123:		Line 123:

	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 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.
		+
		+	@TODO: Write the homomorphic properties from Section 4.1!

	==References==		==References==

@@ Line 108: / Line 108: @@
 <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>
+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>.

← Older revision		Revision as of 14:48, 18 January 2021
Line 121:		Line 121:

	* 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>.		* 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.

	==References==		==References==