FHE

From certFHE Community KB
Jump to navigation Jump to search

Let us fix a security parameter , 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 .

Intuition

Let be a homomorphic encryption scheme. A desirable property of is the possibility of evaluation arbitrary functions on ciphertexts from in a meaningful way. Clearly the complexity of must depend on the complexity of the function . To measure the latter, we use , the size of a boolean circuit that computes . The algorithm is efficient if there exists a polynomial such that for any function that is represented by a circuit of size , the complexity of is at most .

The circuit representation of breaks down the computation of 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 and the plaintext have the algebraic structure of a ring and that is a ring homomorphism.

Definition. A homomorphic encryption scheme is called leveled if the decryption algorithm is correct for a certain number of ring operations made on .

TODO: Write about the practical reasons for using a leveled scheme.

Definition. A homomorphic encryption scheme is called compact if there exists a polynomial function such that the output length of is at most bits long, regardless of the ring homomorphism or the number of ciphertext inputs , for any tuple of ciphertexts.

A homomorphic encryption scheme as above, but for which we do not require that is polynomial in 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 is called fully homomorphic.

In one of his seminal papers, Gentry showed that under a "circular security" assumption, a leveled homomorphic encryption scheme which is capable of homomorphically evaluating its can be transformed into a fully homomorphic encryption scheme . Gentry called the process of transforming bootstrapping .

Examples

References