GSW

Around 2013, Gentry, Sahai and Waters 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 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 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". Their security is based on the so-called approximate eigenvector 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" 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 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 } be a natural number, representing some modulus 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 N } a dimension parameter. A ciphertext is a matrix 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 } of 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 \times N } with "small" entries from 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 } . A secret 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 \vec{v} } is a 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} -dimensional vector 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 } with one big coefficient 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_i} . We can intuitively think of "small" as meaning much smaller (in order of magnitude) than 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} and "big" meaning the same order of magnitude 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 q } . In fact, we will make use of the case when the entries of 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 } belong 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 \{0,1 \} } . We also restrict the 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 } to be a "small" 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 C } encrypts 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 } under 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 \vec{v}} if $C\cdot {\vec {v}}=\mu \cdot {\vec {v}}+{\vec {e}}$, where ${\vec {e}}$ is a small error vector.

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

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

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

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

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

where ${\vec {e_{i}}}$ represents the error vector of $C_{i}$, for $i\in \{1,2\}$ . As long as the sum 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 \vec{e_1} + \vec{e_2} } is small, the sum matrix 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_1 +C_2 } is an encryption of 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_1 +\mu_2} .

Looking at the equality

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_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 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_1 \cdot C_2 } is an encryption of the 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 \mu_1 \mu_2 } , which can be decrypted correctly if 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 i} -th component of 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 \mu_2 \cdot \vec{e_1} + C_1 \cdot \vec{e_2} } is smaller than 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_i} .

Remark 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 C_2 \cdot C_1 } is also an encryption of 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_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 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_1 \cdot C_2 } and $C_{2}\cdot C_{1}$ are very different.