Fully Homomorphic Encryption without Modulus Switching

This scheme proposed by Brakerski has a number of advantages over previous candidates such as BGV. In particular, it uses the same modulus throughout the evaluation process, so there's no need for modulus switching. Security of these scheme is baed on the hardness of the GapSVP problem.

Preliminaries

For an integer $q$, write $\mathbb {Z} _{q}:=\left(-q/2,q/2\right]\cap \mathbb {Z}$. This is not the same with the ring $\mathbb {Z} /q\mathbb {Z}$. For any $x\in \mathbb {Q}$, write $[x]_{p}$ for the unique value in $\left(-q/2,q/2\right]\cap \mathbb {Z}$ that is congruent to $x$ modulo $q$.

If $v,w$ are two $n$-dimensional vectors, then the tensor product $v\otimes w$ is the $n^{2}$ dimensional vector containing all elements of the form $v[i]w[j]$. Note that

$<v\otimes w,x\otimes y>=<v,x>\cdot <w,y>.$

Building Blocks of a homomorphic encryption scheme

We start by presenting Regev's basic public-key encryption scheme.

Let $q=q(n)$ be an integer function and let $\chi (n)$ be a distribution over $\mathbb {Z}$. The scheme 'Regev' is defined as follows:

• Regev.SecretKeygen( $1^{n}$ ): Sample $s\leftarrow \mathbb {Z} _{q}^{n}$ uniformly. Output $sk=s$.

• Regev.PublicKeygen($s$): Let $N:=(n+1)(\log q+O(1))$. Sample uniformly $A\leftarrow \mathbb {Z} _{q}^{N\times n}$ then sample $e\leftarrow \chi ^{N}$. Compute $b:=[A\cdot s+e]_{q}$. Here we apply $[\cdot ]_{q}$ to every entry in the $N$-dimensional vector $A\cdot s+e$ and define

$P:=[b\vert -A]\in \mathbb {Z} _{q}^{N\times (n+1)}$.

Output $pk=P$.

• Regev.Enc($pk,m$): To encrypt a message $m\in \{0,1\}$ using $pk=P$, sample $r\in \{0,1\}^{N}$ uniformly and output the ciphertext

$c:=\left[P^{T}\cdot r+\left\lfloor {\frac {q}{2}}\right\rfloor \cdot {\hat {m}}\right]_{q}\in \mathbb {Z} _{q}^{n+1}$ .

where ${\hat {m}}:=(m,0,\dots ,0)\in \{0,1\}^{n+1}$.

• Regev.Dec($sk,c$): To decrypt $c\in \mathbb {Z} _{q}^{n+1}$ using the secret key $sk=s$, compute

$m:=\left[\left\lfloor 2\cdot {\frac {[<c,(1,2)>]_{q}}{q}}\right\rceil \right]_{2}.$