Difference between revisions of "FHE"
| 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>. | <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 | + | 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 [[ 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. | 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 47: | Line 47: | ||
(<math>c </math> mod <math> p </math>) = <math>m_1' \cdot m_2' </math> as it should be for correct decryption. | (<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. | + | 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 [[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. | ||
| − | < | + | 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>. |
| + | |||
| + | 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]]. | ||
| + | |||
| + | 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 == | == References == | ||
Revision as of 14:40, 17 March 2020
Let us fix a security parameter 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 \lambda } , a variable that measures the input size of the computational problem. In the case of the encryption scheme, both the requirements of the cryptographic algorithms as well as the security of the scheme are expressed in terms 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 \lambda } .
Contents
Intuition
Let be a homomorphic encryption scheme. A desirable property of is the possibility of evaluation arbitrary functions on ciphertexts 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 \mathcal C } in a meaningful way. Clearly the complexity 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 Evaluate(f,c)} must depend on the complexity of 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 } . To measure the latter, we use 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_f } , the size of a boolean circuit that 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 f } . The algorithm 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 Evaluate } is efficient if there exists a polynomial 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 g } such that for any 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 } that is represented by a circuit of size 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_f } , the complexity 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 Evaluate(f,c_1, \dots, c_t, pk) } is at most 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_f \cdot g(\lambda) } .
The circuit representation 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 f } breaks down the computation 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 f } 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.
Definitions
L Assume that 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 \mathcal C } and the plaintext 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 \mathcal P } have the algebraic structure of a ring and 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 Decrypt : \mathcal C \to \mathcal P} is a ring homomorphism.
Definition. A homomorphic encryption scheme 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 \mathcal E = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt, Evaluate) } is called leveled if the decryption algorithm is correct for a certain number of ring operations made 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 \mathcal C } .
TODO: Write about the practical reasons for using a leveled scheme.
Definition. A homomorphic encryption scheme 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 \mathcal E} is called compact if there exists a polynomial 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 s=s(\lambda) } such that the output length 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 Eval(f,c,pk)} is at most 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(\lambda) } bits long, regardless of the ring homomorphism 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 : \mathcal C^{t} \to \mathcal C } or the number of ciphertext inputs 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} , for any tuple 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 = (c_1, \dots, c_t) \in \mathcal C^{t}} of ciphertexts.
A homomorphic encryption scheme as above, but for which we do not require 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 s(\lambda) } is polynomial in 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 \lambda } is called bounded .
Definition. A scheme that is compact and for which the decryption algorithm is correct for any number of ring operations made 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 \mathcal C } is called fully homomorphic.
In one of his seminal papers, Gentry showed that under a "circular security" assumption, a leveled homomorphic encryption scheme 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 \mathcal E } which is capable of homomorphically evaluating its 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 Decryption} can be transformed into a fully homomorphic encryption scheme 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 \mathcal E' } . Gentry called the process of transforming 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 \mathcal E \to \mathcal E' } bootstrapping .
Examples
We start by presenting an encryption scheme 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 \mathcal E } proposed by van Dijk, Gentry and Halevi (TODO:cite). The encryption scheme 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 \mathcal E } goes as follows.
We fix the security parameter 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 \lambda} and set 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=\lambda, P= \lambda^2} 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= \lambda^5 } .
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 Keygen(\lambda):} Output a random odd 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 } -bit integer 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} .
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 Encrypt(p,m):} To encrypt a bit 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 \in \{0,1 \} } , 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 m' } be a random 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 } -bit integer 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 m'=m \pmod 2} . Output 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 \leftarrow m'+pq } , 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 q } is a random -bit integer number.
Ouput (c mod p) mod 2, where (c mod p) is the unique integer such that divides .
Remark that ciphertexts coming out 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 Encrypt } are near-multiples 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 p } . The distance from a 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 } to the nearest multiple 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 p} is commonly called noise . The decryption algorithm is correct because the 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 m' } has the same parity as the message (in plaintext) 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 } .
This scheme is homomorphic since by simply adding, subtracting or multiplying the ciphertexts as integers we can add, subtract or multiply modulo 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 2} the underlying plaintext messages. However, such operations increase the noise on the ciphertexts. Complications arise, i.e. 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 Decrypt } might not work correctly, when the 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 m'} is too large when compared 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 p} . This is a recurrent issue in all homomorphic encription schemes proposed so far in the literature.
Let us emphasize this on the multiplication operation 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 } . 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 c_1,c_2 } be two ciphertexts with associated 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 m_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 m_2' } respectively. We have 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 \leftarrow Mult(c_1,c_2) = m_1' \cdot m_2' + p \cdot q' } for some integer 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' } . As long as 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_1' \cdot m_2'| < p/2} , we have 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 }
mod 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 }
) = 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_1' \cdot m_2' }
as it should be for correct decryption.
If we want to homomorphically evaluate a 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 } whose circuit representation has many additions, subtractions and multiplication operation, we have to be careful that the magnitude of the noise does not surpass 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/2 } . This is why the scheme we just presented is not fully homomorphic, but only leveled. In particular, the encryption scheme 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 \mathcal E } 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 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 \mathcal E } unless the approximate gcd problem is easy.
Gentry proved that if the scheme 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 \mathcal E } has the self-referential property of being able to homomorphically evaluate its own decryption function, then one can use 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 \mathcal E } to construct a fully homomorphic encryption 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 \mathcal E^{\dagger} } . If this is the case, the term bootstrapable was coined by Gentry for the scheme 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 \mathcal E } .
The simple scheme presented above is not bootstrapable, but it can be modified slightly to a new scheme 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 \mathcal E'} 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 \mathcal E' } can handle essentially the same functions as 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 \mathcal E } , but whose decryption circuit is simpler. This new scheme 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 \mathcal E' } is now bootstrappable. In Gentry's construction 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 \mathcal E' } 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 \mathcal E } , he had to add another security assumption to the scheme 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 \mathcal E' } , namely the hardness of the 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.
