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