FHE-CKKS Scheme Introduction

# FHE-CKKS Scheme Introduction [TOC] ## Fully Holomorphic Encryption(specific to CKKS scheme) * An post quantum encryption scheme that support mainly 3 operations: * PolyAdd * PolyMul * Rotation * Lattic-based Algorithm essentially * The length of the polynomial is correlated to the security number($\lambda$) * One needs to keep in mind is that the poly operation is element-wise operation * The main time consuming part is the key-switching part(and also the part that generate the erorrs) * The term "Fully" means you can do infinite multiplications in one computation, which in general is not allowed since the error accumulation in the multiplication operation, and in order to realize it, we need to implement *Bootstrapping* operation (which is far more time-consuming compared to Multiplication). * Note that the Module operation is involved in almost everywhere in FHE, therefore, the corresponding algorithms related to module operation are crucial when it comes to FHE. * Barret reduce algorithm * Montgomery reduced algorithm ## FHE Multiplication * element-wise poly multiplication * relinearization(key-switching) * If the RNS is implemented, the Modup and Moddown is involved * rescaling ## Relinearization * key-switching * Need to be done after do the multiplication and rotation * The basic idea: (a0, a1) * (b0, b1) = (a0 * b0, a1 * b0 + a0 * b1, a1 * b1) $\rightarrow$ (c0, c1) ## RNS(residue numeric system) * To deal with the large number operation * To simply put, it is a procedure to divide a large number to several small part to do the operation and compose them based on Chinese Remainder Theorem. ## Bootstrapping * Contain 4 parts: * Modup * Coeff2Slot(Decode) * Exponential Approximation(to approximate the module operation) * Slot2Coeff(Encode) * The most time consuming part is Coeff2Slot (Involve the matrix-vector multiplication) ## Reference [CKKS explained](https://blog.openmined.org/ckks-explained-part-1-simple-encoding-and-decoding/) [Homomorphic Encryption for Arithmetic of Approximate Numbers](https://eprint.iacr.org/2016/421.pdf) [F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption (Extended Version)](https://arxiv.org/pdf/2109.05371) [CraterLake: A Hardware Accelerator for Efficient Unbounded Computation on Encrypted Data](https://people.csail.mit.edu/devadas/pubs/craterlake.pdf)