Technical Dry Goods | How to Learn Full Homomorphic Encryption

This article was written by Dr. Zhichen Chen.

Since the WeChat public account posted my blog post "Words for PhD students" in 2015, many graduate students have asked how to learn about full homomorphic encryption, and what are the three must-see articles on full homomorphic encryption. Here is a unified answer for everyone.

Learning full homomorphic encryption requires three parts of knowledge: mathematical basis, lattice password basis, and full homomorphic encryption.

Many graduate students think that they only study fully homomorphic encryption when they are studying full homomorphic encryption, so when they read the first article, they went straight from entry to give up.

• Viewpoint | Meditations on Fault Proof (1)
• Ethereum 2.0 client test online for several weeks, running 22,000 validators
• Twitter Picks | Slamming? Satoshi Aumoto was exploded by lawyers who do not own $ 8 billion in Bitcoin private keys

This is because any knowledge requires other knowledge as a basis, and full homomorphic encryption belongs to public key cryptography, so first it is an encryption algorithm, and then it has homomorphic properties.

Therefore, you must be familiar with the lattice encryption algorithm and related mathematical knowledge. Let's talk about these three parts separately.

Mathematical basis

Because the current homomorphic encryption is built on the lattice cipher algorithm, what mathematical knowledge is required for the lattice password and what mathematical knowledge is required for the homomorphic encryption itself constitute the mathematical foundation required for the entire study.

What mathematical foundations do lattice passwords require?

The basis of linear algebra and abstract algebra is mainly required. Linear algebra is generally learned in science and engineering, such as calculations of matrices, determinants, and the basis of vector spaces. The calculations in the lattice encryption algorithm are all matrix determinant calculations.

Abstract algebra estimation is not a mathematics major and may not have been learned. Knowledge of groups, rings, and domains in abstract algebra is very important, especially rings, which are the mathematical basis of lattice encryption. Abstract algebra generally also involves some knowledge of number theory, which is also used in full homomorphic encryption, such as modulo calculation.

Beginners can see: An Introduction to Mathematical Cryptography to add relevant mathematical knowledge.

Of course, the best recognized textbook for cryptography is Jonathan Katz's INTRODUCTION TO MODERN CRYPTOGRAPHY. If you want to learn about cryptography comprehensively and deeply, you can read this book. There are related mathematical knowledge.

Grid password

To learn full homomorphic encryption, you must be familiar with grid passwords, which is inevitable. Because the full homomorphic encryption itself is constructed on the lattice cipher algorithm.

So how to learn lattice passwords?

You should start with the LWE encryption algorithm and then transition to the ring LWE encryption algorithm. The process of the LWE encryption algorithm must be made clear, so that learning homomorphic encryption will be much easier.

How to learn the LWE encryption algorithm?

It is recommended to read an overview article by Oded Regev: The Learning with Errors Problem. This article is relatively easy to write. But don't forget, if you think about it, it is impossible. Need to look again and again. Note the meaning of each parameter in LWE encryption.

Oded Regev is the author of the LWE reduction problem. He also wrote a handbook of lattice passwords, but it is very theoretical and not suitable for beginners.

Learning of fully homomorphic encryption

To learn full homomorphic encryption, just read 3 + 2 articles. After reading the first three articles, you can read the last two articles, otherwise you don't know what the last article is about. However, this final article happens to be the hottest full homomorphic encryption scheme at the moment.

First post: BV11 : Efficient Fully Homomorphic Encryption from (Standard) LWE

The turning point of full homomorphic encryption is from BV11, which can be built on the difficult problem of standard lattices like LWE. Makes full homomorphic encryption much simpler than before.

And BV11 has a very good writing style and is easy to understand.

Second article: BGV12 : (Leveled) fully homomorphic encryption without bootstrapping

BGV is the solution based on HElib. Modular exchange is derived from this article. Makes it possible to build hierarchical FHE without Bootstrapping.

Third article: Bra12: Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

Bra12 is the solution based on Microsoft SEAL library. It is much simpler than BGV, because it can build hierarchical FHE without the need for modulo exchange.

The above three articles directly laid the foundation for full homomorphic encryption. Worth reading again and again.

Fourth article: GSW13 : Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

GSW13 is the shortest in the homomorphic encryption article, and the solution is as simple as the general LWE encryption algorithm.

GSW13 has led to many theoretical results of full homomorphic encryption, allowing theoretical research on full homomorphic encryption to continue to develop for a while. However, this solution is not practical in application, so it only shines in theory.

We have conducted an in-depth analysis of GSW. In fact, GSW schemes reduce noise and maintain homomorphism in a ciphertext. For details, please see our article. (Why is it possible to construct fully homomorphic encryption on lattices-1,2,3)

Fifth article: CKKS17: Homomorphic encryption for arithmetic of approximate numbers

CKKS17 can support the calculation of floating point numbers, and it is very efficient, which is directly used in machine learning. In fact, the ideas of CKKS17 all come from the previous scheme. If you understand the previous plan, you can fully understand the plan.

The above articles and electronic resources are available on my homepage :

https://zhigang-chen.github.io/index.html

We will continue to update Blocking; if you have any questions or suggestions, please contact us!