CKKS — Encryption and Decryption

Table of Contents

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

In the last article, we covered some groundwork about polynomials and the CKKS encoding method. This article covers the encryption and decryption routines.

Notably, if you already know about CKKS, we will deviate from a usual treatment for explanatory purposes. In particular, we will first define CKKS encryption, decryption, and basic operations without using the residue number system (RNS). In a later article we will derive why the RNS form is useful, and then revisit these subroutines to update them for RNS support.

The code for this article is in this pull request.

Prelude: polynomial types, signed representations, and polynomial arithmetic

Last time we showed how CKKS encoding converts a vector of complex numbers in $\mathbb{C}^{N/2}$ to a polynomial with integer coefficients in the ring $(\mathbb{Z}/Q\mathbb{Z})[x] \Big / (x^N+1)$, for some deliberately unspecified choices of $Q$ and $N$, and some scaling factor $\Delta$ to incorporate fixed-point arithmetic. However, our Polynomial class did not quite represent this exactly. In particular, it left out two ingredients that were implicitly satisfied by the encoding process, but which will not be satisfied when we move to ciphertexts.

The first was that the Polynomial class did not enforce any particular representation of mod-$Q$ coefficients. The constructor was

class Polynomial:
    """A univariate polynomial with a ring modulus x^N + 1."""

    def __init__(self, coefficients: np.ndarray, modulus_degree: int):
        ...

Moreover, the encoding parameters had no member variable for $Q$.

@dataclass(frozen=True)
class EncodingParams:
    scale: float
    poly_modulus_degree: int

Related to this, we had no specific choice of representative of the polynomial’s coefficients in this ring. In particular, elements of the ring $\mathbb{Z}/Q\mathbb{Z}$ can be represented by integers in $[0, Q)$, which is often called the standard representative or the unsigned representative. But they can also be represented by integers in $[-Q/2, Q/2)$ (the same as 2’s complement signed integers, when $Q$ is a power of 2), which is called the centered representative or the signed representative.

The difference in signed representation is irrelevant for operations that happen within the ring: the computation results are identical no matter which representative you choose. However, the decoding step is not a ring operation; dividing by the scale and treating the result as a floating point value gives very different results when you use $-1$ or $Q - 1$ as the input. Since the encoding process is done in signed arithmetic, the output of encoding naturally has centered representatives for its coefficients. Hence, decoding must ensure it also accepts centered representatives as input.

So in the first commit, we make this a bit more rigorous as follows: we split the Polynomial class into two. One for ModQPolynomial, in which the arithmetic is always guaranteed to produce coefficients that use the standard representative. And one for IntPolynomial, which allows any integer-valued coefficients. This second class is meant to represent the specific cases where we need a centered representative of a ModQPolynomial, which is only during decoding. That commit includes a small change to the decoding procedure: now it includes a “lift” to the centered representative before dividing by the scale.

def decode(plaintext: Plaintext, params: EncodingParams) -> Cleartext:
    """Decode a CKKS plaintext into a vector of complex numbers."""
    centered_plaintext = plaintext.lift_to_signed_representative()
    scale_removed_coeffs = centered_plaintext.coefficients / params.scale
    unembedded = canonical_embedding(scale_removed_coeffs)
    return unembedded[: params.poly_modulus_degree // 2]

The second issue is that, to support the encryption and decryption routines we’ll introduce in this article, we need to implement basic arithmetic on ModQPolynomial objects. One option is to use the FFT-based tricks from the Negacyclic Polynomial Multiplication article, but a 64-bit FFT has precision issues when we use values larger than roughly $2^{53}$. And even if $Q$ has 31 bits, multiplying a polynomial by $-1$ would produce values on the order of 62 bits (when $-1$ is converted to the unsigned representative). The alternative, and the standard technique used in FHE implementations industry-wide, is to use an integer-exact number theoretic transform (abbreviated NTT).¹ However, I don’t want to discuss the NTT in detail yet. I’ll return to it in a future article. So I’ll just leave it as a commit which implements polynomial multiplication using a standard NTT algorithm. You can treat it as a black box for now, and we will have a lot more to say about it when we turn to performance optimization. This subsequent commit adds the arithmetic functions to ModQPolynomial, as well as makes IntPolynomial compatible with ModQPolynomial (an operation between the two becomes a ModQPolynomial).

Even if we don’t explain how the NTT works yet, using it introduces minor semantic complexity and nontrivial code complexity. For the semantic complexity, it adds a constraint on our parameters: the polynomial modulus degree $N$ must be chosen so that $2N$ divides $Q-1$. We will use a magic constant Q=0x7fffd801 for 32-bit and Q=0x1fffffffffe00001 for 64-bit, and you can read Section 3 of this paper of Satriawan, Mareta, and Lee for more details on NTT-friendly primes.

For the code complexity, computing an NTT involves a number of additional constants that should be precomputed and reused across all NTT invocations. These constants need to be stored somewhere and threaded through the polynomial multiplication API.² To manage this, as well as the growing set of parameters we need to keep track of and validate, we will centralize the API around a class called CKKSContext. The details are in this commit, and the basic API looks like this:

class CKKSContext:

    def __init__(self, params: EncodingParams):
        self.encoding_params = params
        self.ntt_params = ...
        self.encryption_params = ...

    def encode(self, message: Cleartext) -> Plaintext:
        return encode(message, self.encoding_params, self.ntt_params)

    def decode(self, encoded: Plaintext) -> Cleartext:
        return decode(encoded, self.params)

    def encrypt_symmetric(self): ...
    def decrypt_symmetric(self): ...
    def encrypt_asymmetric(self): ...
    def decrypt_asymmetric(self): ...
    def generate_symmetric_private_key(self): ...
    def generate_asymmetric_keypair(self): ...

Ring learning with errors

The basic encryption scheme for CKKS is based on the assumed hardness of a problem called Ring Learning with Errors (RLWE). The details of RLWE are important because the actual CKKS encryption routine is quite close to the pure statement of the RLWE problem itself, and it explains why we bothered to have a plaintext space involving this particular quotient ring.

The intuition behind RLWE is that, while solving a linear system is computationally easy, solving a noisy linear system is computationally intractable.

By noisy I mean that, instead of being presented with a system of linear equations $A \cdot v = b$ where $v$ is unknown and $b$ is constant, you’re presented with $A \cdot v + e = b$ where both $v$ and $e$ are unknown, and $e$ is known to be “small and random” in some precise sense.³ In its raw form, this “noisy linear system” is called Learning with Errors (LWE), and RLWE is a specialization of LWE with some additional structure.

Instead of a linear system $Av = b$ involving a matrix with scalar entries, RLWE supposes we have a polynomial product (in the chosen polynomial ring) of a public and secret polynomial $p(x) \cdot s(x)$, which is then perturbed by a carefully chosen small “noise” polynomial $e(x)$.

The attacker gets to see $p(x)$ and $b(x)$ and wants to learn $s(x)$.⁴ In fact, the attacker gets to see as many random samples of $p(x)$ and $b(x)$ as they want.

I am not going to cover the web of security reductions around this problem and related lattice problems, which are what have led it to be believed to be secure against quantum computers. But what is notable about these reductions is that the hardness of the RLWE problem on random instances has been reduced to the hardness of certain lattice problems on worst case instances.

Next I’ll reformulate the above to be a bit more precise, since the particular details of the randomness and the threat model are conceptually important when considering the use of CKKS in practice.

Definition: Let $Q$ be an integer and $N$ a power of two. Let $R$ be the ring $(\mathbb{Z}/Q\mathbb{Z})[x] \Big / (x^N+1)$. Let $s(x) \in R$ be a ternary⁵ polynomial that is secret. Suppose there is an oracle which can produce pairs of polynomials $(a(x), b(x))$, such that $b(x) = a(x)s(x) + e(x)$, with $a(x)$ having uniform random coefficients, and $e(x)$ having random coefficients drawn from a discrete symmetric Gaussian distribution with standard deviation $\sigma$.

The RLWE problem asks: can a computationally-bounded adversary, when given access to such an oracle, compute $s(x)$?

Some terminology:

• The values $a(x), b(x)$ are often called “RLWE samples,” though sometimes the word “sample” just refers to $a(x)$.
• The value $b(x)$ is sometimes called the “bias,” I guess because people borrow words from statistical machine learning.
• The value $e(x)$ is called the “error polynomial” or “error term.” It represents the intentionally-injected error to hide the secret and/or the message (in the next section we will introduce the message).
• The expression $b(x) - a(x)s(x)$ (which can sometimes be computed without knowing $s(x)$) is sometimes called the “phase” of a sample or problem instance, and is sometimes denoted (also elsewhere on this blog) as $\varphi(x)$.

The details of the secret polynomial distribution are important for this article because it dictates how we generate key material. The distribution for $e(x)$ dictates how we encrypt, and its magnitude relates to how much budget we have to do homomorphic computations before we have to stop or bootstrap.⁶

Next we will see two versions of CKKS encryption and decryption, one for symmetric (secret key only) and one for public key cryptography.

Encryption and decryption (symmetric)

Symmetric key encryption is very similar to the underlying RLWE problem. Suppose $Q$,$N$, and $\sigma$ have been decided in advance so as to provide a certain level of security, which we haven’t learned how to compute yet.

The user generates a secret key $s(x)$ by sampling uniformly random ternary coefficients to form a polynomial of degree $N$. A plaintext $m(x)$ is a polynomial in the ring $R$ as defined in the RLWE problem statement (usually, encoded as per the last blog post).

To encrypt $m(x)$ under $s(x)$, we sample a polynomial $a(x) \in R$ with uniformly random $\mathbb{Z}/Q\mathbb{Z}$ coefficients and an error polynomial $e(x)$ in the discrete Gaussian distribution, and compute

Then we emit as the ciphertext the pair $(b(x), a(x))$.⁷

To decrypt $(b, a)$ under $s(x)$, we compute $b(x) + s(x) a(x)$, which produces $m(x) + e(x)$. Then, provided the encoded scale of $m(x)$ is sufficiently large compared to the error $e(x)$ (which we will scrutinize momentarily), rounding appropriately removes the error and produces $m(x)$.

To implement this in code, first we define some types in this commit.

# ckks_types.py
from polynomial import IntPolynomial, ModQPolynomial

# A private key is a polynomial s(x) with ternary coefficients.
PrivateKey = IntPolynomial


@dataclass(frozen=True)
class Ciphertext:
    """A CKKS Ciphertext.

    Attributes:
        data: A tuple (bias, sample) = (c_0, c_1) where:
            bias (c_0): The encrypted message polynomial combined with error.
            sample (c_1): A uniformly random masking polynomial.
    """

    data: Tuple[ModQPolynomial, ModQPolynomial]

Next, we add a small set of random number generation interfaces to help with testing in this commit.

# rng.py
import abc
import secrets
import numpy as np


class RandomSource(abc.ABC):
    """An interface for random number generation in CKKS."""

    @abc.abstractmethod
    def gen_gaussian_poly(
        self, degree: int, modulus: int, sigma: float = 3.19
    ) -> np.ndarray:
        pass

    @abc.abstractmethod
    def gen_ternary_poly(self, degree: int) -> np.ndarray:
        pass

    @abc.abstractmethod
    def gen_uniform_poly(self, degree: int, modulus: int) -> np.ndarray:
        pass

In particular, we implement this interface three times, once as SecureRandomSource, using secrets.SystemRandom for the underlying rng, (the “production” case), once as SeededRandomSource overriding the underlying rng with random.Random for faster unit testing and allowing a deterministic seed, and once as ZeroNoiseRandomSource, where gen_gaussian_poly returns a zero polynomial. This last one is useful when debugging to ensure the algebraic operations are implemented correctly, as the error polynomial can make it hard to tell what is going on.

But the important one is SecureRandomSource. Here modulus is the coefficient modulus Q, and degree is the polynomial degree N.

class SecureRandomSource(RandomSource):
    """A random source that uses secrets for secure RNG."""

    def __init__(self):
        self.rng = secrets.SystemRandom()

    def gen_gaussian_poly(
        self, degree: int, modulus: int, sigma: float = 3.19
    ) -> np.ndarray:
        return np.array(
            [round(self.rng.normalvariate(0, sigma)) % modulus for _ in range(degree)]
        )

    def gen_ternary_poly(self, degree: int) -> np.ndarray:
        return np.array([self.rng.choice([-1, 0, 1]) for _ in range(degree)])

    def gen_uniform_poly(self, degree: int, modulus: int) -> np.ndarray:
        return np.array([self.rng.randrange(0, modulus) for _ in range(degree)])

Note that the sigma parameter will be something we need to set to achieve a specific security level, but for now we hard-code an arbitrary default.

Next we define the key generation step in this commit.

from ckks_types import PrivateKey
from params import EncryptionParams
import rng


def generate_symmetric_private_key(
    params: EncryptionParams,
    random_source: rng.RandomSource,
) -> PrivateKey:
    return PrivateKey(
        random_source.gen_ternary_poly(params.degree),
        modulus_degree=params.degree,
    )

Finally, we can define the encryption routine in this commit.

@dataclass(frozen=True)
class EncryptionParams:
    degree: int
    modulus: int


def encrypt_symmetric(
    plaintext: Plaintext,
    private_key: PrivateKey,
    params: EncryptionParams,
    random_source: rng.RandomSource,
) -> Ciphertext:
    sample = ModQPolynomial(
        random_source.gen_uniform_poly(degree=params.degree, modulus=params.modulus),
        modulus_degree=params.degree,
        coefficient_modulus=params.modulus,
        ntt_params=plaintext.ntt_params,
    )
    error = ModQPolynomial(
        random_source.gen_gaussian_poly(degree=params.degree, modulus=params.modulus),
        modulus_degree=params.degree,
        coefficient_modulus=params.modulus,
        ntt_params=plaintext.ntt_params,
    )

    bias = -(sample * private_key) + plaintext + error
    return Ciphertext(data=(bias, sample))


def decrypt_symmetric(
    ciphertext: Ciphertext,
    secret_key: PrivateKey,
    params: EncryptionParams,
) -> Plaintext:
    bias, sample = ciphertext.data
    return bias + sample * secret_key

Now this seems reasonable, but a bit of nuance lurks. Last time we emphasized that the scaled message coefficients could not exceed $Q/2$, and now that constraint is slightly worsened because it includes a random, additive error term. If the scaling factor causes messages to come close to Q/2, the added error term could push the coefficients over Q/2 and cause decryption failures. And in particular, we want lots of extra room for the error term to grow, because that allows us more freedom to do homomorphic operations on the ciphertexts before we have to stop and bootstrap. At the same time, the scaling factor $\Delta$ must be sufficiently large to preserve precision necessary for the application. So the scaling factor $\Delta$ gets squeezed between these opposing constraints.

Encryption and decryption (public key)

Public key encryption adds a few more steps, and starts by defining a public-key exactly as an RLWE sample. Again $a(x)$ is a uniformly random polynomial and $e(x)$ is a Gaussian error polynomial. Then we compute

and the public key is $(b, a)$. Public-key generation can also be thought of as encrypting the zero polynomial in the symmetric secret key scheme.

To encrypt, you might think it would suffice to add the message polynomial to $b(x)$. But that would violate a principle of cryptography called probabilistic encryption, which asserts that the same plaintext should encrypt to a different ciphertext (up to randomness) each time the encryption routine is called. There are a number of formal security properties related to this, cf. ciphertext indistinguishability and IND-CPA.

So CKKS encryption starts from the public key $(b, a)$ and computes two new polynomials $(c_0, c_1)$ by sampling a new random ternary polynomial $u(x)$ and two new error polynomials $e_1(x)$ and $e_2(x)$, and computing

We can see by direct computation that the decryption routine is the same as in the symmetric case:

At this point we can see that the remaining error is a sum of three error terms, one of which is multiplied by $s(x)$ and one is multiplied by $u(x)$. This explains, and foreshadows more examples of, why we want the secret key and this auxiliary $u(x)$ polynomial to be ternary: the final error depends on products between existing error terms⁸ and these polynomials. By making them ternary, we can reduce the total norm of the error growth. To rigorously compute these bounds requires us to understand the distribution produced by taking negacyclic polynomial products, which is beyond the scope of this tutorial. But the coarse intuition is that, obviously this will be smaller than if the coefficients were drawn from a uniform distribution. For one, if one multiplicand has small-norm coefficients, it will limit how large the product can grow. And moreover, the negative and positive coefficients on the ternary polynomial will produce some natural cancellation in the product.

This commit has the implementation details.

Putting it all together

The final commit in the PR for this article puts encoding and encryption together in the CKKSContext API, with an example usage in tests:

import numpy as np

from context import CKKSContext
from ntt import NTT_64_BIT_PRIME
from params import EncodingParams
from rng import TestRandomSource


scale = 2**20
message = np.array([1, 2, 3, 4], dtype=np.complex64)
encoding_params = EncodingParams(
    scale=scale,
    poly_modulus_degree=2*message.shape[0],
    coefficient_modulus=NTT_64_BIT_PRIME,
)
context = CKKSContext(encoding_params)

sk, pk = context.generate_asymmetric_keypair()
pt = context.encode(message)
ct = context.encrypt_asymmetric(pt, pk)
decrypted_pt = context.decrypt_asymmetric(ct, sk)
decoded = context.decode(decrypted_pt)

np.testing.assert_allclose(decoded, message, rtol=0, atol=0.2)

The secret key basis

In the previous sections, you may have found it strange that the ciphertext is expressed as $(b, a)$ and the calculation of $b$ involves negating $a\cdot s$.

Given the RLWE problem description above, it seems more natural to define the bias as $b(x) = a \cdot s + m + e$ instead of $b(x) = -(a\cdot s) + m + e$, and to write the ciphertext as $(a, b)$ instead of $(b, a)$. While that is valid, it is more convenient to write the ciphertext as we did above because then the decryption procedure can be viewed as a dot product with $(1, s(x))$. This interpretation will be useful once we see the multiplication of ciphertexts, because that will produce a triple of polynomials which can be thought of as a ciphertext whose decryption routine is a dot product with $(1, s(x), s(x)^2)$.

In other words, the powers of the secret key polynomial $s(x)$ can be thought of as forming a basis. Homomorphic operations will change that basis, and then to continue the program, some “ciphertext management” operation is usually required to restore the usual $(1, s)$ basis. Doing this requires special key material (usually an encryption of the appropriate powers of $s$) and involves a key-switching operation. Moreover, some optimizations lazily defer that key-switching step as long as subsequent operations remain cheap in the nonstandard basis.

Acknowledgements

Thanks to Hongren Zheng and Edward Chen for feedback on a draft of this article.