Last time, we went through the overview of what FHE is, the different stages towards FHE, and the brief history of it. I think at this point, we should be pretty comfortable with understanding what FHE is and its potential applications.
We concluded the last post by alluding to this GSW FHE Scheme. It's the 3rd Gen FHE Scheme based on the LWE Problem assumption which stems from Lattice-based Cryptography.
Although these topics might sound pretty archaic and distant, I claim that it's actually not that hard to understand. In fact, with just simple knowledge in linear algebra, we can fully grasp the idea of the GSW FHE Scheme.
In this post, let's together review some fundamental concept of Lattice-based Crypto and the LWE Problem so we can build up our knowledge to the actual GSW Scheme later.
So what the heck is Lattice-based Crypto? According to Wikipedia:
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography.
Word. Lattice-based Crypto is basically the Crypto that uses lattices. Sounds like a very convenient explaination.
However, for us who don't really understand what lattices are, this concept sounds very confusing. To be honest, I still haven't fully grasped the definition of lattices. If we look at its definition on Wikipedia again, it involves some geometry and group theory concepts which is also hard to comprehend. I think this is probably why this topic scared away lots of pondering readers.
Therefore, I decided to take a more practical approach to introduce this concept using my own understanding of it.
Disclaimer: To more hard-core readers, my interpretation of this concept might not be entirely correct. Here I'm just trying to provide a more friendly perspective of this problem.
At this point, I would assume that we all have some linear algebra background. (If not, I highly recommend watching the YouTube series on Linear Algebra by 3Blue1Brown.)
We all know what a basis vector is - if we say a linear space has basis vectors
If we have some basis vectors
However, what if we were to add one more limitation: all the coefficients
To imagine this, check out the image down below:
Basically, instead of having an area of infinite vector choices, now we have a grid of finite vector choices that are linear combinations of the basis vectors of this linear space where the coefficients are all integers. We refer to this grid-like system as an Integer Lattice.
Although we are describing a two-dimensional lattice structure, it's perfectly fine to extend it into multiple dimensions. In fact, in order to make this into a hard problem that's suitable for cryptography, we need to have plenty of dimensions.
So what's special about Integer Lattices? Turns out it's the "Integer" part that makes this interesting.
Previously, when we talk about the span of the basis vectors, since the coefficients that multiplies the basis vectors can be any number, we can basically express every single vector in the linear space with a set of unique coefficients.
Now since we limit the coefficients to be integers only, we can no longer represent every single element in the original linear space using these basis vectors. Suppose we have basis vectors: $$ b_0 = \begin{bmatrix} 1 \ 0 \end{bmatrix},b_1 = \begin{bmatrix} 0 \ 1 \end{bmatrix} $$ And we would like to represent the vector $v = \begin{bmatrix} 2.6 \ 3.1 \end{bmatrix}$. There isn't a valid pair of integer coefficients that allows us to do this.
However, here comes the interesting part: Since we cannot perfectly represent the vector with a pair of integer coefficients, what about a very close approximation? The problem becomes whether we can find a pair of integer coefficients
This problem is usually known as the Closest Vector Problem (CVP). And it's proven to be a very hard (NP-hard!) problem to solve, once we have lots of dimensions and a handful of basis vectors. This problem serves a prelude to the Learning With Errors problem.
Now we should have a pretty good understanding of integer lattices! Let's switch gears for a bit and talk about the main topic of this post: Learning With Errors.
Before we get into the specifics, I want to quickly do a warmup detour - a retrospection of high school algebra.
In high school algebra class, we might have encountered problems where we need to solve a system of equations. Namely, we are given a set of equations such as:
$$
3x_1 + 4x_2 + x_3 = 0\
4x_1 + 2x_2 + 6x_3 = 1\
x_1 + x_2 + x_3 = 1
$$
In order to solve this kind of problems, we are taught the Row Reduction Method. Basically the idea is to use one equation to subtract another equation, so we can end up in new equations. In this example above, if we subtract the first row with the third row, we can obtain
Eventually, after we do enough of these row reductions, if the problem is set up correctly, we can end up with some pretty nice expressions of
When we systematically learn about Linear Algebra in college, we tend to express this kind of operations in term of matrices. For example, the system of equations presented above can be converted into: $$ Ax = b\ \begin{bmatrix} 3 & 4 & 1\ 4 & 2 & 6\ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} x_1\ x_2\ x_3 \end{bmatrix}
\begin{bmatrix}
0\
1\
1
\end{bmatrix}
$$
The row reduction operation therefore, can be applied on matrices
Since solving systems of equations is a problem taught in high school, we all know that it's not really a hard one to solve. If the problem is well-defined, then after a few row reductions, we can easily obtain the results. Any computer can solve a well-defined Gaussian Elimination problem pretty efficiently.
However, what if the original system of equation is somehow noisy?
Namely, what if we also add an additional noise vector to the
This problem, where we are trying to "learn" the unknown vector
If you are a careful reader, you might find very interesting similarities between the LWE problem and the CVP problem we discussed in previous sections. We are both trying to find a unique "coefficients" vector
Now, let's formally define LWE again.
First, we need to introduce a set of notations for the LWE problem:
- We view
$\mathbb{Z}_q$ as integers in range$(-q/2, q/2)$ as a finite field. - We define
$\mid\mid e \in \mathbb{Z}^m \mid\mid_\infty$ as the infinity norm operation on vector$e$ with$m$ elements. The operations returns the element in vector$e$ that has the greatest absolute value. Namely,$\mid\mid e \mid\mid_\infty = max_i^m \mid e_i \mid$ . - Finally, we define
$x_B$ as a random variable that has its distribution bounded by a number$B$ . Namely, every sample of this random variable will definitely be smaller than$B$ .$\forall x \leftarrow x_B^m: \mid\mid x \mid\mid_\infty \le B$ .
Now, here is the formal definition of LWE: $$ LWE(n, m, q, x_B): \text{ Search Version}\ \text{Let } A \stackrel{R}{\leftarrow} \mathbb{Z}_q^{m \times n}, s \stackrel{R}{\leftarrow} \mathbb{Z}_q, e \stackrel{R}{\leftarrow} x_B.\ \text{Given } (A, As + e) \text{, find } s' \in \mathbb{Z}q^n \text{ s.t. } \mid\mid As' - (As + e) \mid\mid\infty \le B $$
Allow me to paraphrase with my own words again.
Basically, in a LWE problem (Search Version), we need to define the dimensions of the matrix
The LWE problem is basically asking us to recover the unknown vector
Notice that we have a lot of parameters here. LWE has a lot more parameters than the other common problems we encounter in cryptography, such as the Discrete Log Problem in the Diffle-Hellman key exchange protocol. Here, let's see what these parameters are really used for again:
-
$n$ is commonly referred as the security parameter ($\lambda$ ). Therefore, the more unknown variables we have in the system, the harder the LWE problem becomes. -
$m$ is usually a polynomial of$n$ . Namely$m = poly(n)$ and$m >> n$ . The larger$m$ goes, the easier the LWE problem gets. -
$q$ is usually$poly(n)$ . For example, we can set$q$ to be$O(n^2)$ . -
$B << q$ , we want the error bound to be negligible to the size of$q$ , so we can properly recover the unknown vector.
Usually, when we use LWE in practice, we will predefine
Notice that we keep calling the previous LWE problem construct as the Search Version. This is because in the problem we are given the matrix
The Decisional LWE (DLWE) is basically the same setup as the Search Version. However, instead of trying to recover
The reasoning behind the assumption is fairly straightforward: Since it's hard to recover the unknown vector
Actually, this is not the first time we see both the search version and decisional version of a same problem in cryptography. Similar concepts were used when we evaluate the security of the Diffie-Hellman Key Exchange Protocol.
Since Diffie-Hellman Protocol is based on exponentiation of group elements, the general assumption is that performing a discrete log on a group element is hard. Namely, if we are given
When proving semantic security of the DH protocol, we usually prefers the decisional version - the Decisional Diffie-Hellman Problem (DDH). Namely, in this problem, we are presented either
However, if we want to compare the hardness of DDH and CDH, turns out solving CDH is normally harder than solving DDH. This is because of a powerful operation called the Pairing operation, which takes two group elements and maps their product of exponents into another group. (We have covered Pairings in the previous post.)
With the help of pairings, we can easily crack DDH:
$$
e(g^a, g^b) = e(g^{ab}, g) = g_T^{ab}
$$
We can simply apply the pairing operation
This special property is kind of annoying, because it gives us a bad lower bound of the problem hardness. We cannot efficiently relate the hardness of CDH and DDH, and we need to be extra careful when instantiating a key exchange protocol. Therefore, we normally characterize the hardness of DDH by its average performance.
Something worth noticing here is that, the DLWE problem is equally hard as the SLWE problem. Because both problems rely on the same assumption that we cannot recover unknown vector
If you made it to this line, it means we fully understood how LWE works now. Yay!
For the next step, let's actually put together all the knowledge we have learned so far and use lattice-based problems to actually do some cool latticed-based encryption.
One of the most prominent examples of Lattice-based Encryption Schemes is the Regev Encryption. It is invented by Regev in 2005, and it uses the standard assumptions of the DLWE problem.
Regev Encryption is an "ElGamal" style public key encryption scheme. Let's see its formal definition.
-
$KeyGen(1^\lambda)$ : The KeyGen algorithm will first create an LWE problem instance. Namely, it will sample$A \stackrel{R}{\leftarrow} \mathbb{Z}_q^{m \times n}, s \stackrel{R}{\leftarrow} \mathbb{Z}_q^n, e \stackrel{R}{\leftarrow} x_B^m$ and set the product with error term to be$b = As + e$ . We also need to enforce that$q/4 > mB$ for the correctness property. Finally, it sets the private key$sk = s$ , and the public key$pk = (A, b)$ . -
$Encrypt(pk, x \in {0, 1})$ : The encryption algorithm encrypts a single bit at a time. Just like ElGamal, it will first sample some random binary nonce vector$r \stackrel{R}{\leftarrow} \mathbb{Z}_2^m \in {0,1}^m$ , then it will set the first part of the ciphertext$c_0$ to be$r^TA$ , and the second part of the ciphertext$c_1$ to be$r^Tb + \lfloor q/2 \rfloor x$ . Finally, it outputs both parts$(c_0, c_1)$ as the final ciphertext. -
$Decrypt(sk, ct=(c_0, c_1))$ : To decrypt the ciphertext, first we compute$\tilde{x} = c_1 - c_0 \cdot s$ . Then we will check whether$\mid \tilde{x} \mid < q/4$ . If so, we output$x = 0$ , else we output$x = 1$ .
The Correctness property of the encryption scheme is pretty straightforward. We can expand the computation of
Therefore, we can guarantee that the decryption will always succeed. Namely, the error term is tractable and bounded by a negligible amount which won't impact with decryption at all.
Next, we take a look at its Security property.
In order to prove that this scheme is secure, we need to use a very powerful tool in cryptographic proofs: the Hybrid Arguments.
This is really nothing fancy. Hybrid arguments allow us to achieve a certain proof via incremental steps. Let's first construct the first hybrid, which is basically the view of an eavesdropping adversary that sees the entire encryption transcript.
$$
H_0 : pk = (A, b = As + e), c_0 = r^TA, c_1 = r^Tb + q/2 \cdot x
$$
Now, we can replace a part of the public key and arrive at the second hybrid:
$$
H_1 : pk = (A, v \stackrel{R}{\leftarrow} \mathbb{Z}_q^m), c_0 = r^TA, c_1 = r^Tb + q/2 \cdot x
$$
We know that one cannot efficiently distinguish between
Finally, we combine the hybrids and arrive at the conclusion that one cannot effiently distinguish between
To review, we first described what Integer Lattices are, and talked about the hard CVP problem. Then we switched gear to talk about solving systems of equations which can be generalized as Gaussian Elimination. After that we added noise to the problem and that gave us the Learning With Errors problem. We gave formal definition to the LWE problem along with its parameters. Next, we talk about how to transition from SLWE to DLWE, and why is it better compared to DDH/CDH. Finally, we concluded the post with an intro and proof to the Lattice-based Encryption Scheme - Regev Encryption.
And now we are here. If you made it through here, we have just gone through all the fundamental building blocks that will get us FHE!
Since this post is probably already too long, I shall conclude here. For the next post, we will take a look at how to construct a Leveled FHE scheme with noise.