Understand the calculation of the approximate error in CKKS

Library Questions
1

Hello!

I’m playing a little bit with OpenFHE using CKKS scheme. One of the things is to change one bit to the encoding and try to decrypted. Of course because of NTT and RNS this change a lot! But I get this error:

src/pke/lib/encoding/ckkspackedencoding.cpp:535: The decryption failed because the approximation error is too high. Check the parameters.

Going there it gives some info of how this is calculated but I’m still new in this world so I need a little bit of guide to understand it. Some advice to how can I get the knowledge to understand this in a bounded way? Some book/page/post/blog?

The help in question in that cpp is:

     the code below adds a Gaussian noise to the decrypted result
     to prevent key recovery attacks.
     The standard deviation of the Gaussian noise is sqrt(M+1)*stddev,
     where stddev is the standard deviation estimated using the imaginary
     component and M is the extra factor that increases the number of decryption
     attacks that is needed to average out the added Gaussian noise (after the
     noise is removed, the attacker still has to find the secret key using the
     real part only, which requires another attack). By default (M = 1), stddev
     requires at least 128 decryption queries (in practice the values are
     typically closer to 10,000 or so). Then M can be used to increase this
     number further by M^2 (as desired for a given application). By default we
     we set M to 1.
2

One of the things is to change one bit to the encoding and try to decrypted.

Could you explain where you are changing the bit (at which stage of encoding)? Please include the source code that causes this error.

The text you are referring it related to CKKS security for the scenario when decryption results need to be shared. In this case, we add some noise to erase the existing CKKS noise (as an attacker could use it to learn something about the underlying secret key). Internally, this uses the CKKS approximation error estimate derived from the imaginary part of encrypted CKKS vector (which is quite accurate). Then we add extra noise (larger than current approximation noise) that “floods” the CKKS noise.

3

Could you explain where you are changing the bit (at which stage of encoding)? Please include the source code that causes this error.

Basically I take by one polynomial of RNS representation, and take one element of the polynomial (in NTT space), and change one bit of it and continue the pipeline.
I already know that changing one bit in this part will “explode”, making a meaningless decryption, but is not the problem for me.

I didn’t include the source code because my question is more for a guideline for how can I understand all this of the error approximations. I’m really new in all this and want to learn. For example, like you say, OpenFHE uses the imaginary part of encrypted CKKS vector to estimate the error, why?

4

The imaginary part is used to estimate the CKKS approximation error (for accurate noise estimation), which is needed to determine how big the flooding noise should be. This is mitigation for the attack described in On the Security of Homomorphic Encryption on Approximate Numbers, which is relevant when decryption results are shared with other parties. The OpenFHE mitigation is described in Section 5.1 of Securing Approximate Homomorphic Encryption Using Differential Privacy

Various CKKS approximation errors are explained in Approximate Homomorphic Encryption with Reduced Approximation Error