Author: Steven Yue, originally published on the author’s Zhihu
In the previous article, we together understood what lattice cryptography is, and then we learned about the construction of the LWE problem. Finally, we combined the knowledge we learned to form the most classic Regev encryption algorithm in lattice cryptography. (For details, click “Exploring Fully Homomorphic Encryption: Definition and Historical Review”)
I hope that by now, everyone has a deep understanding of the content discussed in the previous issue. In this issue, we can truly start the final boss of practical implementation – constructing a fully homomorphic encryption system.
Review of the Previous Issue
Before we begin, in order to facilitate a better understanding of the FHE system described in this issue, let’s quickly review the key points discussed in the previous two articles.
- Lido monopoly may bring big trouble to Ethereum, V God proposed a solution
- DeFi has yet to fulfill its privacy promises.
- Opinion The Federal Reserve is unlikely to cut interest rates in the short term, but recession is inevitable, testing global risk assets.
LWE Problem
The focus of the previous article was the LWE problem. It can be said that understanding LWE, lattice cryptography, and FHE problems correctly has already solved half of the problem.
Fully Homomorphic Encryption System
Finally, let’s review the construction of a complete fully homomorphic encryption (FHE) system discussed in the previous previous article.
The Four Stages of FHE
In the first article, we also learned about the four different stages that make up an FHE system:
-
Partially Homomorphic Encryption: In this stage, the functionality F that can be computed is either composed of addition/linear combinations or multiplication. Common examples include RSA (multiplicative homomorphism) and ElGamal (additive homomorphism).
-
Somewhat Homomorphic Encryption: Algorithms in this stage have incomplete homomorphic properties, such as the ElGamal cyclic group with LianGuairtially pairing, which has complete additive homomorphic properties but very weak multiplicative homomorphic properties.
-
Leveled Fully Homomorphic Encryption: Algorithms in this stage can perform homomorphic operations on any form of functionality F, but the complexity of the transformed circuit cannot exceed the upper limit L, otherwise the noise will be too large and information will be lost.
-
Fully Homomorphic Encryption: The final stage is the FHE we want to achieve. In this stage, we can compute functionalities F of any complexity, and the noise can be perfectly controlled within a controllable range.
As mentioned before, by bootstrapping, a Leveled Fully Homomorphic Encryption (LFHE) system can be effectively transformed into a Fully Homomorphic Encryption (FHE) system. The concept of bootstrapping was pointed out by Craig Gentry, the pioneer of the FHE field, in his PhD thesis in 2009. The GSW system we are going to discuss this time is an FLHE system, which is then effectively transformed into an FHE system through bootstrapping.
In summary, in this issue, let’s carefully explore how the LFHE system proposed in GSW is constructed~
PS: The content of this review is only a small part of the description in the previous two issues. So if you are not familiar enough with the definition of FHE and the LWE problem, you may want to go back and read the previous articles before continuing to read on.
Three attempts to construct the GSW-LFHE system
The GSW system is the third-generation homomorphic encryption system proposed by Gentry, Sahai, and Waters in 2013. The entire encryption system revolves around a core concept: the approximate eigenvectors of matrices.
At first glance, this concept is a bit vague. So the entire paper is actually divided into three stages, progressively introducing the construction of this system. In each of these three stages, an attempt of the LFHE system is proposed and evaluated to determine its feasibility.
Without further ado, let’s delve into the three attempts of LFHE construction presented by Gentry in the original paper and gradually deduce the full picture of the GSW system.
First attempt: Eigenvalues and Eigenvectors of Matrices
The Problem with the “Encryption Algorithm”
Our first attempt perfectly meets all the requirements of fully homomorphic encryption, and it seems that we can wrap up this article directly.
But we can’t be too happy too soon because this system has a fatal weakness. If attentive readers will notice, when we were describing the first approach, we always put quotation marks around the word “encryption”.
However, this architecture is a good inspiration for our subsequent attempts. As mentioned in the previous issue, the Gaussian elimination method can find solutions to systems of linear equations, but if we introduce noise, it becomes the difficult LWE problem. Let’s try the same approach here, adding noise to the equation of eigenvectors and eigenvalues, to see if there will be any changes.
Summary at the end
Compared to the previous two articles, this article can be said to be the most academic, with the most mathematical formulas. I have tried my best to use plain language to describe the construction of the LFHE system. If you still have some confusion while reading, you can go back and read it again, or private message me for further discussion!
At the beginning of the article, I mentioned that the essence of the GSW system lies in the definition of approximate eigenvectors. We started with ordinary eigenvectors to construct a fully homomorphic system that is not encrypted. Then, we added noise vectors similar to those in the LWE problem to construct a partially homomorphic system that is encrypted. Finally, we used binary decomposition as a tool to construct the finite-level fully homomorphic encryption system mentioned in GSW.
If you have already understood what the GSW system is doing and how it is constructed, congratulations, you have mastered the essence of FHE system construction! This is something to be happy about, because FHE is a relatively young field (about 10 years old), and we are already at the forefront of cryptographic technology.
What’s next?
Based on the description in this article by LianGuaiper, we have built a set of LFHE systems together. But as I promised in the first article, we will continue to work hard and strive for true FHE.
(Note: The encryption algorithm mentioned in GSW’s LianGuaiper may differ from what we mentioned in this article, using an asymmetric form, while we used symmetric encryption. However, this does not affect the correctness or functionality of the entire system. Personally, I think this is easier to understand.)
In order to convert the LFHE system into a true FHE system, we need to use the method called Bootstrapping proposed by Gentry. Simply put, Bootstrapping can “refresh” a ciphertext with a large amount of noise that is about to reach the critical value into a ciphertext with a small amount of noise, so that unlimited homomorphic operations can be performed.
In the next issue, we will introduce in detail how Bootstrapping is applied in the GSW system to convert the original LFHE into FHE. If the length allows, we can also discuss the differences between existing FHE libraries such as HELib, SEAL, and TFHE. See you next time~
Like what you're reading? Subscribe to our top stories.
We will continue to update Gambling Chain; if you have any questions or suggestions, please contact us!
