FHE - Revision history

Georgeg at 15:11, 2 June 2025

2025-06-02T15:11:34Z

Georgeg at 15:10, 2 June 2025

2025-06-02T15:10:48Z

Gturcas: /* Examples */

2020-12-30T08:56:49Z

Examples

Gturcas: /* Examples */

2020-12-30T08:25:14Z

Examples

Gturcas: /* Examples */

2020-12-30T08:23:31Z

Examples

Gturcas: /* Examples */

2020-12-30T08:21:19Z

Examples

Gturcas: /* Examples */

2020-12-30T08:19:53Z

Examples

Gturcas: /* Intuition */

2020-12-30T08:10:26Z

Intuition

Gturcas: /* Examples */

2020-03-17T12:40:35Z

Examples

Gturcas: /* Examples */

2020-03-11T09:45:48Z

Examples

← Older revision		Revision as of 15:11, 2 June 2025
Line 57:		Line 57:
	In Alice's jewellery store analogy presented on the [[Homomorphic encryption]] page, the bootstrapping process is analogous to Alice giving a worker a glovebox #1, containing the raw materials and many additional gloveboxes. In box #2, Alice placed the key to box #1, box #3 contains the key to box number #2 and so on. To assemble a complicated piece, the worker manipulates the materials in box #1 until the gloves on the box become impractical. Then, he places box #1 inside box #2. Using the keys inside, he opens box #1 with the key, extracts the partially assembled piece and continues to assembly until the gloves of box #2 become impractical. When the worker finally finishes the assembly inside box #n, he hands the box to Alice. This process works as long as the worker can open box #i within box #(i+1) and still do a little bit of work on the pieces inside before the gloves of the box #(i+1) stiffen. As long as Alice has enough resources (i.e. gloveboxes and time for the manufacturing process) then her jewellery store can assemble any piece, no matter how complicated it is.		In Alice's jewellery store analogy presented on the [[Homomorphic encryption]] page, the bootstrapping process is analogous to Alice giving a worker a glovebox #1, containing the raw materials and many additional gloveboxes. In box #2, Alice placed the key to box #1, box #3 contains the key to box number #2 and so on. To assemble a complicated piece, the worker manipulates the materials in box #1 until the gloves on the box become impractical. Then, he places box #1 inside box #2. Using the keys inside, he opens box #1 with the key, extracts the partially assembled piece and continues to assembly until the gloves of box #2 become impractical. When the worker finally finishes the assembly inside box #n, he hands the box to Alice. This process works as long as the worker can open box #i within box #(i+1) and still do a little bit of work on the pieces inside before the gloves of the box #(i+1) stiffen. As long as Alice has enough resources (i.e. gloveboxes and time for the manufacturing process) then her jewellery store can assemble any piece, no matter how complicated it is.

−
−	a

	== References ==		== References ==

← Older revision		Revision as of 15:10, 2 June 2025
Line 56:		Line 56:

	In Alice's jewellery store analogy presented on the [[Homomorphic encryption]] page, the bootstrapping process is analogous to Alice giving a worker a glovebox #1, containing the raw materials and many additional gloveboxes. In box #2, Alice placed the key to box #1, box #3 contains the key to box number #2 and so on. To assemble a complicated piece, the worker manipulates the materials in box #1 until the gloves on the box become impractical. Then, he places box #1 inside box #2. Using the keys inside, he opens box #1 with the key, extracts the partially assembled piece and continues to assembly until the gloves of box #2 become impractical. When the worker finally finishes the assembly inside box #n, he hands the box to Alice. This process works as long as the worker can open box #i within box #(i+1) and still do a little bit of work on the pieces inside before the gloves of the box #(i+1) stiffen. As long as Alice has enough resources (i.e. gloveboxes and time for the manufacturing process) then her jewellery store can assemble any piece, no matter how complicated it is.		In Alice's jewellery store analogy presented on the [[Homomorphic encryption]] page, the bootstrapping process is analogous to Alice giving a worker a glovebox #1, containing the raw materials and many additional gloveboxes. In box #2, Alice placed the key to box #1, box #3 contains the key to box number #2 and so on. To assemble a complicated piece, the worker manipulates the materials in box #1 until the gloves on the box become impractical. Then, he places box #1 inside box #2. Using the keys inside, he opens box #1 with the key, extracts the partially assembled piece and continues to assembly until the gloves of box #2 become impractical. When the worker finally finishes the assembly inside box #n, he hands the box to Alice. This process works as long as the worker can open box #i within box #(i+1) and still do a little bit of work on the pieces inside before the gloves of the box #(i+1) stiffen. As long as Alice has enough resources (i.e. gloveboxes and time for the manufacturing process) then her jewellery store can assemble any piece, no matter how complicated it is.
		+
		+
		+	a

	== References ==		== References ==

@@ Line 53: / Line 53: @@
 Gentry <ref name = G10> C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.</ref> proved that if the scheme <math> \mathcal E </math> has the self-referential property of being able to homomorphically evaluate its own decryption function, then one can use <math> \mathcal E </math> to construct a fully homomorphic encryption <math>\mathcal E^{\dagger} </math>. If this is the case, the term <i>bootstrapable</i> was coined by Gentry for the scheme <math> \mathcal E </math>.
-The simple scheme presented above is not bootstrapable, but it can be modified slightly to a new scheme <math>  \mathcal E'</math> such that <math> \mathcal E' </math> can handle essentially the same functions as <math> \mathcal E  </math>, but whose decryption circuit is simpler. This new scheme <math> \mathcal E' </math> is now bootstrappable. In Gentry's construction of <math>\mathcal E' </math> from <math> \mathcal E  </math>, he had to add another security assumption to the scheme <math> \mathcal E'  </math>, namely the hardness of the [[sparse subset sum problem]].
+The simple scheme presented above is not bootstrapable, but it can be modified slightly to a new scheme <math>  \mathcal E'</math> such that <math> \mathcal E' </math> can handle essentially the same functions as <math> \mathcal E  </math>, but whose decryption circuit is simpler. This new scheme <math> \mathcal E' </math> is now bootstrappable. In Gentry's construction of <math>\mathcal E' </math> from <math> \mathcal E  </math>, he had to add another security assumption to the scheme <math> \mathcal E'  </math>, namely the hardness of the [https://eprint.iacr.org/2011/567.pdf sparse subset sum problem].
 In Alice's jewellery store analogy presented on the [[Homomorphic encryption]] page, the bootstrapping process is analogous to Alice giving a worker a glovebox #1, containing the raw materials and many additional gloveboxes. In box #2, Alice placed the key to box #1, box #3 contains the key to box number #2 and so on. To assemble a complicated piece, the worker manipulates the materials in box #1 until the gloves on the box become impractical. Then, he places box #1 inside box #2. Using the keys inside, he opens box #1 with the key, extracts the partially assembled piece and continues to assembly until the gloves of box #2 become impractical. When the worker finally finishes the assembly inside box #n, he hands the box to Alice. This process works as long as the worker can open box #i within box #(i+1) and still do a little bit of work on the pieces inside before the gloves of the box #(i+1) stiffen. As long as Alice has enough resources (i.e. gloveboxes and time for the manufacturing process)  then her jewellery store can assemble any piece, no matter how complicated it is.
 == References ==

@@ Line 51: / Line 51: @@
 The semantic security of the scheme can be reduced to an [https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/ approximate gcd problem]]. That is, it was proved that an attacker cannot efficiently break the semantic security of <math> \mathcal E </math> unless <b>the approximate gcd problem</b> is easy.
-Gentry proved that if the scheme <math> \mathcal E </math> has the self-referential property of being able to homomorphically evaluate its own decryption function, then one can use <math> \mathcal E </math> to construct a fully homomorphic encryption <math>\mathcal E^{\dagger} </math>. If this is the case, the term <i>bootstrapable</i> was coined by Gentry for the scheme <math> \mathcal E </math>.
+Gentry <ref name = G10> C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.</ref> proved that if the scheme <math> \mathcal E </math> has the self-referential property of being able to homomorphically evaluate its own decryption function, then one can use <math> \mathcal E </math> to construct a fully homomorphic encryption <math>\mathcal E^{\dagger} </math>. If this is the case, the term <i>bootstrapable</i> was coined by Gentry for the scheme <math> \mathcal E </math>.
 The simple scheme presented above is not bootstrapable, but it can be modified slightly to a new scheme <math>  \mathcal E'</math> such that <math> \mathcal E' </math> can handle essentially the same functions as <math> \mathcal E  </math>, but whose decryption circuit is simpler. This new scheme <math> \mathcal E' </math> is now bootstrappable. In Gentry's construction of <math>\mathcal E' </math> from <math> \mathcal E  </math>, he had to add another security assumption to the scheme <math> \mathcal E'  </math>, namely the hardness of the [[sparse subset sum problem]].

@@ Line 37: / Line 37: @@
 <math>Decypt(p,c):</math> Ouput (c mod p) mod 2, where (c mod p) is the unique integer <math>c' \in (-p/2,p/2) </math> such that <math>p </math> divides <math>c-c' </math>.
-Remark that ciphertexts coming out of <math>Encrypt </math> are <i> near-multiples</i> of <math> p </math>. The distance from a ciphertext <math>c </math> to the nearest multiple of <math> p</math> is commonly called <b> noise </b>. The decryption algorithm is correct because the noise <math>m' </math> has the same parity as the message (in plaintext) <math> m </math>.
+Remark that ciphertexts coming out of <math>Encrypt </math> are <i> near-multiples</i> of <math> p </math>. The distance from a ciphertext <math>c </math> to the nearest multiple of <math> p</math> is commonly called <b> noise</b>. The decryption algorithm is correct because the noise <math>m' </math> has the same parity as the message (in plaintext) <math> m </math>.
 This scheme is homomorphic since by simply adding, subtracting or multiplying the ciphertexts as integers we can add, subtract or multiply modulo <math> 2</math> the underlying plaintext messages. However, such operations increase the noise on the ciphertexts. Complications arise, i.e. <math> Decrypt </math> might not work correctly, when the noise <math>m'</math> is too large when compared to <math> p</math>. This is a recurrent issue in all homomorphic encription schemes proposed so far in the literature.
@@ Line 49: / Line 49: @@
 If we want to homomorphically evaluate a function <math>f </math> whose circuit representation has many additions, subtractions and multiplication operation, we have to be careful that the magnitude of the noise does not surpass <math>q/2 </math>. This is why the scheme we just presented is not fully homomorphic, but only leveled. In particular, the encryption scheme <math> \mathcal E </math> can homomorphically evaluate polynomials of fairly low degree, where not a lot of multiplications are involved.
-The semantic security of the scheme can be reduced to an [[approximate gcd problem]]. That is, it was proved that an attacker cannot efficiently break the semantic security of <math> \mathcal E </math> unless the approximate gcd problem is easy.
+The semantic security of the scheme can be reduced to an [https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/ approximate gcd problem]]. That is, it was proved that an attacker cannot efficiently break the semantic security of <math> \mathcal E </math> unless <b>the approximate gcd problem</b> is easy.
 Gentry proved that if the scheme <math> \mathcal E </math> has the self-referential property of being able to homomorphically evaluate its own decryption function, then one can use <math> \mathcal E </math> to construct a fully homomorphic encryption <math>\mathcal E^{\dagger} </math>. If this is the case, the term <i>bootstrapable</i> was coined by Gentry for the scheme <math> \mathcal E </math>.

@@ Line 27: / Line 27: @@
 == Examples ==
-We start by presenting an encryption scheme <math> \mathcal E </math> proposed by van Dijk, Gentry and Halevi (<b>TODO:cite</b>). The encryption scheme <math> \mathcal E </math> goes as follows.
+We start by presenting an encryption scheme <math> \mathcal E </math> proposed by van Dijk, Gentry and Halevi <ref name = vanDijk> van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully hohomomorphic encryption over the integers, In EUROCRYPT 2010, pp. 24 - 43 </ref>. The encryption scheme <math> \mathcal E </math> goes as follows.
 We fix the security parameter <math>\lambda</math> and set <math> N=\lambda, P= \lambda^2</math> and <math>Q= \lambda^5 </math>.

@@ Line 3: / Line 3: @@
 == Intuition ==
-Let  <math> \mathcal E = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt, Evaluate) </math> be a [[Homomorphic encryption|homomorphic encryption scheme]]. A desirable property of <math> \mathcal E </math> is the possibility of evaluation arbitrary functions on ciphertexts from <math> \mathcal C </math> in a meaningful way. Clearly the complexity of  <math>Evaluate(f,c)</math> must depend on the complexity of the function <math>f </math>. To measure the latter, we use <math> S_f </math>, the size of a [[boolean circuit]] that computes <math>f </math>. The algorithm <math> Evaluate </math> is efficient if there exists a polynomial <math> g </math> such that for any function <math> f </math> that is represented by a circuit of size <math> S_f </math>, the complexity of <math> Evaluate(f,c_1, \dots, c_t, pk) </math> is at most <math>S_f \cdot g(\lambda) </math>.
+Let  <math> \mathcal E = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt, Evaluate) </math> be a [[Homomorphic encryption|homomorphic encryption scheme]]. A desirable property of <math> \mathcal E </math> is the possibility of evaluation arbitrary functions on ciphertexts from <math> \mathcal C </math> in a meaningful way. Clearly the complexity of  <math>Evaluate(f,c)</math> must depend on the complexity of the function <math>f </math>. To measure the latter, we use <math> S_f </math>, the size of a [https://en.wikipedia.org/wiki/Boolean_circuit boolean circuit] that computes <math>f </math>. The algorithm <math> Evaluate </math> is efficient if there exists a polynomial <math> g </math> such that for any function <math> f </math> that is represented by a circuit of size <math> S_f </math>, the complexity of <math> Evaluate(f,c_1, \dots, c_t, pk) </math> is at most <math>S_f \cdot g(\lambda) </math>.
 The circuit representation of <math>f </math> breaks down the computation of <math>f </math> into AND, OR, and NOT gates. To evaluate these it is enough to be able to add, subtract and multiply. Therefore, to obtain a fully homomorphic encryption scheme, all we need is a scheme that supports arbitrary additions, subtractions and multiplications on the ciphertexts, so as it does on their underlying encrypted messages.

← Older revision		Revision as of 09:45, 11 March 2020
Line 26:		Line 26:

	== Examples ==		== Examples ==
		+
		+	We start by presenting an encryption scheme <math> \mathcal E </math> proposed by van Dijk, Gentry and Halevi (<b>TODO:cite</b>). The encryption scheme <math> \mathcal E </math> goes as follows.
		+
		+	We fix the security parameter <math>\lambda</math> and set <math> N=\lambda, P= \lambda^2</math> and <math>Q= \lambda^5 </math>.
		+
		+	<p><math>Keygen(\lambda):</math> Output a random odd <math>P </math>-bit integer <math> p</math>. </p>
		+
		+	<p><math>Encrypt(p,m):</math> To encrypt a bit <math> m \in \{0,1 \} </math>, let <math> m' </math> be a random <math>N </math>-bit integer such that <math> m'=m \pmod 2</math>. Output the ciphertext <math>c \leftarrow m'+pq </math>, where <math>q </math> is a random <math>Q</math>-bit integer number.</p>
		+
		+	<math>Decypt(p,c):</math> Ouput (c mod p) mod 2, where (c mod p) is the unique integer <math>c' \in (-p/2,p/2) </math> such that <math>p </math> divides <math>c-c' </math>.
		+
		+	Remark that ciphertexts from outputed by <math>Encrypt </math> are <i> near-multiples</i> of <math> p </math>. The distance from a ciphertext <math>c </math> to the nearest multiple of <math> p</math> is commonly called [[ noise ]]. The decryption algorithm is correct because the noise <math>m' </math> has the same parity as the message (in plaintext) <math> m </math>.
		+
		+	This scheme is homomorphic since by simply adding, subtracting or multiplying the ciphertexts as integers we can add, subtract or multiply modulo <math> 2</math> the underlying plaintext messages. However, such operations increase the noise on the ciphertexts. Complications arise, i.e. <math> Decrypt </math> might not work correctly, when the noise <math>m'</math> is too large when compared to <math> p</math>. This is a recurrent issue in all homomorphic encription schemes proposed so far in the literature.
		+
		+	Let us emphasize this on the multiplication operation <math> Mult </math>. Let <math>c_1,c_2 </math> be two ciphertexts with associated noise <math>m_1' </math> and <math>m_2' </math> respectively. We have that
		+
		+	<math> c \leftarrow Mult(c_1,c_2) = m_1' \cdot m_2' + p \cdot q' </math> for some integer <math>q' </math>. As long as <math> \|m_1' \cdot m_2'\| < p/2</math>, we have that
		+
		+	(<math>c </math> mod <math> p </math>) = <math>m_1' \cdot m_2' </math> as it should be for correct decryption.
		+
		+	If we want to homomorphically evaluate a function <math>f </math> whose circuit representation has many additions, subtractions and multiplication operation, we have to be careful that the magnitude of the noise does not surpass <math>q/2 </math>. This is why the scheme we just presented is not fully homomorphic, but only leveled.
		+
		+	The semantic security of the scheme can be reduced to an [[approximate gcd problem]]. That is, it was proved that an attacker cannot efficiently break the semantic security of <math> \mathcal E </math> unless the approximate gcd problem is easy.
		+
		+	<b>TODO: Bootstrappable encryption </b>

	== References ==		== References ==