BGV

In 2011, Brakerski, Gentry and Vaikuntanathan (BGV) published the paper in which they introduce a new (leveled) fully homomorphic encryption (FHE) that improves performance and bases security on weaker assumptions than schemes from the previous generation.

A central conceptual contribution of this work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), without Gentry’s bootstrapping procedure.

Until recently, the BGV scheme was considered to be the most efficient homomorphic encryption scheme when performing the same operations on multiple ciphertexts at once.

Modulus switching

@TODO

New noise management technique

@TODO

Leveled Fully Homomorphic Encryption

Most of the work done by the will focus on the construction of a leveled fully homomorphic scheme, in the sense that the parameters of the scheme depend (polynomially) on the depth of the circuits that the scheme is capable of evaluating.

Definition. We say that a family of homomorphic encryption schemes $\{{\mathcal {E}}^{(L)}:L\in \mathbb {Z} ^{+}\}$ is leveled fully homomorphic if, for all $L\in \mathbb {Z} ^{+}$, they all use the same decryption circuit, ${\mathcal {E}}^{(L)}$ compactly evaluates all circuits of depth at most $L$ (that use some specified complete set of gates), and the computational complexity of ${\mathcal {E}}^{(L)}$'s algorithms is polynomial (a fixed polynomial for all $L$) in the security parameter $L$, and the size of the circuit (in the case of the evaluation algorithm).

The construction: FHE without bootstrapping

The authors base the security of their scheme on the hardness of Ring-Learning with errors problems, a generalisation of the classical LWE problem.

Let $\lambda$ be a security parameter, representing $2^{\lambda }$ security against known attacks.

Let $R$ be a ring. For any integer $q$, we write $R_{q}$ for the quotient $R/qR$.

Let $q=q(\lambda )$ be an odd modulus and $\chi =\chi (\lambda )$ a ``noise" distribution over $R$. Let $N=N(\lambda )$ be an additional parameter of the system which is larger than $3\cdot \log {q}$.

Let us assume that the plaintext is $R_{2}=R/2R$.

• E.Setup($1^{\lambda },1^{\mu }$): Choose a $\mu$-bit modulus $q$ and choose the other parameters $d=d(\lambda ,\mu )$, and $N=\lceil 3\log q\rceil$, $\chi (\lambda ,\mu )$ appropriately to ensure that the scheme is based on a Ring-LWE instance that achieves $2^{\lambda }$ security against known attacks. Let $R=\mathbb {Z} [X]/(x^{d}+1)$ and let params = $(q,d,N,\chi )$.

• E.SecretKetGen(params): Draw $s'\leftarrow \chi$. Set $sk=s\leftarrow (1,s')\in R_{q}^{2}$.

• E.PublicKeyGen(params, sk): Recall that the secret key is $sk=s=(1,s')$. This algorithm generates a (column) vector $A'\leftarrow R_{q}^{N}$, uniformly and a vector $e\leftarrow \chi ^{N}$. The algorithm computes

$b=A's'+2e$. Then, set $A$ to be the $N\times 2$ matrix obtained by setting $b$ on the first column followed by the entries of $-A'$. We remark that $A\cdot s=2e$. The algorithm outputs the public key $pk=A$.

• E.Enc(params, pk,m): To encrypt a message $m\in R_{2}=R/2R$, set $m\leftarrow (m,0)\in R_{q}^{2}$, sample $r\leftarrow R_{2}^{N}$ uniformly and output the ciphertext $c\leftarrow m+A^{T}\cdot r\in R_{q}^{2}$.

• E.Dec(params, sk, c): Output $m\leftarrow [[<c,s>]_{q}]_{2}$. Where $[\cdot ]_{q}$ denotes reduction into the range $(-q/2,q/2]$.

Correctness is easy to verify, whereas we refer to the paper for details upon security.

Key switching (Dimension reduction)

Recall that in the above scheme, the decryption equation for a ciphertext $c$ that encrypts a message $m$ under the secret key $s$ can be written as 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 = E.Dec(params, s,c) = [[L_{c}(s)]_q]_2,} 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 L_c } is a linear operator which depends on 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 } . To be precise, the latter is just the inner product 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_c(s) = <c,s> } between two vectors 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 R_q^2} .

To understand the key switching procedures, we have to (at least briefly) describe the following subroutines first:

• BitDecomp(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 x \in R_q,q } ): decomposes 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 x } into its bit representation, namely 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 x= \sum_{j=0}^{\lfloor \log q \rfloor} 2^j u_j,} where all of the 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 u_j \in R_2 } . The procedure outputs the 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 (u_0, u_1, \dots, u_{\lfloor \log q \rfloor}) \in R_2^{\lceil \log q \rceil} }

• Powersof2(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 x \in R_q,q} ): outputs the 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 (x, 2 \cdot x, \dots, 2^{\lfloor \log q \rfloor} \cdot x) \in R_q^{\lceil \log q \rceil}.}