Making CKKS Encryption from
Scratch
Problem
CKKS is a homomorphic encryption scheme that supports approximate
computations on encrypted real and complex numbers. It relies on
polynomial arithmetic in the ring
Polynomial multiplication is one of the main computational operations
in CKKS. A naive implementation requires
operations, while the Number Theoretic Transform (NTT) reduces the
complexity to
.
How the algorithm/baseline
code works
The baseline is a serial C++ implementation consisting of three main
components:
- NTT: Implements the forward and inverse NTT using an iterative
Cooley–Tukey algorithm.
- Polynomial multiplication: Performs negacyclic convolution using
NTT, pointwise multiplication, and inverse NTT.
- CKKS: Implements approximate encoding/decoding and RLWE-based key
generation, encryption, and decryption.
For polynomial multiplication, the baseline performs the following
steps:
- Multiply polynomial coefficients by powers of a primitive
-th
root of unity (twisting).
- Apply the forward NTT to both polynomials.
- Multiply the transformed coefficients elementwise.
- Apply the inverse NTT.
- Remove the twisting factors.
Basically, the NTT transforms polynomial multiplication into
pointwise multiplication in the NTT domain, making the computation more
efficient. I also added some tests to check the correctness of NTT
inversion, polynomial multiplication, and approximate recovery of
encrypted plaintexts.
Where is parallelism
The main target for parallelization is the NTT.
- Butterfly operations: Within each NTT stage, butterfly operations
are independent and can be executed in parallel.
- Pointwise multiplication: Each coefficient multiplication is
independent.
- Polynomial multiplication: The forward NTTs of the two input
polynomials can be executed independently.
The main challenge is that NTT stages have data dependencies,
requiring synchronization between stages.