Efficient FHE from (Standard) LWE

As anounced in the title, Brakerski and Vaikuntanathan (TODO: cite) introduced a fully homomorphic encryption scheme which is based only on the LWE assumption. They show that the security of the scheme can be reduced to the worst-case hardness of short vector problems on arbitrary latices.

They start by introducing a somewhat homomorphic encryption scheme SH, which is then transformed into a bootstrappable scheme BTS. In doing so, the authors deviate from previously known techniques of “squashing” the decryption algorithm of SH that has been used by Dijk, Gentry, Halevi and Vaikuntanathan in FHE over the integers and instead introduce a new “dimension-modulus reduction” technique, which shortens the ciphertexts and simplifies the decryption circuit of SH. This is all achieved without introducing additional assumptions, such as the hardness of the sparse subset-sum problem.

This scheme has particularly short ciphertexts and for this reasons the authors managed to use it for constructing an efficient single-server private information retrieval (PIR) protocol.

A Somewhat Homomorphic encryption Scheme SH

Let us start by presenting a somewhat homomorphic encryption scheme. Denote by $\lambda$ the security parameter. The scheme is parameterized by a dimension $n\in \mathbb {N}$, a positive integer $m\in \mathbb {N}$ , an odd modulus $q$ (which does not have to be prime) and a noise distribution $\chi$ over $\mathbb {Z} _{q}$. An additional parameter of the scheme $L\in \mathbb {N} </mathisanupperboundonthemaximalmultiplicativedepththattheschemecanhomomorphicallyevaluate.Wearenotgoingtoelaborateontheappropriatechoiceofthesizefortheparameters,butweinvitethecuriousreadertolookatthepaper.However,forbrevity,wementionthatthedimension<math>n$ is polynomial in the security parameter $\lambda$, $m\geq n\log(q)+2\lambda$ is a polynomial in $n$, the modulus is an odd number $q\in [2^{n^{\epsilon }},2\cdot 2^{n^{\epsilon }})$ is sub-exponential in $n$, i.e. $\epsilon$ is a positive constant which is strictly smaller than $1$. The noise distribution $\chi$ produces small samples, of magnitude at most $n$ in $\mathbb {Z} _{\mathfrak {q}}$. The depth bound $L$ is approximately of the size $epsilon\cdot \log(n)$.

Bootstrapping BTS into a Fully Homomorphic encryption scheme

Efficiency of the Scheme