CKKS in FHE for operations on approximate numbers

CKKS

Special thanks to Janmajaya Mall for proofreading and providing valulabe feedback for the article.

FHE enables arithmetic operations, such as addition and multiplication, on encrypted data. Unlike ZK proofs, which is another cryptographic primitive for handling private data, FHE does not involve revealing any information about the plaintext. We are not going to deep dive into their differences. This article will concentrate on CKKS scheme, specifically focusing on the encoding processes utilized in the CKKS scheme. Future discussions will expand into CKKS encryption, decryption and intermediate evaluations methods.

Core Concepts

Lattice-Based Cryptography

Lattices can be thought of as a grid space which is form formed out of random linear combinations of multiple basis vectors. Lattices are fundamental to the security of many FHE schemes, Since it's the basis of hard problems like shortest vector problem and closest vector problem, These hardness problems provides a framework for constructing robust novel encryption schemes which are homomorphic in nature. Among which once of them is CKKS.

Rings and Fields

Understanding the difference between rings and fields is crucial in polynomial arithmetic and integral to the operations within schemes like CKKS.

Rings

A ring is a set equipped with two binary operations addition and multiplication and which follows certain properties which are:

1. Addition is commutative and associative, and there exists an additive identity (often denoted as 0) such that adding this identity to any element of the ring returns the element itself.

2. Addition has inverses: For every element

   $a$ in the ring, there exists an element
   $-a$ such that
   $a+(-a)=0$.

3. Associative Multiplication and Identity: Multiplication is associative and there is a multiplicative identity (often denoted as 1) such that multiplying any element by this identity leaves it unchanged.

Fields

Field are specialised form of rings fields satisfy all the properties followed by ring but in addition Field also has inverses for every non-zero element as well as in field multiplication is commutative whereas in rings it is not.

Cyclotomic Polynomials

These polynomials are essential for defining the ring structure in CKKS, enabling efficient ring operations crucial for encryption and decryption processes.

SIMD Encoding

CKKS uses SIMD encoding to process multiple data points simultaneously within a single operation, enhancing performance in practical applications.

Ring Isomorphisms

In homomorphic encryption, ring isomorphisms preserve algebraic operations such as addition and multiplication between two rings. They are pivotal in transforming data between different algebraic structures without altering the underlying relationships, thereby adapting the data for cryptographic needs.

Introduction to CKKS

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is distinguished by its use of polynomial arithmetic, balancing computational efficiency with robust security. It is particularly well-suited for operations on encrypted data, enabling complex calculations directly on ciphertexts without decryption.

In CKKS, plaintexts are typically vectors of floating-point numbers which are encoded into plaintext polynomials,

$p(X)$. These polynomials are then encrypted using a public key, transforming the plaintext into a secure but operationally capable form.

Unlike many homomorphic encryption methods that approximated integer values through rounding, CKKS inherently supports floating-point arithmetic. This feature is critical because rounding operations in homomorphic encryption are challenging to implement effectively due to their requirement for complex polynomial operations.

Earlier homomorphic encryption schemes often necessitated exponentially large ciphertext moduli to manage error growth, particularly evident in schemes using ciphertexts as matrices of integers or integral polynomials. CKKS introduces an innovative method that incorporates encryption noise as an integral part of the errors occurring during computations.

A key component of CKKS is the rescaling operation, which is crucial for emulating traditional approximate arithmetic on encrypted data. This technique ensures that the size of the ciphertext modulus required grows linearly with the depth of the computation circuit, rather than exponentially. Such linear growth markedly improves the scheme's efficiency, making it highly effective for complex arithmetic circuits.

The design of CKKS enables precise computations on encrypted data, establishing it as an essential tool for privacy-preserving data analysis and secure computation. Its ability to handle floating-point arithmetic with high accuracy and efficiency makes CKKS indispensable in scenarios where data privacy and computational integrity are paramount.

Encoding

Encoding in CKKS scheme is the process of converting the message into the plaintext polynomial. Traditionally, the plaintext space of RLWE-based HE schemes is situated in a cyclotomic polynomial ring

${\mathbb{Z}}_t[X]/({\mathrm{\Phi }}_M(X))$ of finite characteristic.

Key Innovation in CKKS: Polynomial Mapping and SIMD Encoding

A significant advancement in the CKKS encryption scheme is its capability to transform plaintext data, initially encoded into polynomials within the polynomial ring

${\mathbb{Z}}_t[X]/({\mathrm{\Phi }}_M(X))$, into vectors over a complex field by using a ring isomorphism. This transformation happens after encoding the data into polynomials and before encrypting it.

Transformation and Encoding Process:

Data or messages is first encoded into polynomials in the ring

${\mathbb{Z}}_t[X]/({\mathrm{\Phi }}_M(X))$, where

${\mathrm{\Phi }}_M(X)$ represents a cyclotomic polynomial and

$t$ is a modulus.

• SIMD Encoding: Integrates the concept of Single Instruction, Multiple Data (SIMD) by encoding multiple plaintext values into a single polynomial. This technique allows CKKS to process multiple data points simultaneously within a single encryption operation, enhancing computational efficiency.
• Matrix Transformation Using FFT and IFFT: Utilizes Fast Fourier Transform (FFT) and its inverse (IFFT) to transform the polynomials into the frequency domain. This transformation simplifies multiplication operations to element-wise multiplications in the frequency domain, which are computationally less intensive than direct polynomial multiplication.

Technical Implementation of SIMD Encoding:

• Matrix Representation:

  • Define the
    $N$-th cyclotomic polynomial as
    $X^N+1=\prod _{{\omega }_j\in PM}(X-{\omega }_j)$, where
    $(PM)$ is the set of all
    $\frac{N}{2}$ th primitive roots of unity.
  • The transformation matrix
    $U$ and its conjugate
    $\bar{U}$ are used to map a complex vector (
    $z\in {\mathbb{C}}^{N/2}$) to the polynomial space
    $(\frac{R}{X^N}+1)$ by:
    
    $$m=\frac{1}{N}(U{̄}^T\overline{z}+U^{T}z)$$
    where
    $U$ contains the powers of
    ${\zeta }_j$, a primitive
    $N$-th root of unity, and
    $Ū$ contains the powers of
    ${\overline{\zeta }}_j$.

• Efficiency and Practical Application:

  • The use of FFT-like transformations allows for the efficient mapping of vectors to polynomials, reducing computational complexity from
    $O(N^2)$ to
    $O(NlogN)$
  • This encoding is crucial for performing operations in a SIMD manner, enabling the simultaneous processing of multiple data elements within a single encrypted object.

By incorporating both SIMD encoding and FFT-based transformations, CKKS offers an optimized framework for executing complex arithmetic operations on encrypted data with high efficiency and minimal computational overhead. This dual optimization makes CKKS a powerful tool for privacy-preserving computations in resource-intensive applications.

Formally Defining the CKKS Encoding Methodology

CKKS leverages the structure of integer polynomial rings to encode vectors of complex numbers into polynomial forms suitable for encrypted computations. Below, we outline the formal steps for this transformation, using both vanilla and canonical embedding methods.

Mathematical Preliminaries

• Input Vector:
  $z$, a complex number vector in
  ${\mathbb{C}}^{N/2}$.
• Polynomial Representation:
  $z$ is to be encoded into a polynomial
  $m(x)$ in the ring
  $\mathbb{Z}[X]/(X^N+1)$
• Cyclotomic Polynomial:
  ${\mathrm{\Phi }}_M(X)=X^N+1$, where
  $M=2N$.

Encoding Steps for

$O(n^2)$ complexity

Vanilla encoding in the CKKS scheme involves encoding a complex vector into a polynomial representation. Here are the detailed steps and equations used in the encoding process:

Step 1: Define the Input Vector

Let

$z\in {\mathbb{C}}^{N/2}$ be the complex vector you want to encode.

Step 2: Polynomial Representation

The target is to represent

$z$ as a polynomial

$m(X)\in \mathbb{C}[X]/(X^N+1)$.

Step 3: Setup Parameters

• Let
  $N$ be a power of 2, specifically
  $N=2M$.
• Define
  ${\mathrm{\Phi }}_M(X)=X^M+1$, which is the
  $M$-th cyclotomic polynomial. This leads to the polynomial ring
  $\mathbb{Z}[X]/({\mathrm{\Phi }}_M(X))$.

Roots X^4 +1 (source: Cryptography from Rings, HEAT summer school 2016)

Step 4: Canonical Embedding and Decoding

Use the canonical embedding

$\sigma$, which maps a polynomial

$m(X)$ to a vector in

${\mathbb{C}}^N$ by evaluating

$m(X)$ at the

$N$-th roots of unity

${\xi }_i={\xi }^i$, where

$\xi =e^{2\pi i/M}$.

To decode a polynomial

$m(X)$, we define:

$$\sigma (m)=(m(\xi ),m({\xi }^3),...,m({\xi }^{2N-1}))\in {\mathbb{C}}^N$$
Note that

$\sigma$ defines an isomorphism, which means it is a bijective homomorphism, so any vector will be uniquely encoded into its corresponding polynomial, and vice-versa.

Step 5: Encode the Vector to Polynomial

The encoding process involves the inverse of the canonical embedding,

${\sigma }^{-1}$. To encode vector

$z\in {\mathbb{C}}^N$ into polynomial

$m(X)$, solve for the coefficients

${\alpha }_i$ of

$m(X)=\sum _{i=0}^{N-1}{\alpha }_i{X}^i$ such that:

$$\sigma (m)=(m(\xi ),m({\xi }^3),...,m({\xi }^{2N-1}))=(z_1,...,z_N)$$

Pursuing this thread further, we end up with the following system:

$$\sum _{j=0}^{N-1}{\alpha }_j({\xi }^{2i-1}{)}^j=z_i,i=1,...,N$$

Step 6: Vandermonde Matrix

The system can be expressed using the Vandermonde matrix, which is defined as follows:

$$\left[\begin{array}{ccccc}1& {\xi }_1& {\xi }_1^2& \cdots & {\xi }_1^{N-1}\\ 1& {\xi }_2& {\xi }_2^2& \cdots & {\xi }_2^{N-1}\\ 1& {\xi }_3& {\xi }_3^2& \cdots & {\xi }_3^{N-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\xi }_N& {\xi }_N^2& \cdots & {\xi }_N^{N-1}\end{array}\right]$$

This matrix, denoted as

$A$, is used to solve for

$\alpha$:

$$A\alpha =z$$
Where

$A$ is the Vandermonde matrix based on the

$({\xi }^{2i-1})$ for

$i=1,...,N$,

$\alpha$ the vector of polynomial coefficients, and

$z$ the vector we want to encode.

Step 7: Compute Polynomial Coefficients

Solve the linear system using the matrix inversion or other numerical methods to find the coefficients

$\alpha$ which define the polynomial

$m(X)$:

$$\alpha =A^{-1}z$$

Step 8: Verification and Reconstruction

To verify, apply the canonical embedding

$\sigma$ to

$m(X)$ and ensure that it reconstructs the original vector

$z$. Also, the inverse encoding:

$${\sigma }^{-1}(z)=\sum _{i=0}^{N-1}{\alpha }_i{X}^i\in \mathbb{C}[X]/(X^N+1)$$

The above steps outline the encoding of a vector into a polynomial using the canonical embedding in the CKKS scheme for homomorphic encryption.

Error Handling in CKKS encoding

An important aspect of CKKS's security is the deliberate introduction of an error separate from the plaintext space during the encryption process.

But unlike in some other homomorphic encryption schemes, the error in CKKS does not grow exponentially with each operation performed. Instead, it is meticulously controlled through techniques such as rescaling, which helps to maintain the error at a manageable level throughout the computational process.
The plaintext data, represented as an element of a cyclotomic ring of characteristic zero, inherently includes this small error. This is critical for ensuring that while the data remains encrypted, operations performed on the ciphertext result in accurate and secure outcomes when decrypted.

In addition to sophisticated error management, CKKS also utlizes techniques to ensure the preservation of polynomial size during cryptographic operations:

• The complex canonical embedding map is a type of isometric ring homomorphism, which ensures that operations within the ring preserve distances and thus the magnitude of polynomial coefficients.
• By preserving the size of the polynomials, this mapping technique helps prevent the escalation of the small error introduced during the encoding or decoding processes. This is crucial for maintaining the accuracy and security of the computations, as any significant increase in error could compromise the integrity of the decryption results.

$$\begin{gathered} H=(z_j{)}_{j\in {\mathbb{Z}}_M^{\ast }}:z_{-j}=z_j,\mathrm{\forall }j\in {\mathbb{Z}}_M^{\ast } \\ \subset {\mathbb{C}}^{\varphi (M)} \end{gathered}$$

Here,

$H$ is a set of sequences or tuples of complex numbers that exhibit a specific symmetry: each element indexed by

$j$ is identical to its counterpart indexed by

$-j$.

In actual encoding, the native plaintext space of our scheme is the set of polynomials in the cyclotomic ring

${\mathbb{Z}}_t[X]/({\mathrm{\Phi }}_M(X))$ bounded by the ciphertext modulus. The decoding procedure transforms a plaintext polynomial

$m(X)\in R$ into a complex vector

$(z_j)\ast j\in \mathbb{Z}\ast M^{\ast }\in H$ using the inverse of canonical embedding map(vandermond matrix). It then projects this vector to

$(z_j)\ast j\in T$ using the natural projection

$\pi :H\to {\mathbb{C}}^{\varphi (M)/2}$. The encoding method is nearly the inverse of this decoding process, but includes a rounding algorithm for discretization to yield an integral polynomial. In summary, our encoding function is represented as:

where

$\lceil \cdot {\rfloor }^{(R)}$ denotes rounding to the nearest element in

$\sigma (R)$.

Conclusion

In this article we tried to cover the background of CKKS scheme, along with how to perform encoding in CKKS scheme in next sets of article we will discuss more about encryption, decryption, rescaling etc.

If you find any mistakes or unexpected results, please contact me on Telegram(@rishotics).