I  Basic Math
A-1 Modulo Arithmetic
A-1.1 Overview
A-1.2 Modulo Arithmetic
A-1.2.1 Inverse
A-1.2.2 Modulo Division
A-1.2.3 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.1.1 Example
A-5.1.2 Discussion
A-5.2 Coefficient Rotation
A-5.2.1 Example
A-6 Decomposition
A-6.1 Number Decomposition
A-6.1.1 Example
A-6.2 Polynomial Decomposition
A-6.2.1 Example
A-6.2.2 Discussion
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.6.1 Finding Appropriate Modulus $t$
A-10.7 Isomorphism between Polynomials and Vectors over Complex Numbers
A-10.7.1 Isomorphism between ${ℂ}^{\frac{n}{2}}$ and ${\widehat{ℂ}}^n$
A-10.7.2 Isomorphism between ${\widehat{ℂ}}^n$ and $ℝ[X]∕X^n+1$
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-12.1.1 Example
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.2.1 High-level Idea
A-16.2.2 Details
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-2.3.1 In the Case of $t$ not Dividing $q$
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.3.1 Discussion
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-2.1 Discussion
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.6.1 Discussion on the Noise Growth
D-1.6.2 Generalization to GLWE-to-GGSW Multiplication
D-1.7 Coefficient Extraction
D-1.8 Noise Bootstrapping
D-1.8.1 Overview
D-1.8.2 Modulus Switch for Noise Boootstrapping
D-1.8.3 Halving the Plaintext Space To be Used
D-1.8.4 Blind Rotation
D-1.8.5 Coefficient Extraction
D-1.8.6 Noise Bootstrapping Summary
D-1.8.7 Example: Noise Bootstrapping
D-1.8.8 Discussion
D-1.8.9 Application: Gate Bootstrapping
D-1.8.10 Application: Neural Networks 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.2.1 Encoding₁
D-2.2.2 Encoding₂
D-2.2.3 Decoding₁
D-2.2.4 Decoding₂
D-2.2.5 Summary
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.7.1 ModRaise
D-2.7.2 Polynomial Multiplication
D-2.7.3 Relinearization
D-2.7.4 Rescaling
D-2.7.5 Summary
D-2.8 Homomorphic Key Switching
D-2.9 Homomorphic Rotation of Input Vector Slots
D-2.9.1 Rotating Input Vector Slots by Updating the Plaintext Polynomial
D-2.9.2 Updating the Plaintext Polynomial by Updating the Ciphertext Polynomials
D-2.9.3 Summary
D-2.9.4 Encoding Example
D-2.9.5 Rotation Example
D-2.10 Application: Matrix Multiplication
D-2.11 Noise Bootstrapping
D-2.11.1 High-level Idea
D-2.11.2 Modulus Switch
D-2.11.3 Homomorphic Decryption
D-2.11.4 CoeffToSlot and SlotToCoeff
D-2.11.5 Digit Extraction
D-2.11.6 Scaling Factor Re-interpretation
D-2.11.7 Summary
D-3 CKKS Scheme
D-3.1 Encoding and Decoding
D-3.1.1 Example
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.5.1 Synthetic Ciphertext Derivation
D-3.5.2 Relinearization Method 1 – Ciphertext Decomposition
D-3.5.3 Relinearization Method 2 – Ciphertext Modulus Switch
D-3.5.4 Rescaling
D-3.5.5 Comparing BFV and CKKS Bootstrapping
D-3.5.6 Summary
D-3.6 Ciphertext-to-Plaintext Multiplication
D-3.7 ModDrop
D-3.7.1 Difference between Modulus Switch and ModDrop
D-3.8 Homomorphic Key Switching
D-3.9 Homomorphic Rotation of Input Vector Slots
D-3.9.1 Example
D-3.10 Contemplation on CKKS Encoding
D-3.11 Homomorphic Conjugation
D-3.12 Sparsely Packing Ciphertexts
D-3.12.1 Forward Proof: Decoding of Sparsely Packed Ciphertext
D-3.13 Modulus Bootstrapping
D-3.13.1 High-level Idea
D-3.13.2 Mathematical Expansion of the High-level Idea
D-3.13.3 Details: CoeffToSlot
D-3.13.4 Details: EvalExp
D-3.13.5 Details: SlotToCoeff
D-3.13.6 Reducing the Bootstrapping Overhead by Sparsely Packing Ciphertext
D-3.13.7 Summary
D-3.13.8 Reducing the Bootstrapping Noise
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.7.1 Difference between Modulus Switch and ModDrop
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-4.11.1 The Reason for Modulus Switch from $q_l\to \widehat{q}$
D-4.11.2 ModRaise instead of Homomorphic Decryption
D-4.11.3 The Choice of $𝜀$
D-4.11.4 Generalization to $\Delta =p^r$
D-5 RNS-variant FHE Schemes
D-5.1 Fast Base Conversion: FastBConv
D-5.2 RNS-based ModRaise: ModRaise_RNS
D-5.3 RNS-based ModDrop: ModDrop_RNS
D-5.4 RNS-based Modulus Switch: ModSwitch_RNS
D-5.4.1 Comparing ModSwitch_RNS, ModRaise_RNS, and ModDrop_RNS
D-5.5 RNS-based Decryption
D-5.5.1 BFV Decryption: ${\mathsf{\text{𝖣𝖾𝖼}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖥𝖵}}}$
D-5.5.2 CKKS and BGV Decryption
D-5.6 BGV’s RNS-based Modulus Switch: ${\mathsf{\text{𝖬𝗈𝖽𝖲𝗐𝗂𝗍𝖼𝗁}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖦𝖵}}}$
D-5.7 Small Montgomery Reduction Algorithm: SmallMont
D-5.7.1 Improving FastBConv by Using SmallMont
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-5.10.1 Addition and Multiplication of Polynomials
D-5.10.2 Key Switching
D-5.10.3 Input Slot Rotation
D-5.10.4 BFV’s Ciphertext-to-Ciphertext Multiplication
D-5.10.5 CKKS’s Ciphertext-to-Ciphertext Multiplication
D-5.10.6 BGV’s Ciphertext-to-Ciphertext Multiplication
D-5.10.7 BFV’s Bootstrapping
D-5.10.8 CKKS’s Bootstrapping
D-5.10.9 BGV’s Bootstrapping
D-5.10.10 Noise Impact of RNS Operations
D-5.10.11 Python Source Code of RNS Primitives
D-6 FHE Scheme Comparison and Summary