CKKS – Addition and Multiplication

Explains CKKS ciphertext addition and multiplication using a simplified 64-bit-modulus implementation (RNS/security ignored) and modular polynomial arithmetic (NTTs used as a black box). Ciphertexts are polynomial pairs (c0, c1) in Z/Q[x]/(x^N+1) that decrypt by dotting with (1, s); for symmetric encryption c0 = -c1·s + m + e. Addition is defined componentwise, (c0 + d0, c1 + d1), which yields an encryption of m_c + m_d with error e_c + e_d. Error sums remain sub-Gaussian so variance parameters add and noise grows linearly; the write-up includes a direct Python implementation and notes on how sub-Gaussian bounds simplify correctness probability estimates.

Multiplication produces a degree-2 ciphertext (t0, t1, t2) = (c0d0, c0d1 + c1d0, c1d1) whose decryption uses (1, s, s^2). The decrypted value equals (m_c + e_c)(m_d + e_d) = m_cm_d + (m_c e_d + e_c m_d) + e_ce_d, so noise includes a quadratic e_ce_d term and linear plaintext-dependent terms scaled by Δ; the raw product has scale Δ^2. This necessitates rescaling (to restore scale and divide down errors) and relinearization (to collapse length-3 tuples back to length-2) for further arithmetic. The post provides code for deg-2 decryption, unit tests showing Δ^2 decoding, and a discussion of practical implications - especially the need to bound intermediate plaintext ranges for reliable error tracking in CKKS.