Difference between revisions of "FHE over the Integers"
| Line 8: | Line 8: | ||
<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>. | <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>. | ||
| + | |||
| + | 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>. | ||
| + | |||
| + | 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>. | ||
Revision as of 16:32, 24 March 2020
This is a fully homomorphic encryption relying only on modular arithmetic. 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 d , find d .
The bootstrappable encryption scheme
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.
Definition. Let be an encryption scheme where is implemented by a circuit that depends only on the security parameter. For a given value of the security parameter, the set of augmented decryption circuits 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 , the other decrypts both ciphertexts and multiplies the resulting plaintext bits modulo . The authors denote this set by .
A homomorphic encyption scheme is called bootstrappable if for every value of the security parameter, the scheme can handle all the circuits in .
Given such a scheme and a paramater , there is an efficient transformation that outputs the description of another encryption scheme which is compact, has the same circuit as , and is homomorphic for all circuits of depth up to .
If we assume that the initial bootstrappable scheme is circular secure then it can be converted into a single compact fully-homomorphic encryption scheme .
