Fully homomorphic encryption allows evaluation of arbitrary functions on encrypted data. In an FHE scheme, the ciphertexts are "noisy". This noise is necessary for security reasons, but can interfere with decryption if it grows too large, and the noise increases with each homomorphic operation. This means that there is a limited number of homomorphic operations which can be performed, and we then have what is called a Somewhat Homomorphic Encryption scheme (SHE). In this context, bootstrapping is used as a noise management technique to turn an SHE scheme into an FHE one. This is done by homomorphically decrypting the ciphertext before the noise grows too large, in order to reduce the said noise so that more homomorphic operations can be performed. It is implemented by augmenting the public key with an encryption of the secret key (under the public key) $Enc_{pk}(sk)$, then by a homomorphic decryption which results in a "fresh" ciphertext. Note that for this to work, circular security is assumed.
There are three generations of homomorphic schemes, the first being the scheme proposed by Gentry. Then, there are the packing scheme (which is faster asymptotically) and the small noise one. So far as we know, slow noise growth is incompatible with the ciphertext packing technique. This paper implements the ciphertext packing scheme, described by [BGV12].
Quick overview of the BGV scheme
The parameters of the scheme are integers $m$, $p$ and $q$. The plaintext space is integers in the group $R=\mathbb{Z}[x]/ (\Phi_{m}, p)$, where $\Phi_{m}$ is the $m^{th}$ cyclotomic polynomial. Ciphertexts and secret keys are vectors in $R$, and we require $q$ to be much larger than $p$. A ciphertext $c$ encrypts a plaintext $m$ with respect to a secret key $sk$ if it holds that $m=[[ \langle c, sk \rangle ]_{q}]_{p}$, where $[.]_{p}$ denotes modular reduction in an interval centered around zero (rather than in ${0, 1, ..., p-1}$) and $\langle ., . \rangle$ stands for inner product. The homomorphic operations are done over $R$. The scheme is also parameterised by a sequence of gradually decreasing moduli $q_{i}$, where we perform a modulus switch in order to reduce noise levels (bootstrapping is then performed upon reaching the last modulus).
Work presented
Bootstrapping for HElib which was presented today by Shai Halevi follows the method of [GHS12], and generalises it. We take $q$ such that $q=2^{e}+1$ for some $e$ not too small. Recryption is done by storing $Enc_{pk}(sk)$ with respect to a larger plaintext space where $p'=2^{e+1}$. We then compute $u=[ \langle sk, c \rangle]_{2^{e}+1}$, and extract the plaintext as the xor of the least and most significant bits of $u$. $u$ is very easily and quickly computed, and it is the extracting of the most and least significant bits that is the most expensive part of the recryption procedure. It is done in three steps, the first of which is a linear transformation which outputs ciphertexts that have the coefficients of $u$ in the plaintext slots. Then a bit extraction operation is performed and an inverse linear transformation, which recovers a ciphertext encrypting the initial plaintext.
The linear transformations are achieved through imposing a hypercube structure to the group $R_{p}=\mathbb{Z}[x]/(\Phi_{m}, p)$ with one dimension per factor of $m$, where we recall that $p$ can be any prime power. The inverse linear transformation is implemented as a sequence of multi-point polynomial evaluations operations, one per each dimension of the hypercube. It can happen that some of these linear transformations are linear over the base field, but not over the extension. To avoid that, various constraints are applied to the parameters.
Results
This paper generalises [GHS12] and [AP13] by extending their methods from the prime $p=2$ to any prime power $p^{r}$. The implementation presented supports recryption of packed ciphertexts, i.e. recryption of ciphertexts encrypting vectors of plaintexts. The procedure also has low enough depth so as to allow for a significant processing in between recryptions while remaining efficient. The ePrint version can be found here.
References:
[GHS12]: http://eprint.iacr.org/2011/566.pdf
[AP13]: http://www.cc.gatech.edu/~cpeikert/pubs/simpleboot.pdf
No comments:
Post a Comment