CKKS API¶

Data Structures¶

Poseidon Supported parameter data structures, the following is specific to CKKS:

1. CKKS encoding and decoding class : CKKSEncoder ¶

Description: CKKSEncoder is used to encode and decode message for CKKS scheme.

Functions:

CKKSEncoder(const PoseidonContext &context);

context (const PoseidonContext &): The context specified by user, which includes the parameters of homomorphic encryption scheme, polynomial degree and security level.

Usage: Creates a CKKSEncoder instance initialized with the specified PoseidonContext.

void encode(const std::vector<std::complex<double>> &values, parms_id_type parms_id, double scale, Plaintext &destination, MemoryPoolHandle pool = MemoryManager::GetPool()) const;

void encode(const std::vector<double> &values, parms_id_type parms_id, double scale, Plaintext &destination, MemoryPoolHandle pool = MemoryManager::GetPool()) const;

void encode(std::complex<double>, parms_id_type parms_id, double scale, Plaintext &destination, MemoryPoolHandle pool = MemoryManager::GetPool()) const;

void encode(double value, parms_id_type parms_id, double scale, Plaintext &destination, MemoryPoolHandle pool = MemoryManager::GetPool()) const;

void encode(int64_t value, parms_id_type parms_id, double scale, Plaintext &destination) const;

values (const vector<complex>&, const vector\<double>&, std::complex\<double>, double, int64_t): The source number message.
parms_id (parms_id_type): parms_id specifies the modulus level of the modulus chain to of the result plaintext.
scale (double): Scaling parameter defining encoding precision.
destination (Plaintext): The plaintext polynomial to overwrite with the result.

Usage: The packing technique of HE schemes allow us to encrypt multiple messages in a single ciphertext. The encode function encodes either a single complex number or many complex numbers into a plaintext. It appends zeros to the end if the vector size is less than N/2 (N is the polynomial degree).

For a message $z \in \mathbb{C}^{\frac{N}{2}}$ , the coefficients of plaintext polynomial $m(X) = \sum_{i=0}^{N-1}m_iX^i$ can be computed by $m = (U;\overline{U})^T (z;\overline{z})= \frac{1}{N}(\overline{U}^T \cdot z + U^T \cdot \overline{z})$ where $U$ is the $(N/2) ×N$ Vandermonde matrix generated by ${\zeta_j : 0 ≤ j < N/2}$ .

$U = \begin{bmatrix} 1 & \zeta_0 & \zeta_0^2 & \cdots & \zeta_0^{N-1} \\ 1 & \zeta_1 & \zeta_1^2 & \cdots & \zeta_1^{N-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \zeta_{\frac{N}{2}-1} & \zeta_{\frac{N}{2}-1}^2 & \cdots & \zeta_{\frac{N}{2}-1}^{N-1} \\ \end{bmatrix}$

void decode(const Plaintext &plain, std::vector<double> &destination, MemoryPoolHandle pool = MemoryManager::GetPool()) const;

void decode(const Plaintext &plain, std::vector<std::complex<double>> &destination, MemoryPoolHandle pool = MemoryManager::GetPool()) const;

plain (const Plaintext &): The plaintext to be decoded.
destination (std::vector\<double>&, std::vector\<std::complex\<double>>&): A number vector to store the message.

Usage: The decode function decodes a plaintext polynomial into a vector of numbers. The decoding result is fulfilled with zeros to size $N/2$ .

For a plaintext $m \in \mathbb{R}^N$ , the corresponding message $z$ can be computed by $(z;\overline{z}) = (U;\overline{U}) \cdot m$ which is the inverse of encoding.

2. Plaintext matrix class : MatrixPlain ¶

Description: MatrixPlain is a class for storing plaintext matrix information.

MatrixPlain()
        : log_slots(0), n1(0), level(0),
          scale(1.0), rot_index{}, plain_vec_pool{sz, std::map<int, Plaintext>()}, read_idx(0),
          write_idx(0), is_precompute(false)

Members:

LogSlots (uint32_t): Indicates the logarithm to 2 of the number of matrix elements.
N1 (uint32_t): Indicates the number of rows in a matrix.
level (uint32_t): Indicates the level of the ciphertext module chain in which the matrix resides.
scale (double): Indicates the scaling factor of the matrix.
rot_index (vector):Indicates the rotation index of a matrix element in a polynomial.
plain_vec (map):Indicates the polynomial corresponding to the matrix elements.

3. Group of Plaintext matrix in linear transform : LinearMatrixGroup ¶

Description: LinearMatrixGroup is a class for storing a group of plaintext matrix information.

Functions:

LinearMatrixGroup() = default;

Usage: Creates an LinearMatrixGroup instance initialized.

vector<MatrixPlain> &data();

Usage: The function is used to get the vector of MatrixPlain.

vector<int> &rot_index();

Usage: The function is used to get all rotate index.

void set_step(uint32_t step)

step (uint32_t): The number of modulus used during encoding matrix message to plaintext.

Usage: The function is used to set the scaling factor of Matrix Plain. When step is 1, the scaling factor is one modulus.

const int step() const;

Usage: The function get the step.

4. Homomorphic DFT Parameter class : HomomorphicDFTMatrixLiteral ¶

Description: Parameter config class for homomorphic DFT.

Functions:

HomomorphicDFTMatrixLiteral(LinearType type, uint32_t log_n, uint32_t log_slots, 
                            uint32_t level_start, vector<uint32_t> levels, 
                            bool repack_imag_to_real = false, double scaling = 1.0, 
                            bool bit_reversed = false, uint32_t log_bsgs_ratio = 0);

type (LinearType): indicating the matrix type (DFT or IDFT).
log_n (uint32_t): The logarithm of polynomial degree.
log_slots (uint32_t): The logarithm of plaintext slots.
level_start (uint32_t): The start level in modulus chain.
levels (vector): The levels of DFT process.
repack_imag_to_real (uint32_t): Allowing repackage image message to real message ciphertext.
scaling (uint32_t): The scaling factor of HomomorphicDFT process.
bit_reversed (uint32_t): Allow bit reversed (only support false now).
log_bsgs_ratio (uint32_t): The ratio of BSGS matrix (1 is recommend).

Usage: HomomorphicDFTMatrixLiteral class constructs the DFT or IDFT matrix for bootstrapping.

 void create(LinearMatrixGroup &mat_group, CKKSEncoder &encoder,uint32_t step);

mat_group (LinearMatrixGroup &): The LinearMatrixGroup.
encoder (CKKSEncoder &): The CKKSEncoder.
step (uint32_t): The number of modulus used during encoding matrix message to plaintext.

Usage: Create the LinearMatrixGroup object according to the HomomorphicDFTMatrixLiteral parameter.

5. Polynomial class : Polynomial ¶

Description: The polynomial coefficients class in homomorphic polynomial evaluator.

Polynomial(const vector<complex<double>> &data, int a, int b, int max_deg,
           PolynomialBasisType basis_type, bool lead = false)

data (const vector>): the polynomial coeffcients.
a (int): upper bound scope of series expansion
b (int): lower bound scope of series expansion
max_deg (int): the highest degree of polynomial
basis_type (PolynomialBasisType): the polynomial is to be evaluated in Monomial type or Chebyshev type.
lead (bool): whether contains the highest degree term of the polynomial

6. PolynomialVector class : PolynomialVector ¶

Description: A vector of polynomials class in homomorphic polynomial evaluator.

Functions:

PolynomialVector() = default;

Usage: Construct an empty polynomial vector.

PolynomialVector(const vector<Polynomial> &polys, const vector<vector<int>> &indexs, bool lead = true);

polys (const vector &): The Polynomials.
indexs (const vector> &): The indexs of each Polynomial in slots.
lead(bool): Whether is lead or not.

Usage: Construct a polynomial vector.

PolynomialVector(const PolynomialVector &copy) = default;

copy (const PolynomialVector &copy): The Polynomial.

Usage: Copy a given PolynomialVector to the current one.

PolynomialVector(PolynomialVector &&source) = default;

source (Polynomial &&): The Polynomial.

Usage: Moves a given PolynomialVector to the current one

PolynomialVector &operator = (const PolynomialVector &assign);

copy (const PolynomialVector &copy): The Polynomial.

Usage: Copy constructor.

PolynomialVector &operator = (PolynomialVector &&assign) = default;

source (Polynomial &&): The Polynomial.

Usage: Move constructor.

vector<Polynomial>  &polys();

Usage: Gets the Polynomials of PolynomialVector.

vector<vector<int>> &index()

Usage: Gets the PolynomialVector index.

7. Homomorphic Mod polynomial class : EvalModPoly ¶

Description: Parameter config class for homomorphic mod.

Functions:

EvalModPoly(const PoseidonContext &context, SineType type, double scaling_factor, uint32_t level_start, uint32_t                            log_message_ratio, uint32_t double_angle, uint32_t k, uint32_t arcsine_degree, uint32_t sine_degree);

context (const PoseidonContext &): The PoseidonContext.
type (SineType): Cosine Discrete, Sine Continuous or Cosine Continuous.
scaling_factor (double): The scaling factor of HomomorphicMod process.
level_start (uint32_t): The start level in modulus chain.
log_message_ratio (uint32_t): The logarithm of message ratio.
double_angle (uint32_t): The num of double angle.
k (uint32_t): The rang if Chebyshev.
arcsine_degree (uint32_t): arcsine poly degree.
sine_degree (uint32_t): sine poly degree.

Usage: Constructs homomorphic mod parameters.

Evaluation Functions¶

1. Addition between ciphertexts : add¶

void add(Ciphertext &ciph1, Ciphertext &ciph2, Ciphertext &result);

ciph1 (Ciphertext): representing a ciphertext.
ciph2 (Ciphertext): representing another ciphertext.
result (Ciphertext): storing the computation result.

Usage: add computes result = ciph1 + ciph2 .

2. Addition of ciphertext and plaintext : add_plain¶

void add_plain(Ciphertext &ciph, Plaintext &plain,Ciphertext &result);

ciph (Ciphertext): representing the addend.
plain (Plaintext): representing the other addend.
result (Ciphertext): storing the addition result.

Usage: add_plain computes result = ciph + plain .

3. Subtraction between ciphertexts : sub¶

void sub(Ciphertext &ciph1, Ciphertext &ciph2, Ciphertext &result);

ciph1 (Ciphertext): representing the minuend.
ciph2 (Ciphertext): representing the subtrahend
result (Ciphertext): storing the computation result.

Usage: sub computes result = ciph1 - ciph2.

4. Multiplication between ciphertexts : multiply ( only software)¶

void multiply(const Ciphertext &ciph1, const Ciphertext &ciph2, Ciphertext &result) const;

ciph1 (Ciphertext): representing a ciphertext.
ciph2 (Ciphertext): representing the other ciphertext.
result (Ciphertext): storing the computation result.

Usage: multiply computes result = ciph1 * ciph2.

5. Relinearization : relinearize ( only software)¶

void relinearize(const Ciphertext &ciph, Ciphertext &result, const RelinKeys &relin_keys) const;

ciph (Ciphertext): representing a ciphertext.
relin_keys (RelinKeys): representing the relinearization key.
result (Ciphertext): storing the computation result.

Usage: relinearize function performs relinearization operation on the ciphertext.

6. Multiplication between ciphertexts : multiply_relin¶

void multiply_relin(const Ciphertext &ciph1, const Ciphertext &ciph2, 
                    Ciphertext &result, const RelinKeys &relin_key) const;

ciph1 (Ciphertext): representing a ciphertext.
ciph2 (Ciphertext): representing the other ciphertext.
result (Ciphertext): storing the computation result.
relin_key (RelinKeys): A constant reference to a RelinKeys object, representing the relinearization key.

Usage: multiply_relin computes result = ciph1 * ciph2 and relinearize the ciphertext size of result.

7. Multiplication of ciphertext and plaintext : multiply_plain¶

void multiply_plain(const Ciphertext &ciph, const Plaintext &plain, 
                    Ciphertext &result) const;

ciph (Ciphertext): representing a ciphertext.
plain (Plaintext): representing a plaintext.
result (Ciphertext): storing the computation result.

Usage: multiply_plain computes result = ciph * plain.

8. Rescale : rescale¶

void rescale (const Ciphertext &ciph,Ciphertext &result) const;

ciph (Ciphertext): A reference to a Ciphertext object, representing a ciphertext.

Usage: rescale performs a rescaling operation on a ciphertext.

9. Ciphertext rotation : rotate¶

void rotate(const Ciphertext &ciph, Ciphertext &result, 
            int step, const GaloisKeys &galois_keys) const;

ciph (Ciphertext): representing a ciphertext.
result (Ciphertext): storing the ciphertext after row rotation.
rot_step (int): An integer representing the rotation step length; a positive value indicates a left rotation while a negative value indicates a right rotation.
galois_keys (GaloisKeys): representing the galois keys used for row rotation.

Usage: rotate rotates a ciphertext.

10. Conjugation : conjugate¶

void conjugate(const Ciphertext &ciph, const GaloisKeys &conj_keys, Ciphertext &result) const;

ciph (Ciphertext): representing the ciphertext to be conjugated.
conj_keys (GaloisKeys): representing the galois key used for conjugation.
result (Ciphertext): storing the resulting ciphertext after conjugation.

Usage: conjugate transforms the complex elements of ciphertext into its complex conjugate.

11. Matrix multiplication of ciphertext and plaintext : multiply_by_diag_matrix_bsgs¶

void multiply_by_diag_matrix_bsgs(const Ciphertext &ciph, const MatrixPlain &plain_mat, Ciphertext &result, const GaloisKeys &rot_key) const;

ciph (Ciphertext): representing a ciphertext.
plain_mat (MatrixPlain): representing a plaintext matrix.
result (Ciphertext): storing the computation result.
rot_key (GaloisKeys): representing the galois key used for rotations.

Usage: multiply_by_diag_matrix_bsgs multiplies a ciphertext with a plaintext matrix, performing the linear transformation over the ciphertext with the Baby-Step-Giant-Step (BSGS) algorithm to accelerate the operations.

The BSGS algorithm can be performed with the following equation.

$\begin{aligned} A \cdot z & = \sum\limits_{0 \le j \le N_2} \sum\limits_{0 \le i \le N_1} (u_{N_i \cdot j + i} \odot \rho(z;N_1 \cdot j + i)) \\ & = \sum\limits_{0 \le j < N_2} \rho ( \sum\limits_{0 \le i < N_1} \rho(u_{N_1 \cdot j + i};-N_1 \cdot j) \odot \rho(z;i);N_1 \cdot j ) \end{aligned}$

notation:

$A$ denotes the plain matrix

$z$ denotes the ciphertext

$N_1$ is a divisor of $N/2$ and $N_2$ is $N/2N_1$

$\odot$ denotes the Hadamard (component-wise) multiplication between vectors.

$\rho(c;s)$ denotes the rotation of ciphertext $c$ , the rotation step is $s$ .

12. Number Theoretic Transform (forward) : ntt_fwd¶

void ntt_fwd(const Plaintext &plain, Plaintext &result, 
             parms_id_type parms_id = parms_id_zero) const;
void ntt_fwd(const Ciphertext &ciph, Ciphertext &result) const;

plain (Plaintext): representing a plaintext.
ciph (Ciphertext): representing a ciphertext.
id (Ciphertext): target parms_id of plain(only used in BGV and BFV).
result (Ciphertext / Plaintext): storing the transformed plaintext or ciphertext.

Usage: ntt_fwd performs the Number Theoretic Transform(NTT) on a plaintext or a ciphertext.

13. Number Theoretic Transform (inverse) : ntt_inv¶

void ntt_inv(const Ciphertext &ciph, Ciphertext &result) const;

ciph (Ciphertext): representing a ciphertext.
result (Ciphertext or Plaintext): storing the inverse transformed ciphertext or plaintext.

Usage: ntt_inv performs the Inverse Number Theoretic Transform(INTT) on a plaintext or a ciphertext.

14. Multiplication of ciphertext and constant value : multiply_const¶

template <typename T, typename = std::enable_if_t<
                      std::is_same<std::remove_cv_t<T>, double>::value ||
                      std::is_same<std::remove_cv_t<T>, std::complex<double>>::value>>
void multiply_const(const Ciphertext &ciph, T const_data, double scale, 
                    Ciphertext &result, const CKKSEncoder &encoder) const;

ciph (Ciphertext): representing a ciphertext.
constData (double or complex \<double> ): representing a constant or a vector of constant.
scale (double): the scaling factor.
result (Ciphertext): A reference to a Ciphertext object, used to store the computation result.
encoder (CKKSEncoder): A reference to a CKKSEncoder object, representing the encoder and decoder.

Usage: multiply_const computes result = ciph * const.

15. Addition of ciphertext and complex constant : add_const¶

template <typename T, typename = std::enable_if_t<
                      std::is_same<std::remove_cv_t<T>, double>::value ||
                      std::is_same<std::remove_cv_t<T>, std::complex<double>>::value>>
void add_const(const Ciphertext &ciph, T const_data, Ciphertext &result,
               const CKKSEncoder &encoder) const

ciph (Ciphertext): representing a ciphertext.
constData (double or std::complex\<double>): representing a constant or a vector of constant.
result (Ciphertext): storing the computation result.

Usage: add_const computes result = ciph + const_data.

16. Discrete Fourier Transform on ciphertext : dft¶

void dft(Ciphertext &ciph, MatrixPlain& plain_mat,
         Ciphertext &result,const GaloisKeys &rot_key);

ciph (Ciphertext): representing a ciphertext.
matrix_group (LinearMatrixGroup): representing the group of linear matrices used for the DFT.
result (Ciphertext): storing the transformed ciphertext.
rot_key (GaloisKeys): representing the galois key for rotation.

Usage: dft function is used for Discrete Fourier Transform (DFT) of a ciphertext.

17. Dynamic rescale : rescale_dynamic¶

void rescale_dynamic(const Ciphertext &ciph,Ciphertext &result, double min_scale);

ciph (Ciphertext): representing a ciphertext.
result (Ciphertext):representing a ciphertext.
min_scale (double): representing the given scaling factor.

Usage: rescale_dynamic is used for multiple times of rescale of the ciphertext util the scale becomes satisfied with the min_scale.

18. Polynomial evaluation : evaluate_poly_vector¶

void evaluate_poly_vector(const Ciphertext &ciph, Ciphertext &destination, 
                          const PolynomialVector &polys, double scale, 
                          const RelinKeys &relin_key, const CKKSEncoder &encoder) const;

ciph (Ciphertext): representing a ciphertext.
destination (Ciphertext): storing the evaluated ciphertext.
polys (PolynomialVector): representing the given polynomial vector.
scale (double): representing the given scaling factor.
relin_key (RelinKeys): representing the encryption key used for relinearization.
encoder (CKKSEncoder): representing the encoder and decoder.

Usage: evaluate_poly_vector evaluates a polynomial. In detail, the coefficients of Chebyshev or Taylor polynomials are pre-calculated, then the polynomial approximation is calculated.

19. Coefficient to plaintext slot : coeff_to_slot¶

void coeff_to_slot(const Ciphertext &ciph, const LinearMatrixGroup &matrix_group, 
                   Ciphertext &result_real, Ciphertext &result_imag, const GaloisKeys &galoisKeys, 
                   const CKKSEncoder &encoder) const;

ciph (Ciphertext): representing the ciphertext to be transformed.
matrix_group (LinearMatrixGroup): A reference to a LinearMatrixGroup object, representing the group of linear matrices used for the transformation.
result_real (Ciphertext): storing the real part of the transformed ciphertext.
result_imag (Ciphertext): storing the imaginary part of the transformed ciphertext.
rot_key (GaloisKeys): representing the galois key for rotation.
conj_key (GaloisKeys): representing the galois key for conjugation.
encoder (CKKSEncoder): representing the encoder used in the transformation process.

Usage: coeff_to_slot transforms a ciphertext from the coefficient domain to the slot domain. It performs the homomorphic mapping on the ciphertext.

20. Plaintext slot to coefficient : slot_to_coeff¶

void slot_to_coeff(const Ciphertext &ciph_real, const Ciphertext &ciph_imag, 
                   const LinearMatrixGroup &matrix_group, Ciphertext &result, 
                   const GaloisKeys &galoisKeys, const CKKSEncoder &encoder) const;

ciph_real (Ciphertext): representing the real part of the ciphertext to be transformed.
ciph_imag (Ciphertext): representing the imaginary part of the ciphertext to be transformed.
matrix_group (LinearMatrixGroup): representing the group of linear matrices used for the transformation.
result (Ciphertext): storing the transformed ciphertext.
rot_key (GaloisKeys): representing the galois key for rotation.
conj_key (GaloisKeys): representing the galois key for conjugation.
encoder (CKKSEncoder): representing the encoder used in the transformation process.

Usage: slot_to_coeff transforms a ciphertext from the slot domain to the coefficient domain. It performs the inverse homomorphic mapping of coeff_to_slot operation.

21. Evaluate modulo on the ciphertext vector : eval_mod¶

void eval_mod(Ciphertext &ciph, Ciphertext &result, const EvalModPoly &eva_poly, 
              const RelinKeys &relin_key, CKKSEncoder &encoder);

ciph (Ciphertext): representing a ciphertext.
result (Ciphertext): storing the ciphertext after the modular arithmetic.
eva_poly (EvalModPoly): representing the given modular polynomial.
relin_key (RelinKeys): representing the encryption key used for relinearization.
encoder (CKKSEncoder): representing the encoder and decoder.

Usage: eval_mod computes modular arithmetic on a ciphertext $[t]_q$ where $q$ is a modulus much larger than the current modulus. Bounded by $Kq$ , $[t]_q$ could be approximately computed by the series expansion of $\frac{q}{2 \pi} sin(\frac{2\pi}{q} t) + O(\epsilon^3 q)$ .

bootstrap

In Poseidon, it first calculates $P_0(t) = \Delta \sum\limits_{k=0}^{d} \frac{1}{k!} {(\frac{2 \pi i t} {2^r q})}^k$ . Then computes $P_{j+1}(t) = \Delta^{-1} {(P_j(t))}^2$ for $r$ times of iteration to get $P_r(t)$ which is approximately equal to $e ^ {\frac{2 \pi i t} {q}}$ . Finally imaginary part $sin(\frac{2 \pi t}{q})$ is extracted in the by $\frac{P_r(t) - conj(P_r(t))}{2}$ .

bootstrap

22. Bootstrap : bootstrap¶

void bootstrap(const Ciphertext &ciph, Ciphertext &result,
               const RelinKeys &relin_keys, const GaloisKeys &galois_keys,
               const CKKSEncoder &encoder, EvalModPoly &eval_mod_poly)

ciph (Ciphertext): representing a ciphertext.
result (Ciphertext): storing the bootstrapped ciphertext.
relin_key (RelinKeys): representing the encryption key used for relinearization.
galois_keys (GaloisKeys): representing the encryption key used for rotation operations.
encoder (CKKSEncoder): representing the encoder and decoder.
eva_poly (EvalModPoly): representing the given modular polynomial.

Usage: bootstrap is used for bootstrapping. In poseidon library, bootstrap restore the modulus chain to the original level in the RAISE_MODULUS phase. It consumes several levels to perform the following coeff_to_slot, eval_mod, imaginary part extraction and slot_to_coeff operations. If the original modulus level is too small, the ciphertext after bootstrap may be unavailable.

The process of bootstrapping is illustrated in this picture.

bootstrap