CKKS Decoding, Conjugate sum

Library Questions
1

Hi!

I’m stuck on a part of the CKKS decoding process. I understand that the step I’m describing is done for security reasons, and I’m not questioning why it’s necessary, but rather how it still allows us to obtain the correct result.

From what I understand, for the encoding (skipping scaling and other details), given a complex vector of size n, an IFFT is applied. The result is then expanded into a polynomial of degree N by separating the real and imaginary components.

To decode, we reverse the process to recover a complex vector of size n, denoted as m(x). After this, the conjugate function is applied, yielding m(1/x). Then, by summing m(x) + m(1/x) and performing an FFT on the result, we obtain the correct answer (again skipping some scaling factors).

Could someone help me to clarify why this works? I’m missing something? Some property?

2

Looks like you are referring to this part in OpenFHE?

The added Gaussian noise does not affect the most significant bits of the message. It only affects the noise which lives in the least significant bits of the message. Hence, the message is not significantly affected but the original noise is flooded. Subtracting (rather than summing) the conjugate from the message is to find the imaginary part, which includes the accumulated noise in the ciphertext as a result of the computation. The ciphertext noise is needed to estimate the magnitude of the flooding noise that needs to be added to the message.

More on noise flooding can be found in the resources below:

  1. Securing Approximate Homomorphic Encryption Using Differential Privacy
  2. Appropriate error parameters for the noise flooding - #5 by Nick_Genise
3

Yes, but more specifically, I’m referring to this section.

Trying to formulate this response I answer my own question. I still have one.

I was struggling too understand what m(1/x) represents. Basically, given the coefficients of m(x), which then are evaluated at the roots of unity, m(1/x) simply means that we are evaluating at 1/(root of unity), right?
Then because of ComplexConjugate(root of unity) [with reverse index] = 1/(root of unity).

so given z the values that we obtaint when we evalute m(x) with the roots of unity:

\mathbf{m} = (m_1, m_2, m_3, m_4, m_5, m_6, m_7, m_8)

Openfhe makes the vector to be transform with the FFT like:

\mathbf{m'} = (m_1 + i m_5, m_2 + i m_6, m_3 + i m_7, m_4 + i m_8)

So when we apply the Conjugate function of Openfhe:

\mathbf{m''} = (m_1 + i m_5, -m_8 - i m_4, -m_7 - i m_3, -m_6 - i m_2)

And finally if we transform it to a flat vector:

\mathbf{m'''} = (m_1, -m_8, -m_7, -m_6, -m_5, -m_4, -m_3, -m_2, -m_1)

Given the property of the roots of unity, evaluating the polynomial at 1/(root of unity) yields the complex conjugate of Z. Subtracting them results in 2Im⁡.

However, why does adding the conjugate \mathbf{m'''} to \mathbf{m} yield the same result when applying the FFT? Is it because we obtain 2Re(Z) and are only interested in the real part since OpenFHE does not support complex encryption? If so, why not simply use \mathbf{m}?

4

The logic that is implemented in OpenFHE is described in Section 5.1 of Securing Approximate Homomorphic Encryption Using Differential Privacy (see especially the paragraph after the main procedure). The high-level idea is that the noise is added before decoding, and then decoding is done for the message with extra noise added. StdDev is computed using m(X) - m(1/X), corresponding to the imaginary part. What is decoded is computed using m(X) +m(1/X), which corresponds to the real part. I also suggest carefully looking through the code-level comments for StdDev.