FHE over the Integers - Revision history

Gturcas: /* Making the scheme fully homomorphic */

2020-12-30T09:56:51Z

Making the scheme fully homomorphic

Gturcas: /* Making the scheme fully homomorphic */

2020-12-30T09:56:24Z

Making the scheme fully homomorphic

Gturcas: /* Ciphertext compression */

2020-12-30T09:51:21Z

Ciphertext compression

Gturcas: /* A somewhat homomorphic encryption scheme */

2020-12-30T09:50:18Z

A somewhat homomorphic encryption scheme

Gturcas: /* A somewhat homomorphic encryption scheme */

2020-12-30T09:23:47Z

A somewhat homomorphic encryption scheme

Gturcas at 09:21, 30 December 2020

2020-12-30T09:21:37Z

Gturcas at 09:19, 30 December 2020

2020-12-30T09:19:37Z

Gturcas at 09:00, 30 December 2020

2020-12-30T09:00:04Z

Gturcas: /* References */

2020-12-30T08:58:13Z

References

Gturcas at 06:45, 25 May 2020

2020-05-25T06:45:21Z

@@ Line 64: / Line 64: @@
 It can be easily shown that the modified scheme is correct for all the circuits that the original scheme <math> \mathcal E </math> could handle.
-On the other hand, the authors prove (see Theorem 3 of loc. cit.) that new scheme can handle its decryption circuit, hence it can be [[bootstrapped]] and transformed into a [[fully homomorphic encryption scheme]].
+On the other hand, the authors prove (see Theorem 3 of loc. cit.) that new scheme can handle its decryption circuit, hence it can be bootstrapped and transformed into a fully homomorphic encryption scheme.
 ==References==

@@ Line 47: / Line 47: @@
 == Making the scheme fully homomorphic ==
-In order to successfully transform <math> \mathcal E </math> into a [[bootstrappable]] scheme, the authors slightly modify the decryption circuit of <math> \mathcal E  </math>.
+In order to successfully transform <math> \mathcal E </math> into a bootstrappable scheme, the authors slightly modify the decryption circuit of <math> \mathcal E  </math>.
 The problem with <math> \mathcal E </math> is that its decryption equation <math> m' \leftarrow (c - \lfloor c/p \rfloor) </math> mod 2, requires Boolean circuits that are deeper than what <math> \mathcal E </math> can handle.

@@ Line 41: / Line 41: @@
 The authors of the scheme describe various optimisations in order to keep the evaluated ciphertexts of the same length as the original "fresh" ciphertexts. However, the size of the evaluated ciphertexts is still very large large for applications.
-To solve this problem, the authors propose a compression of these ciphertexts down to the size of an [[RSA]] modulus. This reduces the communication complexity of the scheme dramatically.
+To solve this problem, the authors propose a compression of these ciphertexts down to the size of an [https://en.wikipedia.org/wiki/RSA_(cryptosystem) RSA] modulus. This reduces the communication complexity of the scheme dramatically.
 The price of this optimisation is that the compressed ciphertexts cannot be further evaluated and hence this compression can be used only on the final output ciphertexts, after all the desired evaluations were completed.

@@ Line 13: / Line 13: @@
 A homomorphic encyption scheme <math> \mathcal E =  </math> is called <b> bootstrappable </b> if for every value of the security parameter, the scheme can handle all the circuits in <math> D_{\lambda} </math>.
-Given such a scheme <math> \mathcal E </math> and a paramater <math>d=d(\lambda) </math>, there is an efficient transformation that outputs the description of another encryption scheme <math> \mathcal E^{(d)}</math> which is [[compact]], has the same <math> Decryption</math> circuit as <math>\mathcal E</math>, and is homomorphic for all circuits of depth up to <math>d</math>.
+Given such a scheme <math> \mathcal E </math> and a paramater <math>d=d(\lambda) </math>, there is an efficient transformation that outputs the description of another encryption scheme <math> \mathcal E^{(d)}</math> which is compact, has the same <math> Decryption</math> circuit as <math>\mathcal E</math>, and is homomorphic for all circuits of depth up to <math>d</math>.
-If we assume that the initial bootstrappable scheme <math>\mathcal E</math> is [[circular secure]] then it can be converted into a single compact fully-homomorphic encryption scheme <math>\mathcal E'</math>.
+If we assume that the initial bootstrappable scheme <math>\mathcal E</math> is circular secure then it can be converted into a single compact fully-homomorphic encryption scheme <math>\mathcal E'</math>.

@@ Line 7: / Line 7: @@
 Using a theorem of Gentry, the authors are able to construct a homomorphic encryption scheme that can handle circuits of any depth from a scheme that is capable of evaluating just a little more than its own decryption circuit.
-Let us first construct a [[somewhat homomorphic encryption scheme]].
+Let us first construct a somewhat homomorphic encryption scheme.
 <b> Definition. </b> Let <math> \mathcal E = (Keygen, Encrypt, Decrypt, Evaluate) </math> be an encryption scheme where <math> Decrypt </math> is implemented by a circuit that depends only on the security parameter. For a given value <math> \lambda </math> of the security parameter, the set of <b> augmented decryption circuits</b> consists of two circuits, both take as input a secret key and two ciphertexts. One circuit decrypts both ciphertexts and adds the resulting plaintext bits modulo <math> 2</math>, the other decrypts both ciphertexts and multiplies the resulting plaintext bits modulo <math>2 </math>. The authors denote this set by <math>D_{\mathcal E}(\lambda) </math>.

← Older revision		Revision as of 09:21, 30 December 2020
Line 1:		Line 1:
−	This is a fully homomorphic encryption relying only on modular arithmetic introduced by van Dijk et al <ref name = vDGHV10> M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In "Advances in Cryptology – EUROCRYPT 2010", 2010.</ref>. The authors first create a somewhat homomorphic scheme~~(see the definition given by~~ Gentry <ref name = G10> C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.</ref>~~) which is [[~~bootstrappable~~]] and then apply Gentry's technique to construct a fully homomorphic scheme~~.	+	This is a fully homomorphic encryption relying only on modular arithmetic introduced by van Dijk et al <ref name = vDGHV10> M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In "Advances in Cryptology – EUROCRYPT 2010", 2010.</ref>. The authors first create a somewhat homomorphic scheme which is bootstrappable and then apply Gentry's technique to construct a fully homomorphic scheme. We refer to Gentry's article <ref name = G10> C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.</ref> for the precise definitions of "somewhat homomorphic" and "bootstrappable" schemme.

	One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the [https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/ approximate gcd problem] over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b>d</b>, find <b>d</b>.		One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the [https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/ approximate gcd problem] over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b>d</b>, find <b>d</b>.

← Older revision		Revision as of 09:19, 30 December 2020
Line 1:		Line 1:
−	This is a fully homomorphic encryption relying only on modular arithmetic introduced by van Dijk et al <ref name = vDGHV10> M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In "Advances in Cryptology – EUROCRYPT 2010", 2010.</ref>. The authors first create ~~an [[~~somewhat homomorphic scheme]] which is [[bootstrappable]] and then apply Gentry's technique to construct a fully homomorphic scheme.	+	This is a fully homomorphic encryption relying only on modular arithmetic introduced by van Dijk et al <ref name = vDGHV10> M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In "Advances in Cryptology – EUROCRYPT 2010", 2010.</ref>. The authors first create a somewhat homomorphic scheme(see the definition given by Gentry <ref name = G10> C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.</ref>) which is [[bootstrappable]] and then apply Gentry's technique to construct a fully homomorphic scheme.

	One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the [https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/ approximate gcd problem] over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b>d</b>, find <b>d</b>.		One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the [https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/ approximate gcd problem] over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b>d</b>, find <b>d</b>.

@@ Line 1: / Line 1: @@
 This is a fully homomorphic encryption relying only on modular arithmetic introduced by van Dijk et al <ref name = vDGHV10> M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In "Advances in Cryptology – EUROCRYPT 2010", 2010.</ref>. The authors first create an [[somewhat homomorphic scheme]] which is [[bootstrappable]] and then apply Gentry's technique to construct a fully homomorphic scheme.
-One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the approximate gcd problem over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b> d </b>, find <b> d </b>.
+One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the [https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/ approximate gcd problem] over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b>d</b>, find <b>d</b>.
 == A somewhat homomorphic encryption scheme ==

← Older revision		Revision as of 08:58, 30 December 2020
Line 65:		Line 65:

	==References==		==References==
−	~~{{Reflist\|30em}}~~

← Older revision		Revision as of 06:45, 25 May 2020
Line 1:		Line 1:
−	This is a fully homomorphic encryption relying only on modular arithmetic introduced in <ref name = vDGHV10> M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In "Advances in Cryptology – EUROCRYPT 2010", 2010.</ref>. The authors first create an [[somewhat homomorphic scheme]] which is [[bootstrappable]] and then apply Gentry's technique to construct a fully homomorphic scheme.	+	This is a fully homomorphic encryption relying only on modular arithmetic introduced by van Dijk et al <ref name = vDGHV10> M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In "Advances in Cryptology – EUROCRYPT 2010", 2010.</ref>. The authors first create an [[somewhat homomorphic scheme]] which is [[bootstrappable]] and then apply Gentry's technique to construct a fully homomorphic scheme.

	One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the approximate gcd problem over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b> d </b>, find <b> d </b>.		One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the approximate gcd problem over the integers, that is, given a list of integers that are near-multiples of an unknown integer <b> d </b>, find <b> d </b>.