GSW - Bootstrapping

Gentry's bootstrapping theorem allows for converting a “somewhat homomorphic” encryption scheme (which supports only a bounded number of homomorphic operations) into a fully homomorphic encryption one (which has no such bound). The bounded nature of all known somewhat homomorphic schemes cannot be avoided due to “error” terms in their ciphertexts, which are necessary for security. The error grows as a result of performing homomorphic operations, and if it grows too large, the ciphertext will no longer decrypt correctly.

Bootstrapping the error of a ciphertext so that it can support more homomorphic operations, by homomorphically evaluating the decryption function on the ciphertext. The result is a ciphertext that still encrypts the original encrypted message. If the error coming from the homomorphic evaluation is smaller than the error in the original ciphertext, we say that the ciphertext is “refreshed”. To date, bootstrapping is the only known way of obtaining an unbounded FHE scheme, i.e., one that can homomorphically evaluate any efficient function using keys and ciphertexts of a fixed size.

Here we present an efficient bootstrapping method for a variant of the GSW scheme, as presented in the paper of Alperin-Sheriff and Peikert .

Recall that in GSW, a ciphertext is a square binary matrix $C$, a secret key is a "structured" mod $q$ vector $s$, and $s$ is an "approximate mod $q$ eigenvector" of $C$, in the sense that $s^{t}C\approx \mu \cdot s^{t}$, where $\mu \in \mathbb {Z}$ is the message.

In this new variant, a ciphertext is a rectangular mod $q$ matrix $C$, a secret key is some (unstructured, short) integer vector $s\in \mathbb {Z} ^{n}$ and $s^{t}C\approx \mu \cdot s^{t}G$ (mod $q$), i.e. $s$ amd $G^{t}s$ are corresponding left- and right- "approximate singular vectors" of $C$.

A "simpler" variant of the GSW cryptosystem

The authors present a variant of the GSW scheme which permits a tighter analysis of its error growth under homomorphic operations.

Given a modulus $q$, let us denote by $l=\lceil \log _{2}(q)\rceil$ and define the "gadget" (we will think of it as column) vector

${\mathfrak {g}}=(1,2,4,\dots ,2^{l-1})\in \mathbb {Z} _{q}^{l}.$

Remark that $2^{l-2}\in [q/4,q/2){\pmod {q}}$, according to our choice of $l$.

A randomized decomposition function. There is a randomized, efficiently computable function ${\mathfrak {g}}^{-1}:\mathbb {Z} _{q}\to \mathbb {Z} ^{l}$ such that $x\leftarrow {\mathfrak {g}}^{-1}(a)$ is "subgaussian" with parameter $O(1)$, and always satisfies $\langle g,x\rangle =a$.

In particular $x$ is randomized and has low entries with very large probability.

For vectors and matrices over $\mathbb {Z} _{q}$, define the randomized function $G^{-1}:\mathbb {Z} _{q}^{n\times m}\to \mathbb {Z} ^{nl\times m}$ by applying ${\mathfrak {g}}$ independently to each entry. Notice that for any $A\in \mathbb {Z} _{q}^{n\times m}$, if $X\leftarrow G^{-1}(A)$, then $X$ has small entries (is "subgaussian") and

$G\cdot X=A$, where $G={\mathfrak {g}}^{t}\otimes I_{n}=\mathrm {diag} ({\mathfrak {g}}^{t},\dots ,{\mathfrak {g}}^{t})\in \mathbb {Z} _{q}^{n\times nl},$

is the block matrix with $n$ copies of ${\mathfrak {g}}^{t}$ as diagonal blocks, and zeros elsewhere.

This version of the GSW scheme has as parameters a dimension $n$, a modulus $q$ and $l=\lceil \log _{2}(q)\rceil$, as defined above. For bootstrapping, we only work with ciphertexts encrypting messages in $\{0,1\}\subseteq \mathbb {Z}$. The ciphertext space is ${\mathcal {C}}=\mathbb {Z} _{q}^{n\times nl}$. For simplicity, we present just a symmetric-key scheme, which can be converted to a public key setting, similar to the one described in GSW.

A substantial difference between the original GSW scheme and this variant is the following: the homomorphic multiplication procedure in the current variant uses the randomized $G^{-1}(\cdot )$ operation presented above. This gives important advantages, such as very simple error analysis (using the subgaussianity property) and the ability to completely re-randomize the error in a ciphertext.

The algorithms of the scheme are as follows

• GSW.Gen(): choose ${\overline {s}}\leftarrow \chi ^{n-1}$ and output the secret key $s=({\overline {s}},1)\in \mathbb {Z} ^{n}$.

• GSW.Enc($({\overline {s}},1),\mu \in \mathbb {Z}$): choose ${\overline {C}}\leftarrow Z_{q}^{(n-1)\times nl}$ uniformly and $e\leftarrow \chi ^{nl}$, let $b^{t}=e^{t}-{\overline {s}}^{t}{\overline {C}}$ mod $q$, and output the ciphertext

$C=\left({\begin{array}{c}{\overline {C}}\\b^{t}\end{array}}\right)+\mu G\in {\mathcal {C}},$

where $G=\mathrm {diag} ({\mathfrak {g}}^{t},\dots ,{\mathfrak {g}}^{t})\in \mathbb {Z} _{q}^{n\times nl}$.

• GSW.Dec($s,C\in {\mathcal {C}}$): let $c$ be the penultimate column of $C$. Output $\mu =\lfloor \langle s,c\rangle \rceil _{2}$, where $\lfloor \cdot \rfloor _{2}:\mathbb {Z} _{q}\to \{0,1\}$ indicates whether its argument is closer modulo $q$ to $0$ or to $2^{l-2}$, the penultimate entry of ${\mathfrak {g}}$.

• GSW.Add($C_{1},C_{2}$): Output $C_{1}+C_{2}$.

• GSW.Multiply($C_{1},C_{2}$ ): Output $C_{1}\cdot G^{-1}(C_{2})$. This operation is a ramdomized one, as $G^{-1}$ is randomized. The multiplication is also right-associative.

The authors remark that a fresh ciphertext is just $\mu G$ plus a matrix which contains $nl$ independent LWE samples under the secret ${\overline {s}}$ which are pseudorandom if one assumes the hardness of $LWE_{n-1},q,\chi$.

Correctness and homomorphic operations

A ciphertext $C$ is said to be designed to encrypt a message $\mu \in \mathbb {Z}$ (under a secret key $s$) if it is a fresh encryption of $\mu$, or if $C$ is the sum (or the product) of two ciphertexts that are designed to encrypt $\mu _{1},\mu _{2}\in \mathbb {Z}$ and $\mu =\mu _{1}+\mu _{2}$.

The error vector of a ciphertext $C$ designed to encrypt a message $\mu$ under the key $s$ is $e^{t}=s^{t}C-\mu \cdot s^{t}G$ (mod $q$).

Notice that the matrix $\mu G$ is designed to encrypt $\mu$ and has error $0$.

Claim. If $C$ is designed to encrypt some $\mu \in \{0,1\}\subset \mathbb {Z}$ and has error vector $e^{t}$ whose penultimate coordinate has magnitude less than $q/8$, then GSW.Dec($s,C$) correctly outputs $\mu$.

This follows from the fact that $s=({\overline {s}},1)$ and the penultimate column of $G$ is $(0,\dots ,0,2^{l-2})$, where $2^{l-2}\in [q/4,q/2)$ mod $q$.

Let $C_{1},C_{2}$ be ciphertexts designed to encrypt $\mu _{1},\mu _{2}\in \mathbb {Z}$ and have error vectors $e_{1}^{t},e_{2}^{t}$. Then, their homomorphic sum has error vector $e_{1}^{t}+e_{2}^{t}$. Moreover, if $C_{1}\boxdot C_{2}$ is the homomorphic product of these ciphertexts, then for $X\leftarrow G^{-1}(C_{2})$ (subgaussian), we have the following

$s^{t}(C_{1}\boxdot C_{2})=s^{t}C_{1}\cdot X=(e_{1}^{t}+\mu _{1}\cdot s^{t}G)X$,

which as $G\cdot X=C_{2}$ is further equal to

$s^{t}(C_{1}\boxdot C_{2})=e_{1}^{t}X+\mu _{1}(e_{2}^{t}+\mu _{2}\cdot s^{t}G)=(e_{1}^{t}X+\mu _{1}e_{2}^{t})+\mu _{1}\mu _{2}\cdot s^{t}G.$

It is important to remember that the error upon multiplication is quasi-additive and asymmetric with respect to the errors $e_{1}^{t},e_{2}^{t}$. The first error is multiplied by a subgaussian matrix $X$, the second error vector $e_{2}^{t}$ is only multiplied by the message $\mu _{1}$, which the authors make sure they always keep in $\{0,1\}$.

Homomorphic product of multiple ciphertexts. Suppose that $C_{i},i\in [k]$ are designed to encrypt $\mu _{i}\in \{0,1\}$ and have error vectors $e_{i}^{t}$. Then for any fixed values of these variables, the matrix

$C\leftarrow C_{1}\boxdot \left(C_{2}\boxdot (\dots C_{k}\boxdot G)\dots )\right)$

has an error vector whose entries are mutually independent and subgaussian with parameter $O(||e||)$, where $e^{t}=(e_{1}^{t},\dots ,e_{k}^{t})\in \mathbb {Z} ^{knl}$ is the concatenation of the individual error vectors.

Homomorphic encryption for Symmetric Groups

We describe HEPerm a homomorphic encryption scheme for symmetric groups. Let ${\mathcal {C}}$ be the ciphertext space for the GSW scheme. The main procedures of HEPerm are as follows:

• HEPerm.Enc($sk,\pi \in S_{r}$): let $P=(p_{i,j})\in \{0,1\}^{r\times r}$ be the permutation matrix associated with $\pi \in S_{r}$. Output the following ciphertext space

$C=(c_{i,j})\in {\mathcal {C}}^{r\times r},$, where $c_{i,j}\leftarrow GSW.Enc(sk,p_{i,j}).$

This is an entry-wise encryption of $P$. Decryption is obvious. A ciphertext $C\in {\mathcal {C}}^{r\times r}$ is said to be "designed" to encrypt a permutation $pi\in S_{r}$, if its $C$-entries are designed to encrypt the corresponding entries of $P_{\pi }$.

$J\in {\mathcal {C}}^{r\times r}$ will denote the encryption of the identity permutation, where each entry is encrypted with zero noise.

• Homomorphic composition: $C^{\pi }\circ C^{\sigma }$ will be computed in the obvious way. Namely, the entries of the output $C^{\pi }\circ C^{\sigma }=(c_{i,j})\in {\mathcal {C}}^{r\times r}$ where

$c_{i,j}\leftarrow \sum \limits _{l\in [r]}(c_{i,l}^{\pi }\boxdot c_{l,j}^{\sigma })\in {\mathcal {C}}.$

Like the multiplication $\boxdot$ for ciphertexts in the GSW, the composition $\circ$ is right associative.

• Homomorphic equality test Eq?($C^{\pi }=(c_{i,j}^{\pi },\sigma \in S_{r})$): Given a ciphertext encrypting some permutation $\pi \in S_{r}$ and a permutation $\sigma \in S_{r}$ (in the clear), output a ciphertext $c\in {\mathcal {C}}$ encrypting $1$ if $\pi =\sigma$ and $0$ otherwise, i.e. output

$c\leftarrow \prod \limits _{i\in [r]}c_{\sigma (i),i}^{\pi }\boxdot g$ ,

where $g\in {\mathcal {C}}$ is the fixed zero-error encryption of $1$.

Remark the for the two operations above, the GSW ciphertext(s) that appear in the output are always designed to encrypt $\{0,1\}$ messages.

To analyse the noise resulting in these operations, let is recall that the GSW scheme is parameterized by $n,q$. Denote the space of error vectors by ${\mathcal {E}}=\mathbb {Z} ^{m}$, where $m=n\lceil \log _{2}(q)\rceil$. The Euclidean norm on ${\mathcal {E}}^{r}=\mathbb {Z} ^{mr}$ is defined in the ovious way. In the following analysis, we will often consider vectors and matrices over ${\mathcal {E}}$, i.e. in which the entries are vectors from ${\mathcal {E}}$.

Claim. (Lemma 4.1 in the first reference) The error matrix in $C^{\pi }\circ C^{\sigma }$ is $E+P^{\pi }\cdot E^{\sigma }$, where $P^{\pi }$ is the matrix encoding $\pi$ (in the clear), $E^{\sigma }\in {\mathcal {E}}^{r\times r}$ is the error of $C^{\sigma }$ and the $\mathbb {Z}$-entries of the matrix $E$ are mutually independent, and those in its $i$-th row are subgaussian with parameter $O(||e_{i}^{\pi }||)$, where $e_{i}^{\pi }$ is the $i$-th row of $E^{\pi }$.

Similarly to a multiplication chain of GSW ciphertexts, one can perform a (right-associative) chain of compositions while incurring only small error growth. For conveniece of analysis, we always include the fixed zero-error ciphertext $J\in {\mathcal {C}}^{r\times r}$ as the rightmost ciphertext in the chain.

Claim. (Corollary 4.2 in the first reference) Suppose that $C_{i}$ are designed to encrypt permutation matrices $P_{i}\in \{0,1\}^{r\times r}$ and have error matrices $E_{i}\in {\mathcal {E}}^{r\times r}$. Then for any fixed values of these variables,

$C\leftarrow C_{1}\circ (C_{2}\circ (\dots (C_{k}\circ J)\dots ))$

has an error matrix whose $\mathbb {Z}$-entries are mutually independent, and those in its $i$-th row are subgaussian with parameter $O(||e_{i}||)$, where $e_{i}^{t}\in {\mathcal {E}}^{kr}$ is the $i$-th row of the concatenated matrices $[E_{1}|\dots |E_{k}]$.

Bootstrapping

We have to instantiate the GSW and HEPerm with parameters $n,Q,\chi$. Importantly, the ciphertext modulus $Q$ is not the modulus $q$ of the scheme to be bootstrapped, but rather some modulus $Q>>q$. Let ${\mathcal {C}}$ be the ciphertext of the GSW scheme.

Let $q$ be of the form $q=\prod _{i\in [t]}r_{i}$, where $r_{i}$ are small powers of distinct primes. One can choose $q={\tilde {O}}(\lambda )$ to be large enough by letting it be the product of all maximal prime-powers $r_{i}$ that are bounded by $O(\log(\lambda ))$, of which there are $t=O(\log(\lambda )/log(\log(\lambda )))$. Let $\phi$ be the group embedding of $\mathbb {Z} _{q}$ into $S=S_{r_{1}}\times S_{r_{t}}$, and let $\phi _{i}$ denote the $i$-th component of this embedding, i.e. the one from $\mathbb {Z} _{q}$ into $S_{r_{i}}$.

• BootGen($s\in \mathbb {Z} _{q}^{d},sk$): Given secret key $s\in \mathbb {Z} _{q}^{d}$ for the scheme GSW and a secret key $sk$ for HEPerm, embed each coordinate $s_{j}\in \mathbb {Z} _{q}$ of $s$ as $\phi (s_{j})\in S$ and encrypt the components under HEPerm. That is, generate and output the bootstrapping key

$bk=\{C_{i,j}\leftarrow HEPerm.Enc(sk,\phi _{i}(s_{j})):i\in [t],j\in [d]\}$.

Recalling that we are working with embeddings of $\mathbb {Z} _{r_{i}}$, each $C_{i,j}\in {\mathcal {C}}^{r_{i}}$ can be represented as a tuple of $r_{i}$ GSW ciphertexts encrypting an indicator vector. Since $t,r_{i}=O(\log \lambda )$ and $d={\tilde {O}}(\lambda )$, the bootstrapping key has ${\tilde {O}}(\lambda )$ ciphertexts.

• Bootstrap($bk,c\in \{0,1\}^{d}$): given a binary ciphertext $c\in \{0,1\}^{d}$, do the following:

First, homomorphically compute an encryption of $v=\langle s,c\rangle =\sum _{j:c_{j}=1}s_{j}\in \mathbb {Z} _{q}$ using the encryptions of the $s_{j}\in \mathbb {Z} _{q}$ as embedded into the permutation group $S$. Additions above are replaced using a chain of compositions.

Then, one has to round. Homomorphically map $v\in \mathbb {Z} _{q}$ to $\{0,1\}$, in the following way. For each $x\in \mathbb {Z} _{q}$ such that $f(x)=1$, homomorphically tests whether $v=x$ by evaluating the homomorphic product of the resulting ciphertexts from all the equality tests $v=x$ mod $r_{i}$. Then homomorphically sum the results of all the $v=x$ tests.

Bootstrapping performs ${\tilde {O}}(\lambda )$ homomorphic multiplications and additions on GSW ciphertexts.

We refer to the paper of Alperin-Sheriff and Peikert <ref name = "ASP"> for a detailed analysis of the security and correctness.