Polynomials, the Canonical Embedding, and Encoding

CKKS — Polynomials, the Canonical Embedding, and Encoding || Math ∩ Programming

CKKS — Polynomials, the Canonical Embedding, and Encoding #cryptography #ckks #ckks tutorial #homomorphic encryption #programming #mathematics #python 2026-04-29 Table of Contents In this tutorial series, I will introduce the CKKS homomorphic encryption scheme from the ground up, in rather intricate detail. Each article in this series corresponds to a pull request on a GitHub repository. The code for this article is in this pull request. Follow along by cloning the repository and checking out the code at the relevant commit. This first article will cover some of the mathematical background necessary in the formulation of the CKKS encryption scheme, specifically the polynomial ring used in the most basic version of CKKS, and the canonical embedding used to encode cleartext messages as plaintexts. This series will contain plenty of mathematics, but I may abbreviate some verbose definitions, especially those that I would expect to be familiar to readers of this blog (such as the formal definition of a ring). In other words, I’ll assume basic undergraduate mathematics familiarity, with some reminders. A good accompaniment for this series would be The Beginner’s Textbook for Fully Homomorphic Encryption by Ronny Ko, which complements this series in giving more complete (albeit terse) definitions, formulas, and proofs. A brief history of CKKS Some of the terms used in this section may make more sense if you’ve read my high-level technical overview of homomorphic encryption. We will re-cover all of this in detail in future articles. The original CKKS homomorphic encryption scheme was introduced in the 2016 paper Homomorphic Encryption for Arithmetic of Approximate Numbers by Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song as a joint collaboration between Seoul National University and UC San Diego.1 Its primary innovation was to handle approximate arithmetic on real or complex numbers, rather than prior schemes which only handled exact arithmetic on integers. This is relevant in contexts like neural network inference, where the calculations can be inexact and still useful. In particular, CKKS allows the inexactness of fixed-point arithmetic to coexist with the error introduced by the homomorphic encryption scheme itself. After its initial publication, several followup papers made improvements to CKKS that elevated it to the state of the art. First, and most importantly, a bootstrapping procedure was found in 2018 that made CKKS “fully homomorphic.” Subsequent years saw a plethora of additional improvements and variants to CKKS bootstrapping. Experts would even say there are too many variants to keep track of. The second major improvement was the introduction of the residue number system variant of CKKS in 2017. The original CKKS scheme used large integer arithmetic, in particular doing arithmetic modulo hundred-bit or even thousand-bit moduli. Using a residue number system (RNS) allows one to replace the (inherently serial) carry propagation required for large-precision arithmetic with parallel operations on vectors of 64-bit values.2 Combining RNS with bootstrapping produces what, in my view, is the “baseline” version of CKKS that most new works extend or use for contrast. Plaintexts and a polynomial ring The main setting for CKKS is a particular polynomial ring. We start with some ring $R$ of coefficients for the polynomials $R[x]$; sometimes $R$ will be the integers, reals, but more often it will be the field of integers modulo a prime. CKKS is an encryption scheme, and in every encryption scheme there are three distinct spaces: the cleartext space, the plaintext space, and the ciphertext space. Cleartexts describe the atomic message units (e.g., a vector of 32-bit integers of a fixed size). The user must decide how to split their larger program data into cleartext units, say, by chunking. Plaintexts describe preprocessing required to make a cleartext compatible with the encryption scheme. And ciphertexts are the form of the messages after they are encrypted. I spell all this out because, while many encryption schemes don’t have major differences between cleartext and plaintext space, CKKS uses a sophisticated transformation. This article focuses purely on the conversion between the cleartext and plaintext space. Fix a parameter $N$, a power of two, which will be used to define the polynomial ring. A CKKS cleartext is a vector of $N/2$ complex numbers.3 A CKKS plaintext is an element of the ring \[ (\mathbb{Z}/Q\mathbb{Z})[x] \Big / (x^N+1) \]As a reminder, the coefficients $\mathbb{Z}/Q\mathbb{Z}$ form the ring of integers with arithmetic done modulo $Q$. If $Q$ were a prime, this would form a field, but in most cases $Q$ is composite. As a second reminder, the polynomial modulus converts the ring of polynomials mod $Q$ into a quotient ring where two polynomials $p(x)$ and...

Polynomials, the Canonical Embedding, and Encoding

Related Articles

Elevated error rates on requests to multiple models

Donald Trump and sons to be 'forever' exempt from tax audits

PopuLoRA: Co-Evolving LLM Populations for Reasoning Self- Play

Old Reddit Is Down

The ultimate female fantasy – A feminist critique of Beauty and the Beast