Question about encoding process in CKKS

FHE Questions
1

Hello everyone,

I have a question about the CKKS paper. In particular, in the Introduction, after “Encoding Technique for Packing Message”, the procedure transforms our input vector in a polynomial.

I understood why we need to “expand” it using \pi^{-1} and why we scale it, but I did not properly understood why we can’t perform \sigma^{-1} on the resulting vector; we need to “change its coordinates” with respect to a new basis.

Why is this needed?
And also, if I can, why are we using roots of unity as evaluating values for the decoding part? Because of some efficiency reason?

Thank you and sorry for the probably stupid question, I am trying to build a sort of mathematical background :smiley:

2

I suggest reading the following series of posts on CKKS encoding: CKKS explained: Part 1, Vanilla Encoding and Decoding

1 Like
3

Thank you, I am using that series quite a lot :smiley:

In particular, I understood the vanilla de/encoding, but I’ve problems to understand the “changing basis coordinates” part. I have two questions:

  • We want to encode our point into a “lattice” that represent the set of all the possible solutions when evaluating the polynomial on roots of unity, is that correct?

  • I the post the author says "A problem that we face is that we cannot directly use \sigma:R=\mathbb{Z}[X]/(X^N+1)\rightarrow \sigma(X)\subset H, because an element of H is not necessarily in \sigma(R). Why? I think I’m not getting what H is, though…

Thank you very much for your reference!