Introduction
First of all, what is FHE? The basic idea is to allow a third party, like a remote server, to perform computations over your data without giving the server access to it. To do so, we provide this third party with an encrypted version of our data so that it can perform encrypted operations. When the server is done with the computation, it returns the encrypted result, which is to be decrypted by the original owner of the data. Learning how this is all done is a challenge. For a slightly deeper overview, read the first paragraphs of this Wikipedia article or part 1 of this blog post.
Math and cryptographic concepts
How can we start approaching the world of FHE? First, you need to learn some basic concepts like algebraic group, ring, and group and ring homomorphism. These are pure math subjects that will build a solid base for a better understanding of the topics that follow. It will also help to be familiar with symmetric and public-key cryptography, specifically focusing on RSA for now. There are a lot of resources where you can learn these basic concepts, but An Introduction to Mathematical Cryptography by Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman is a great book to start with. You don’t have to read every chapter—focus on things you don’t know. A non-exhaustive list of sections for these topics is:
- 1.3 Modular Arithmetic
- 1.5 Powers and Primitive Roots in Finite Fields
- 1.7 Symmetric and Asymmetric Ciphers
- 3.2 The RSA Public Key Cryptosystem
For a deeper look at algebra concepts like groups and rings, I recommend the algebra section (chapter 4) of The MoonMath Manual.
Homomorphic Encryption and Noise
The first step to understanding Fully Homomorphic Encryption is to understand Partial Homomorphic Encryption (or just Homomorphic Encryption), a basic form of FHE where the server can perform only one kind of operation over encrypted data (usually addition or multiplication alone). A great example is RSA, where you can perform arbitrary multiplications over encrypted data. But before that, you should learn some basic definitions like Homomorphic Encryption from the book Homomorphic Encryption and Applications by Xun Yi, Russell Paulet, and Elisa Bertino, in particular sections:
- 1.3.2 RSA
- 2 Homomorphic Encryption
- 2.1 Homomorphic Encryption Definition
These pages provide a solid base for you to understand what makes a cryptographic system homomorphic, and with that knowledge, I recommend you apply the definition you just learned to RSA encryption and infer that it’s effectively homomorphic over multiplication. Moving on, read the definition of Fully Homomorphic Encryption (finally!) from section 3 to section 3.2. At this point, the definition should feel intuitive for you, but remember we’re just beginning. Things start to get a bit messy here. Read sections:
- 3.3 Somewhat Homomorphic Encryption Scheme over Integers
- 3.3.1 Secret Key Somewhat Homomorphic Encryption
The important thing you should take from this cryptographic system is the idea of noise, and why you cannot perform an arbitrary number of encrypted multiplications in this scheme. This may take a while and many re-reads to convince yourself, but it’s important to grasp this concept because even though noise will take many forms depending on the system, the key idea is always the same.
Lattices, Learning With Error and modern FHE
At this point, maybe you’re tired of reading, but don’t worry, we’ll continue with some videos. Now we’ll move to the field of lattice and Learning With Errors (LWE) cryptography. For an introduction to lattices, watch this video. It doesn’t matter if you don’t fully understand it, it’s only to gain an intuition of lattices and justify what comes next. The following video is about Learning With Errors, and in this case, I would suggest you watch it as many times as you need because the intuition behind this is really important. You may think it’s weird this isn’t really related to FHE directly, but the tools this cryptographic system uses are similar to the ones we’ll use next when we move to Torus FHE. To start, I recommend watching this video until the end. Many things will sound familiar, and others won’t, but hopefully, it will smooth the ground for the final track.
Here’s the really hard part, now I’ll let you deep dive into this series of blog posts by Zama, where they explain Torus FHE (a modern and implemented FHE scheme) in depth, with a special focus on understanding Programmable Bootstrapping.
That’s all for now, I hope this was helpful. I don’t know if it’s the best path to learn FHE, but it was the one I took. You can also start playing with Concrete, the FHE framework implemented by Zama. Good Luck!
