Understanding the CKKS encoding algorithm

FHE Questions
1

I’d like to understand OpenFHE’s choices around the packed CKKS encoding algorithm [1].

My naive understanding of CKKS encoding is that you:

  1. Ensure/extend the input vector to satisfy a conjugate symmetry property
  2. Apply an inverse canonical embedding (via FFT or similar)
  3. The values at this step are guaranteed to be real-valued up to floating point roundoff errors.
  4. Scale by \Delta and round to the nearest integer, putting the values as coefficients to get a polynomial

I noticed a few things about [1]:

  1. No symmetry condition seems to be enforced.
  2. OpenFHE uses the FFTSpecialInv function, which cites Algorithm 1 of [2]. That algorithm appears designed for evaluating coeffToSlot/slotToCoeff homomorphically, not for encoding.

These two appear related, so I’m curious to know how this special FFT is relevant for encoding (if there is anything here besides efficiency of doing operations in-place), and how it compensates for a lack of conjugate symmetry on the input.

[1]: openfhe-development/src/pke/lib/encoding/ckkspackedencoding.cpp at 1306d14f8c26bb6150d3e6ad54f28dfe1007689e · openfheorg/openfhe-development · GitHub

[2]: https://eprint.iacr.org/2018/1043.pdf

1 Like
2

Just my two cents on question 1.: as far as i know extending the input is “mathematically correct” if one uses the standard iDFT using all the roots of unity. On the other hand, one can use the odd powers only to avoid doing the conjugacy on the input (remark that one can obtain half the roots by conjugating the other half as, e.g., \omega_8^5 = \overline{\omega_8^3}, so using them all it’s redundant).

Visually, e.g., the roots in X^4+1 are

\omega_8^1, \omega_8^3, \overline{\omega_8^3}, \overline{\omega_8^1}

so why not using only the first ones

I guess this is simply done for efficiency?

1 Like
3

Thanks! This makes sense to me.

1 Like
4

just be careful as perhaps the used roots might be in the shape \zeta^{5^i} to enable rotations (with \zeta being is a complex primitive 2n root of unity)