The Beginner’s Textbook
for Fully Homomorphic Encryption

Preface
Contents
I  Basic Math
A-1 Modulo Arithmetic
A-1.1 Overview
A-1.2 Modulo Arithmetic
A-1.3 Inverse
A-1.4 Modulo Division
A-1.5 Centered Residue Representation
A-2 Group
A-2.1 Definitions
A-2.2 Examples
A-3 Field
A-3.1 Definitions
A-3.2 Examples
A-3.3 Theorems
A-4 Order
A-4.1 Definitions
A-4.2 Theorems
A-5 Polynomial Ring
A-5.1 Overview
A-5.2 Coefficient Rotation
A-6 Decomposition
A-6.1 Number Decomposition
A-6.2 Polynomial Decomposition
A-6.3 Approximate Decomposition
A-6.4 Gadget Decomposition
A-7 Roots of Unity
A-7.1 Definitions
A-7.2 Theorems
A-8 Cyclotomic Polynomial
A-8.1 Definitions
A-8.2 Theorems
A-9 Roots of Unity and Cyclotomic Polynomial over Rings
A-10 Vector and Matrix
A-10.1 Vector Arithmetic
A-10.2 Various Types of Matrix
A-10.3 Matrix Arithmetic
A-10.4 Projection
A-10.5 Basis of a Polynomial Ring
A-10.6 Isomorphism between Polynomials and Vectors over Integers
A-10.7 Isomorphism between Polynomials and Vectors over Complex Numbers
A-10.8 Transforming Basis between Polynomial Ring and Vector Space
A-11 Euler’s Formula
A-11.1 Pythagorean Identity
A-11.2 Imaginary Number
A-11.3 Euler’s Formula
A-11.4 Vandermonde Matrix with Roots of Cyclotomic Polynomial over Complex Numbers
A-11.5 Vandermonde Matrix with Roots of Cyclotomic Polynomial over Rings (${\mathbb{Z}}_p$)
A-12 Modulo Rescaling
A-12.1 Rescaling Modulo of Congruence Relations
A-13 Chinese Remainder Theorem
A-13.1 Application: Residue Number System (RNS)
A-14 Taylor Series
A-15 Lagrange’s Polynomial Interpolation
A-16 Efficient Polynomial Multiplication by FFT and NTT
A-16.1 Background and Motivation
A-16.2 Forward FFT (or NTT)
A-16.3 Point-wise Multiplication
A-16.4 Inverse FFT (or NTT)
II  Post-quantum Cryptography
B-1 Lattice-based Cryptography
B-1.1 Overview
B-1.2 LWE Cryptosystem
B-1.3 RLWE Cryptosystem
B-2 LWE Cryptosystem
B-2.1 Setup
B-2.2 Encryption
B-2.3 Decryption
B-3 RLWE Cryptosystem
B-3.1 Setup
B-3.2 Encryption
B-3.3 Decryption
B-4 GLWE Cryptosystem
B-4.1 Setup
B-4.2 Encryption
B-4.3 Decryption
B-4.4 An Alternative Version of GLWE
B-4.5 Public Key Encryption
B-5 GLev
B-5.1 Encryption
B-5.2 Decryption
B-5.3 Lev and RLev
B-6 GGSW
B-6.1 Encryption
B-6.2 Decryption
B-6.3 GSW and RGSW
III  Generic Fully Homomorphic Encryption
C-1 GLWE Ciphertext-to-Ciphertext Addition
C-1.1 Discussion
C-2 GLWE Ciphertext-to-Plaintext Addition
C-3 GLWE Ciphertext-to-Plaintext Multiplication
C-3.1 Gadget Decomposition for Noise Suppression
C-4 GLWE Modulus Switching
C-4.1 LWE Modulus Switching
C-4.2 Example
C-4.3 Discussion
C-4.4 RLWE Modulus Switching
C-4.5 GLWE Modulus Switching
C-5 GLWE Key Switching
IV  Fully Homomorphic Encryption Schemes
D-1 TFHE Scheme
D-1.1 Encryption and Decryption
D-1.2 Homomorphic Ciphertext-to-Ciphertext Addition
D-1.3 Homomorphic Ciphertext-to-Plaintext Addition
D-1.4 Homomorphic Ciphertext-to-Plaintext Multiplication
D-1.5 Homomorphic Key Switching
D-1.6 Homomorphic Ciphertext-to-Ciphertext Multiplication
D-1.7 Coefficient Extraction
D-1.8 Noise Bootstrapping
D-1.9 TFHE on a Discrete Torus
D-2 BFV Scheme
D-2.1 Single Value Encoding
D-2.2 Batch Encoding
D-2.3 Encryption and Decryption
D-2.4 Ciphertext-to-Ciphertext Addition
D-2.5 Ciphertext-to-Plaintext Addition
D-2.6 Ciphertext-to-Plaintext Multiplication
D-2.7 Ciphertext-to-Ciphertext Multiplication
D-2.8 Homomorphic Key Switching
D-2.9 Homomorphic Rotation of Input Vector Slots
D-2.10 Application: Matrix Multiplication
D-2.11 Noise Bootstrapping
D-3 CKKS Scheme
D-3.1 Encoding and Decoding
D-3.2 Encryption and Decryption
D-3.3 Ciphertext-to-Ciphertext Addition
D-3.4 Ciphertext-to-Plaintext Addition
D-3.5 Homomorphic Ciphertext-to-Ciphertext Multiplication
D-3.6 Ciphertext-to-Plaintext Multiplication
D-3.7 ModDrop
D-3.8 Homomorphic Key Switching
D-3.9 Homomorphic Rotation of Input Vector Slots
D-3.10 Contemplation on CKKS Encoding
D-3.11 Homomorphic Conjugation
D-3.12 Sparsely Packing Ciphertexts
D-3.13 Modulus Bootstrapping
D-4 BGV Scheme
D-4.1 Encoding and Decoding
D-4.2 Encryption and Decryption
D-4.3 Ciphertext-to-Ciphertext Addition
D-4.4 Ciphertext-to-Plaintext Addition
D-4.5 Ciphertext-to-Plaintext Multiplication
D-4.6 ModDrop
D-4.7 Modulus Switch
D-4.8 Ciphertext-to-Ciphertext Multiplication
D-4.9 Homomorphic Key Switching
D-4.10 Homomorphic Rotation of Input Vector Slots
D-4.11 Modulus Bootstrapping
D-5 RNS-variant FHE Schemes
D-5.1 Fast Base Conversion: FastBConv
D-5.2 Small Montgomery Reduction Algorithm: SmallMont
D-5.3 RNS-based ModRaise: ModRaise_RNS
D-5.4 RNS-based ModDrop: ModDrop_RNS
D-5.5 RNS-based Modulus Switch: ModSwitch_RNS
D-5.6 RNS-based Decryption
D-5.7 BGV’s RNS-based Modulus Switch: ${\mathsf{\text{𝖬𝗈𝖽𝖲𝗐𝗂𝗍𝖼𝗁}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖦𝖵}}}$
D-5.8 Exact Fast Base Conversion: FastBConvEx
D-5.9 Decomposing Multiplication: DecompMult_RNS
D-5.10 Applying RNS Techniques to FHE Operations
D-6 FHE Scheme Comparison and Summary
D-7 Python Demo FHE Library
References