# GSW

Around 2013, Gentry, Sahai and Waters [1] proposed a new way of building FHE schemes whose homomorphic multiplication algorithms are more natural than those presented in BFV or BGV. A distinguished feature of the scheme we are about to present is an asymmetric formula for the growth of the noise when multiplying two ciphertexts. Due to this feature, certain types of circuits have a very slow noise growth rate. Based on this asymmetry, Alperin-Sheriff and Peikert [2] found a very efficient bootstrapping technique for the GSW scheme.

More efficient FHE schemes based on ring variants of GSW have been proposed since then. These achieve very fast bootstrapping via various optimisation techniques, such as "refreshing the ciphertexts" after every single homomorphic operation. To our knowledge, among the schemes based on GSW (and not only), TFHE [3] holds the record for fastest bootstrapping. In the literature, the schemes based on the aformentioned work of Gentry, Sahai and Waters are commonly referred to as "third generation FHE". The authors provide a reduction to the LWE problem (see Section 1.3.4) of GSW [1], basic the security of their scheme only on the LWE problem.

## Overview of the GSW scheme

We follow the exposition in the paper "Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based" [1] by Gentry, Sahai and Waters.

The description of this scheme is strikingly simple. In GSW, homomorphic encryption based on LWE is achieved while the homomorphic addition and multiplications correspond to matrix addition and multiplication, respectively.

Let ${\displaystyle q}$ be a natural number, representing some modulus and ${\displaystyle N}$ a dimension parameter. A ciphertext is a matrix ${\displaystyle C}$ of dimension ${\displaystyle N\times N}$ with "small" entries from ${\displaystyle \mathbb {Z} _{q}}$. A secret key ${\displaystyle {\vec {v}}}$ is a ${\displaystyle N}$-dimensional vector over ${\displaystyle \mathbb {Z} _{q}}$ with one big coefficient ${\displaystyle v_{i}}$. We can intuitively think of "small" as meaning much smaller (in order of magnitude) than ${\displaystyle q}$ and "big" meaning the same order of magnitude as ${\displaystyle q}$. In fact, we will make use of the case when the entries of ${\displaystyle C}$ belong to ${\displaystyle \{0,1\}}$. We also restrict the message ${\displaystyle \mu }$ to be a "small" integer.

${\displaystyle C}$ encrypts ${\displaystyle \mu }$ under ${\displaystyle {\vec {v}}}$ if ${\displaystyle C\cdot {\vec {v}}=\mu \cdot {\vec {v}}+{\vec {e}}}$, where ${\displaystyle {\vec {e}}}$ is a small error vector.

To decrypt, one first exacts the ${\displaystyle i}$-th row ${\displaystyle C_{i}}$ of ${\displaystyle C}$. Compute ${\displaystyle x\leftarrow \langle C_{i},{\vec {v}}\rangle =\mu \cdot v_{i}+e_{i}}$. Now, as ${\displaystyle v_{i}}$ is large and ${\displaystyle e_{i}}$ small, we have

${\displaystyle \mu =\lfloor x/v_{i}\rceil }$.

Basically, ${\displaystyle {\vec {v}}}$ is almost an eigenvector for ${\displaystyle C}$ corresponding to the eigenvalue ${\displaystyle \mu }$. This is commonly referred to being an approximate eigenvector.

Observe that if ${\displaystyle C_{1}}$ and ${\displaystyle C_{2}}$ encrypt ${\displaystyle \mu _{1}}$ and ${\displaystyle \mu _{2}}$ respectively under the same key vector ${\displaystyle v}$, then

${\displaystyle (C_{1}+C_{2})\cdot {\vec {v}}=(\mu _{1}+\mu _{2})\cdot {\vec {v}}+{\vec {e_{1}}}+{\vec {e_{2}}}}$,

where ${\displaystyle {\vec {e_{i}}}}$ represents the error vector of ${\displaystyle C_{i}}$, for ${\displaystyle i\in \{1,2\}}$ . As long as the sum ${\displaystyle {\vec {e_{1}}}+{\vec {e_{2}}}}$ is small, the sum matrix ${\displaystyle C_{1}+C_{2}}$ is an encryption of ${\displaystyle \mu _{1}+\mu _{2}}$.

Looking at the equality

${\displaystyle (C_{1}\cdot C_{2})\cdot {\vec {v}}=C_{1}\cdot (\mu _{2}\cdot {\vec {v}}+{\vec {e_{2}}})=\mu _{1}\mu _{2}\cdot {\vec {v}}+\mu _{2}\cdot {\vec {e_{1}}}+C_{1}\cdot {\vec {e_{2}}}}$

,

we observe that ${\displaystyle C_{1}\cdot C_{2}}$ is an encryption of the product ${\displaystyle \mu _{1}\mu _{2}}$, which can be decrypted correctly if the ${\displaystyle i}$-th component of the vector ${\displaystyle \mu _{2}\cdot {\vec {e_{1}}}+C_{1}\cdot {\vec {e_{2}}}}$ is smaller than ${\displaystyle v_{i}}$.

Remark that ${\displaystyle C_{2}\cdot C_{1}}$ is also an encryption of ${\displaystyle \mu _{1}\mu _{2}}$, even though matrix multiplication is not commutative. The essence of the previously anticipated asymmetry is captured by the fact that the noises of ${\displaystyle C_{1}\cdot C_{2}}$ and ${\displaystyle C_{2}\cdot C_{1}}$ are very different.

## Flattening ciphertexts and keeping the noise small

We can decrypt homomorphically evaluated ciphertext ${\displaystyle C}$ as long as the ${\displaystyle i}$-th component of the error vector ${\displaystyle {\vec {e}}}$ is small enough. As we saw in the overview section, the noise might grow quickly with each multiplication. To mitigate this and to perform homomorphically evaluations of deep circuits (in the sense of multiplication depth), observing that the noise growth depends of the size of the coefficients of the ciphertexts, the size of the messages and the fresh error size (in an asymmetric way), we can try to restrict the message space and the entries of the ciphertexts to ${\displaystyle \{0,1\}}$. We also impose a bound ${\displaystyle B}$ for the entries of the fresh fresh error vectors ${\displaystyle {\vec {e}}}$.

Such ciphertexts will be further called ${\displaystyle B}$-strongly bounded, terminology that is used throughout the paper GSW [1].

The homomorphic operations performed on ciphertexts should correspond to operations "in the clear" that keep the message within the set ${\displaystyle \{0,1\}}$. To achieve this, we will use only NAND gates to evaluate any circuit.

Notice that if ${\displaystyle C_{1},C_{2}}$ are two ${\displaystyle B}$-strongly bounded ciphertexts, the ciphertext ${\displaystyle C_{3}\leftarrow I_{N}-C_{1}C_{2}}$ obtained by evaluating a NAND gate has underlying message in ${\displaystyle \{0,1\}}$, but the coefficients of ${\displaystyle C_{3}}$'s error vector have magnitude at most ${\displaystyle (N+1)B}$. If one could ensure that the coefficients of ${\displaystyle C_{3}}$ have magnitude at most ${\displaystyle 1}$, then the noise after evaluating a NAND gate will remain quite small, allowing us to evaluate deeper circuits.

The authors introduce an operation on ciphertexts called flattening, inspired by ideas in second generation FHE schemes such as BGV. Flattening is basically an operation that modify vectors without affecting their dot product.

Let ${\displaystyle N=k\cdot l}$ , where ${\displaystyle l=\lfloor \log _{2}{q}+1\rfloor }$ and ${\displaystyle k}$ is a positive integer. We will consider ${\displaystyle {\vec {a}},{\vec {b}}\in \mathbb {Z} _{q}^{k}}$, two ${\displaystyle k}$-dimensional vector spaces.

${\displaystyle BitDecomp({\vec {a}})=(a_{1,0},\dots ,a_{1,l-1},\dots ,a_{k,0},\dots ,a_{k,l-1}),}$ where ${\displaystyle a_{i,j}}$ is the ${\displaystyle j}$-th bit in the binary decomposition of ${\displaystyle a_{i}}$, so a ${\displaystyle N}$-dimensional vector.

For any ${\displaystyle N}$-dimensional vector ${\displaystyle {\vec {a'}}=(a_{1,0},\dots ,a_{1,l-1},\dots ,a_{k,0},\dots ,a_{k,l-1})}$, define

${\displaystyle BitDecomp^{-1}({\vec {a'}})=\left(\sum 2^{j}\cdot a_{1,j},\dots ,\sum 2^{j}\cdot a_{k,j}\right)}$, now a ${\displaystyle k}$ dimensional vector,

and

${\displaystyle Flatten({\vec {a'}})=BitDecomp(BitDecomp^{-1}({\vec {a}}))\in \mathbb {Z} _{q}^{N}}$.

The authors also introduce

${\displaystyle Powersof2({\vec {b}})=(b_{1},2b_{1},\dots ,2^{l-1}b_{1},\dots ,b_{k},2b_{k},\dots ,2^{l-1}b_{k})}$, an ${\displaystyle N}$-dimensional vector.

Some obvious properties of these definitions are

• ${\displaystyle \langle BitDecomp({\vec {a}}),Powersof2({\vec {b}})\rangle =\langle a,b\rangle }$;
• For any ${\displaystyle N}$-dimensional ${\displaystyle {\vec {a'}}}$, we have that

${\displaystyle \langle {\vec {a'}},Powersof2({\vec {b}})\rangle =\langle BitDecomp^{-1}({\vec {a'}}),{\vec {b}}\rangle =\langle Flatten({\vec {a'}}),Powersof2({\vec {b}})\rangle .}$

The latter is showing us an interesting feature of ${\displaystyle Flatten}$, i.e. it makes the coefficients of a vector "small", without changing its inner product with ${\displaystyle Powersof2({\vec {b}})}$

We will have to "flatten" ciphertexts, which are matrices. When ${\displaystyle Flatten}$ is applied to a ${\displaystyle N\times N}$ matrix ${\displaystyle C}$ , this will be done by applying ${\displaystyle Flatten}$ to each row of ${\displaystyle C}$. Recall that a step in the decryption process is multiplying the ciphertext matrix ${\displaystyle C}$ with a secret key vector ${\displaystyle {\vec {v}}}$. We will always use ${\displaystyle {\vec {v}}=Powersof2({\vec {s}})}$, a vector of this special form in order for flattening to preserve the product between ${\displaystyle C}$ and ${\displaystyle {\vec {v}}}$ required for decryption.

Now, for any ${\displaystyle N\times N}$ ciphertext matrix ${\displaystyle C}$, we have

${\displaystyle Flatten(C)\cdot {\vec {v}}=C\cdot {\vec {v}}}$

After computing a ciphertext ${\displaystyle C_{3}\leftarrow I_{N}-C_{1}\cdot C_{2}}$ for the NAND gate, we will immediately flatten it, namely we will set

${\displaystyle C^{NAND}\leftarrow Flatten(C_{3})}$.

## The basic algorithms of the encryption scheme

Let ${\displaystyle \lambda }$ be the security parameter and ${\displaystyle L}$ a natural number representing the multiplicative level of homomorphic operations this scheme can achieve. If we know the maximal level ${\displaystyle L}$ that we want to evaluate, we can choose parameters such that the scheme can handle circuits of depth ${\displaystyle L}$. Thus, the scheme described here is a priori a Somewhat Homomorphic Encryption scheme and can be made fully homomorphic after applying Gentry's bootstrapping theorem.

• Setup(${\displaystyle 1^{\lambda },1^{L}}$): We choose a modulus ${\displaystyle q=q(\lambda ,L)}$, depending of ${\displaystyle \lambda ,L}$, a lattice dimension parameter ${\displaystyle n=n(\lambda ,L)}$ and an error distribution ${\displaystyle \chi =\chi (\lambda ,L)}$ such that the scheme achieves at least ${\displaystyle 2^{\lambda }}$ security against known attacks. We also choose a parameter ${\displaystyle m=m(\lambda ,L)=O(n\log _{q})}$. We set the paramaters of the scheme ${\displaystyle params=(n,q,\chi ,m)}$ and let ${\displaystyle l=\lfloor \log _{2}q\rfloor +1}$ and ${\displaystyle N=(n+1)\cdot l}$.
• SecretKeyGen(${\displaystyle params}$): Sample ${\displaystyle {\vec {t}}\leftarrow \mathbb {Z} _{q}^{n}}$ uniformly. Output ${\displaystyle sk={\vec {s}}\leftarrow (1,-t_{1},\dots ,-t_{n})\in \mathbb {\mathbb {Z} } _{q}^{n+1}}$. Let ${\displaystyle {\vec {v}}=Powersof2({\vec {s}})}$.
• PublicKeyGen(${\displaystyle params}$): Generate a matrix ${\displaystyle B=\mathbb {Z} _{q}^{m\times n}}$ and a vector with small entries (noise) ${\displaystyle {\vec {e}}\leftarrow \chi ^{m}}$. Set ${\displaystyle {\vec {b}}=B\cdot {\vec {t}}+{\vec {e}}}$ and ${\displaystyle A}$ to be the ${\displaystyle (n+1)}$ column matrix which is obtained by the placing ${\displaystyle {\vec {b}}}$ on the first column, fllowed by the ${\displaystyle n}$ columns of ${\displaystyle B}$. Set the public key ${\displaystyle pk=A}$. We observe that ${\displaystyle A\cdot {\vec {s}}={\vec {e}}.}$
• Enc(${\displaystyle params,pk,\mu }$): To encrypt a message ${\displaystyle \mu \in \mathbb {Z} _{q}}$, sample a uniform matrix ${\displaystyle R\in \{0,1\}^{N\times m}}$ and output the ciphertext
${\displaystyle C\leftarrow Flatten(\mu \cdot I_{N}+BitDecomp(R\cdot A))\in \mathbb {Z} _{q}^{N\times N}}$

Disclaimer: The decryption algorithm we describe below decrypts correctly only messages in ${\displaystyle \{0,1\}}$. This can be easily generalised to recover any ${\displaystyle \mu \in \mathbb {Z} _{q}}$, bit by bit, starting with the least significant one. The interested reader should consult for example the paper of Micciano and Peikert. [4]

• Dec(${\displaystyle params,sk,C}$): Observe that the first ${\displaystyle l}$ coefficients of ${\displaystyle {\vec {v}}}$ are ${\displaystyle 1,2,\dots ,2^{l-1}}$. Let us choose, among these coefficients, the unique ${\displaystyle v_{i}=2^{i}\in (q/4,q/2]}$. Let ${\displaystyle C_{i}}$ be the ${\displaystyle i}$-th row of ${\displaystyle C}$. We output
${\displaystyle \mu '=\left\lfloor {\frac {\langle C_{i},{\vec {v}}\rangle }{v_{i}}}\right\rceil }$ .

We remark that ${\displaystyle Dec}$ is only applied to one row of the ciphertext, however extra rows will play a role in the homomorphic operations. If ${\displaystyle C}$ is properly generated (fresh), then by the properties of ${\displaystyle BitDecomp}$ described above, we have

${\displaystyle C\cdot {\vec {v}}=\mu \cdot v+R\cdot A\cdot {\vec {s}}=\mu \cdot v+R\cdot {\vec {e}}}$

The ${\displaystyle i}$-th coefficient of the above expression is ${\displaystyle x_{i}=\mu \cdot v_{i}+\langle R,{\vec {e}}\rangle }$. In the encryption scheme, we set ${\displaystyle \chi }$ to ensure that the error ${\displaystyle {\vec {e}}}$ is ${\displaystyle B}$-bounded with very high probability.

## Homomorphic operations

• Add(${\displaystyle C_{1},C_{2}}$): To add ciphertexts ${\displaystyle C_{1},C_{2}\in \mathbb {Z} _{q}^{N\times N}}$, output ${\displaystyle Flatten(C_{1}+C_{2})}$.
• Mult(${\displaystyle C_{1},C_{2}}$): To multiply ciphertexts ${\displaystyle C_{1},C_{2}\in \mathbb {Z} _{q}^{N\times N}}$, output ${\displaystyle Flatten(C_{1}\cdot C_{2})}$.
• MultConst(C, ${\displaystyle \alpha }$): To multiply a ciphertext ${\displaystyle C\in \mathbb {Z} _{q}^{N\times N}}$ by a known constant ${\displaystyle \alpha \in \mathbb {Z} _{q}}$, given in the clear, we set ${\displaystyle M_{\alpha }\leftarrow \alpha \cdot I_{N}}$ and output ${\displaystyle Flatten(M_{\alpha }\cdot C)}$.

One could compute multiplication by ${\displaystyle \alpha }$ by repeating additions. However, by repeating additions, the error of the resulting ciphertext will be linear in ${\displaystyle \alpha }$. On the other hand, if one uses MultConst(), the error term depends only on the dimension ${\displaystyle N}$ and not on ${\displaystyle \alpha }$. This turns out to be extremely convenient for when ${\displaystyle \alpha }$ is very large (possible applications of this includes homomorphic fast Fourier transforms).

• NAND(): To NAND ciphertexts ${\displaystyle C_{1},C_{2}\in \mathbb {Z} _{q}^{N\times N}}$ that are known to encrypt messages ${\displaystyle \mu _{1},\mu _{2}\in \{0,1\}}$, output ${\displaystyle Flatten(I_{N}-C_{1}\cdot C_{2})}$.

The NAND homomorphic operation increases the error by a factor of at most ${\displaystyle N+1}$.

By iteratively applying the homomorphic operations above, different types of (boundeddepth) circuits may be homomorphically computed while maintaining correctness of decryption. The simplest ones to analyse are Boolean circuits computed over encryptions of ${\displaystyle \{0,1\}}$ values. Here the circuit can be converted to use only NAND gates, and the final ciphertext’s error will be bounded by ${\displaystyle (N+1)^{L}\cdot B}$, where L is the NAND-depth of the circuit, and ${\displaystyle B}$ is the original bound on the error of a fresh encryption of ${\displaystyle \{0,1\}}$.

## References

1. C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer). https://eprint.iacr.org/2013/340
2. J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094
3. I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully Homomorphic Encryptionover the Torus. In Journal of Cryptology, volume 33, pages 34–91 (2020). https://eprint.iacr.org/2018/421
4. D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT, pages 700–718, 2012. https://eprint.iacr.org/2011/501