Part 3. How does CKKS work?
The mathematical machinery behind CKKS is, surprisingly, a single type of object: the polynomial. The secret key is a polynomial, and every public key and ciphertext is a pair of polynomials. The five fundamental ciphertext operations from Part 2 — along with bootstrapping, key generation, and everything else — are all built from a handful of operations on polynomials.
The reason this works comes down to a hardness assumption called the Ring Learning With Errors (RLWE) assumption: adding a small amount of noise to certain polynomial products makes it computationally infeasible to recover the underlying secret.
By the end of this section, you should have a complete picture of how CKKS works, end to end. We'll cover:
- the seven base operations on polynomials (3.1),
- how vectors of complex numbers are encoded as a polynomial and then encrypted as a pair of polynomials (3.2),
- how the five fundamental ciphertext operations are built from the seven polynomial operations (3.3),
- how to refresh a “used up” (level 0) ciphertext so more computation can be done on it (3.4),
- various optimizations that make the scheme faster (3.5), and
- the protocol that lets multiple parties jointly generate the public keys for a shared secret key without any one of them ever knowing the secret (3.6).