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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m \in \mathbb N } , an odd modulus $q$ (which does not have to be prime) and a noise distribution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \chi } over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb Z_q } . An additional parameter of the scheme Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L \in \mathbb N } is an upper bound on the maximal multiplicative depth that the scheme can homomorphically evaluate.

We are not going to elaborate on the appropriate choice of the size for the parameters, but we invite the curious reader to look at the paper. However, for brevity, we mention that the dimension Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} is polynomial in the security parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lambda } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m \geq n \log(q) + 2 \lambda } is a polynomial in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n } , the modulus is an odd number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q \in [ 2^{n^{\epsilon}}, 2 \cdot 2^{n^{\epsilon}}) } is sub-exponential in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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)$.

SH.Keygen: sample $L+1$ vectors $s_{0},\dots ,s_{L}$ uniformly from $\mathbb {Z} _{q}^{n}$ and compute, for all $l\in [L]$, $0\leq I\leq j\leq n$ and $\tau \in \{0,\dots ,\lfloor \log {q}\rfloor \}$, the value

$\psi _{l,i,j,\tau }:=\left(a_{l,i,j,\tau },b_{l,i,j,\tau }:=\langle a_{l,i,j,\tau },s_{l}\rangle +2\cdot e_{l,I,j,\tau }+2^{\tau }\cdot s_{l-1}\cdot s_{l-1}[j]\right)\in \mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}$

SH.Keygen: sample $L+1$ vectors $s_{0},\dots ,s_{L}$ uniformly from $\mathbb {Z} _{q}^{n}$ and compute, for all $l\in [L]$, $0\leq I\leq j\leq n$ and $\tau \in \{0,\dots ,\lfloor \log {q}\rfloor \}$, the value

$\psi _{l,i,j,\tau }:=\left(a_{l,I,j,\tau },b_{l,I,j,\tau }:=\langle a_{l,I,j,\tau },s_{l}\rangle +2\cdot e_{l,I,j,\tau }+2^{\tau }\cdot s_{l-1}\cdot s_{l-1}[j]\right)\in \mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}$

Where $a_{l,I,j,\tau }$ and $e_{l,I,j,\tau }$ are chosen uniformly at from $\mathbb {Z} _{q}^{n}$ and from the distribution $\chi$, respectively.

Let $\Psi :=\{\psi _{l,i,j,\tau }\}_{l,I,j,\tau }$ be the set of all these values. Notice that these seem like encryptions of $2^{\tau }\cdot s_{l-1}[i]\cdot s_{l-1}[j]$ (mod $q$), except these “ciphertexts” can’t be decrypted since the underlying message $2^{\tau }\cdot s_{l-1}[i]\cdot s_{l-1}[j]$ is not a single bit value.

The key generation might seem rather strange now, but publishing these “encryptions” of the quadratic terms in the secret keys $s_{l}$ is very important and we will explain this when we describe homomorphic multiplication.

The key-generation algorithm proceeds to choose a uniformly random matrix $A$ from $\mathbb {Z} _{q}^{m\times n}$ and an $m$-dimensional vector $e$ from the distribution $\chi ^{m}$. Set $b:=As_{0}+2e$.

The algorithm outputs the secret key $sk=s_{L}$, the evaluation key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle evk := \Psi} and the public key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle pk := (A,b) } .

Encryption(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu} ): We recall that the public key is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle pk = (A,b) } . To encrypt a message Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu \in GF(2) } , we sample a random vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle r \in \{0,1 \}^m } and set:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v:= A^{T} \cdot r } and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w := b^{T} \cdot r + \mu } .

The output ciphertext contains the pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (v,w) \in \mathbb Z_q^{n} \times \mathbb Z_{q} } , together with a "level tag" which is used during homomorphic evaluation and indicates the multiplicative depth of the ciphertexts. Fresh ciphertexts, i.e. ciphertexts that are obtained straight from the encryption of messages and that did not suffer any homomorphic evaluation, will have this tag level zero. The encryption algorithm outputs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c:= ((v,w),0) } .

Homomorphic evaluation: We now present the algorithm Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle SH.Eval_{evk}(f,c_1, \dots, c_t) } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f: \{0,1 \}^{t} \to \{0,1 \} } . We require that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f } is represented by a binary arithmetic circuit with 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle +} ' gates of arbitrary fan-in and 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \times } ' gates with fan-in equal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2} . Furthermore, it is required that every circuit is layered, namely that it is composed of layers containing having either all 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle +} ' gates or all 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \times } ' gates. Every binary circuit can be represented in this way. It is also required that the multiplicative depth of the circuit $f$ is exactly $L$.

The algorithm homomorphically evaluates the circuit $f$ gate by gate. We present how to perform homomorphic addition for arbitrarily many ciphertexts and homomorphic multiplication for two ciphertexts. Combining the two, any circuit Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f } can be evaluated.

Bootstrapping BTS into a Fully Homomorphic encryption scheme

Efficiency of the Scheme