CKKS — Addition and Multiplication

Table of Contents

This is part of a tutorial series on the CKKS homomorphic encryption scheme.

In the last article, we introduced symmetric and public-key encryption and decryption routines, and implemented modular polynomial arithmetic (using NTTs as a black box). This article covers the addition and multiplication operations performed on ciphertexts (without relinearization).

Again, if you already know about CKKS, we are still avoiding the RNS form of the scheme and using a 64-bit modulus $Q$, which means that we’re momentarily ignoring cryptographic security.

The code for this article is in this pull request.

Reminder of CKKS ciphertext structure

As a quick reminder, CKKS ciphertexts in both the symmetric and public key settings are pairs of polynomials $(c_0, c_1)$ in the ring $(\mathbb{Z}/Q\mathbb{Z})[x] \Big / (x^N+1)$, and while they have different constructions in the symmetric/asymmetric cases, they share the same decryption routine: a dot product with $(1, s(x))$, where $s(x)$ is the secret key polynomial. If the error is sufficiently small, the decoding algorithm will divide by the scale and effectively remove the error.

For symmetric encryption, the structure is

with $c_1(x)$ uniform random, $e(x)$ a discrete Gaussian error polynomial, $s(x)$ the ternary secret key, and $m(x)$ the (encoded) plaintext.¹

For public key encryption, the notation is similar, but $(b, a)$ is a symmetric encryption with the zero polynomial as the “plaintext,” and then $u(x)$ is a new uniform ternary random polynomial, and $e_1, e_2$ are also error polynomials, with the following formulas.

Ciphertext addition

Let’s start with ciphertext addition.

Let $(c_0, c_1)$ and $(d_0, d_1)$ be two ciphertexts decrypting to $m_c + e_c$ and $m_d + e_d$ under the same secret key $s(x)$, respectively. Then the sum of these ciphertexts is defined as $(c_0 + d_0, c_1 + d_1)$. The definition of addition is the same for both symmetric and public-key ciphertexts, though the analysis differs slightly.

For symmetric-key encryption, each of $c_1, d_1$ are random uniform samples, so their sum is also uniformly random.² For $c_0 + d_0$, by definition

And by regrouping,

The non-error parts of the regrouped formula exactly fit the structure of an encryption of $m_c + m_d$. The error part, however is not exactly a Gaussian error sample like a fresh encryption.³

This is the first glimpse we have into the tricky details of CKKS error analysis. As we proceed, we’ll do increasingly complicated operations to ciphertexts, and this error term will be harder and harder to tame analytically, especially when you think of a holistic “CKKS program” as involving arbitrary sequences of additions, multiplications, and ciphertext management operations.

For this reason, a more straightforward way to analyze noise in CKKS ciphertexts is to allow the distribution of the noise term to have the so-called “sub-Gaussian” property. I will defer details to a future post in this tutorial, but for now think of a sub-Gaussian random variable as having a tail that decreases at least as fast as a Gaussian distributed random variable. In particular, bounds like the Chernoff-Hoeffding bound hold for sub-Gaussian distributed random variables, which allows us to say things like, “the error term of this CKKS ciphertext does not exceed $Q/2$ (and hence decrypts and decodes to the right message) with probability at most $2^{-100}$.”

For now, all we need to know is that a sum of two sub-Gaussian random variables is also sub-Gaussian, and their ‘variance’ parameters sum.⁴ I.e., the error does not explode, and instead it grows linearly with the error of the two addends.

As these operations simply require polynomial arithmetic, their implementation is straightforward, in this commit.

from ckks_types import Ciphertext

def add(ct1: Ciphertext, ct2: Ciphertext) -> Ciphertext:
    c0, c1 = ct1.data
    d0, d1 = ct2.data
    return Ciphertext(data=(c0 + d0, c1 + d1))

Ciphertext multiplication

Next we turn to multiplication.

Again let $(c_0, c_1)$ and $(d_0, d_1)$ be two ciphertexts decrypting to $m_c + e_c$ and $m_d + e_d$ respectively. A native attempt to define multiplication might start by assuming some operation produces a ciphertext $(t_0, t_1)$ such that

However, the left and right sides of this equation are polynomials in $s$ that differ in degree: the left side is linear and the right side has a term $s^2$. This can only work if the secret key satisfies a relation like $s^2 = as + b$ for some scalars $a, b$.⁵ Excluding that possibility (see the footnote), the next best thing is quadratic, and here the expression $(c_0 + c_1s)(d_0 + d_1s)$ gives us a natural direction. It expands to

and this can be seen as the dot product of $(c_0 d_0, c_0 d_1 + c_1 d_0, c_1 d_1)$ and a new “key basis” of $(1, s, s^2)$. In other words, we are generalizing our concept of a ciphertext to include three-tuples $(t_0, t_1, t_2)$ that decrypt by a dot product with $(1, s, s^2)$.

The structure of this product can also be seen as a tensor product. The tensor product of the two ciphertexts produces the matrix

and using $(1, s)$ as the input to the corresponding quadratic form $x^TAx$ reproduces the desired decryption.

So we have our candidate “multiplication” operation:

By construction, the “decryption procedure” for the product of two ciphertexts produces the quantity $(m_c + e_c)(m_d + e_d) = m_c m_d + (m_c e_d + e_c m_d + e_ce_d)$.

There are three notable aspects of this expression. First, it contains a product of the operand error terms, implying that multiplication causes error to grow (at least) quadratically. Second, it includes a linear error term that also depends on the plaintext being encrypted (including the scaling factor $\Delta$, which is quite large!). Finally, because the messages are encoded via fixed-point arithmetic, the first term produces a value that has a scaling factor of $\Delta^2$. In other words, if we decrypted without doing anything else, we’d need to tweak our decoding procedure’s rounding and dividing to recover the product of the underlying cleartexts.

Each of these poses a problem we’ll have to account for. Error growth will have to be managed, and we’ll have two methods called “rescaling” and “bootstrapping.” The $\Delta^2$ scale will have to be restored to $\Delta$, in order to permit us to do further arithmetic on other ciphertexts with $\Delta$ scaling factor. This will also be managed via “rescaling.”

Finally, we will have to convert the three-tuple ciphertext structure back into a two-tuple structure. Otherwise, further multiplications (by extending the tensor product idea) would further increase the length of this ciphertext tuple, and this would produce unmanageable large and inefficient operations (i.e., a product of two length-3 ciphertexts would give a length-5 ciphertext). The technique that will handle this is called “relinearization.”

But for the rest of this article, I want to demonstrate these properties of multiplication via code.

First, implementing multiplication is straightforward, in this commit.

from ckks_types import Ciphertext, Deg2Ciphertext

def mul(ct1: Ciphertext, ct2: Ciphertext) -> Deg2Ciphertext:
    c0, c1 = ct1.data
    d0, d1 = ct2.data

    t0 = c0 * d0
    t1 = c0 * d1 + c1 * d0
    t2 = c1 * d1
    return Deg2Ciphertext(data=(t0, t1, t2))

Note the new type, Deg2Ciphertext, which is the same as Ciphertext but with a three-tuple instead of a two-tuple.

Second, we implement decryption of a three-tuple ciphertext in this section of the same commit.

# encryption.py

def decrypt_deg2(
    ciphertext: Deg2Ciphertext,
    secret_key: PrivateKey,
) -> Plaintext:
    t0, t1, t2 = ciphertext.data
    return t0 + t1 * secret_key + t2 * (secret_key * secret_key)

In the tests from that commit, you can see how the decoding process needs to account for the squared scaling factor:

# multiplication_test.py

DEFAULT_ENCODING_PARAMS = EncodingParams(
    scale=2**20,
    poly_modulus_degree=8,
    coefficient_modulus=NTT_64_BIT_PRIME,
)

PRODUCT_ENCODING_PARAMS = EncodingParams(
    scale=DEFAULT_ENCODING_PARAMS.scale**2,
    poly_modulus_degree=DEFAULT_ENCODING_PARAMS.poly_modulus_degree,
    coefficient_modulus=DEFAULT_ENCODING_PARAMS.coefficient_modulus,
)

def test_mul_two_asymmetric():
    message1 = ...
    message2 = ...
    expected = ...

    # encode with Delta
    context = CKKSContext(DEFAULT_ENCODING_PARAMS)

    sk, pk = context.generate_asymmetric_keypair()
    pt1 = context.encode(message1)
    ct1 = context.encrypt_asymmetric(pt1, pk)
    pt2 = context.encode(message2)
    ct2 = context.encrypt_asymmetric(pt2, pk)

    ct_product = context.mul_no_relin(ct1, ct2)
    decrypted_product = decrypt_deg2(ct_product, sk)

    # decode with Delta^2
    decoded_product = decode(decrypted_product, PRODUCT_ENCODING_PARAMS)
    np.testing.assert_allclose(decoded_product, expected, rtol=0, atol=0.2)

Finally, we demonstrate the formula for error growth with a unit test in this commit.

Notes

Before moving on, I wanted to return to a few points from above.

First: recall the error growth depends on the plaintext value. The error part was:

This raises a complication for writing programs in CKKS, because to properly track error growth, you effectively need a bound on the ranges of the intermediate values of variables in your program.

For applications like machine learning, this is not a problem because you can use a validation set to estimate these ranges (and even tighten those ranges to, say, a 1%/99%-ile lower/upper bound, if you’re not worried about outliers affecting accuracy). For general-purpose programs, however, this is a serious limitation of CKKS.

Second: the scaling factor shows up in the error formula. Writing the error formula with the scaling factors visible (now thinking of $m_c, m_d$ as the underlying messages),

One might expect (before the end of this tutorial) that using a smaller $\Delta$ could help reduce the error growth from multiplication. However, the rescaling procedure, which we will cover after relinearization, effectively divides the ciphertext by $\Delta$. This has the dual purpose of restoring the squared scaling factor back to $\Delta$, and dividing the error terms by $\Delta$ as well. Along the way, this removes the $\Delta$ factor from the error formula, so that the error growth becomes (essentially) linear in the operand errors.

Third and finally, I’m not sure how useful it is to dwell on the following question: to what extent should we think of the product of two ciphertexts as a “CKKS ciphertext” insofar as it follows some structural form like the two operand ciphertexts? All we said above was, “you can decrypt them with a dot product.”

But this tuple $(c_0 d_0, c_0 d_1 + c_1 d_0, c_1 d_1)$ is not particularly random. In the symmetric case, you can’t express it as a “generalized RLWE encryption” with a secret consisting of two polynomials. For one, the third component isn’t uniformly random, and $s^2$ isn’t independent from $s$. All that said, what really matters is that the product is secure. If the product had such structure that you could learn about the message $m_c m_d$, then you could use that to crack the original CKKS encryption for the operands.