Incorrect Power Basis in Polynomial Evaluation: Rescale Failure to Control Noise? How to Obtain Ciphertext Noise?

[Tokubara]

When performing homomorphic bitonic sorting (which consists of multiple steps, with polynomial approximation being the main computation in each step), I encountered a problem: at a certain step, the input to the homomorphic polynomial evaluation is normal, but the output is completely incorrect. For example, while sorting numbers in the range [0,1], after polynomial evaluation, the values suddenly range in the tens, indicating a completely wrong result.

Let (x) be the input ciphertext to the polynomial evaluation. During the polynomial evaluation, a series of power basis terms (x, x^2, x^4, x^8, x^{16}, \ldots) are computed, following the relationship:
$$x^{2n} = 2x^n \cdot x^n - 1.$$
When I decrypt the power basis ciphertexts (x, x^2, x^4, x^8, x^{16}, \ldots), I observe that the multiplication error increases with the power. At higher powers, the results of multiplication become completely incorrect. For example, decrypting (x^8) and using the relationship above to compute (x^{16}) results in significant discrepancies between the manually computed value and the homomorphically computed (x^{16}) after decryption, indicating that multiplication errors have occurred.

Hypothesis

I suspect that during sorting, the noise grows excessively, and at the problematic polynomial evaluation step, the Rescale operations during the evaluation of power basis fail to effectively control the noise (possibly due to insufficient scaling factors), leading to exponential noise growth and ultimately incorrect multiplication results.

Experiment Plan and Challenges

To validate this hypothesis, I plan to:

1. Obtain the noise of the ciphertext (x).
2. Use noise formulas (or noise models) to predict the noise of (x^2), (x^4), (x^8), etc., and compare these predictions with the actual noise.

However, I face difficulties in both obtaining the noise of a ciphertext and making noise predictions effectively:

• I read Approximate homomorphic encryption with reduced approximation error, which provides noise formulas. However, these formulas are based on polynomials, such as the encoded plaintext polynomial (\mu), while in my work with Lattigo, I only have access to the decrypted and decoded vector, not the polynomial.
• I also read ELASM: Error-Latency-Aware Scale Management for Fully Homomorphic Encryption, which presents a noise model using vectors instead of polynomials. However, it claims that its noise formula originates from Approximate homomorphic encryption with reduced approximation error. The two formulas are not entirely consistent, raising doubts about the validity of the ELASM results. For instance, the relinearization error formula in the first paper is:
  $$|e_{\mathrm{ks}}|^{\text{can}} \leq \frac{8 \sqrt{3} \cdot \text{dnum} \cdot \omega \sigma N}{3P} + \sqrt{3N} + 8\sqrt{\frac{hN}{3}}.$$
  Whereas in ELASM, it is:
  $$\frac{8\sqrt{3}}{3} \sigma l N + \frac{8\sqrt{2}}{3} N + \sqrt{3N}.$$

Questions

1. Is my observed phenomenon (completely incorrect multiplication results in the power basis) likely due to excessive noise growth, where the series of multiplications in the power basis computation causes exponential noise growth due to ineffective Rescale? Or is there a better explanation?
2. How can I obtain the noise of a ciphertext using Lattigo?
3. How can I use the noise of ciphertext (x) to predict the noise of (x^2)? I want to compare the noise in the Lattigo result of multiplication with the noise predicted by the formula to assess their consistency.

If any part of my description is unclear, please let me know, and I’ll provide additional details.

[Pro7ech]

The issue is not the noise. Powers in the thousands should still be relatively accurate when using the Chebyshev power because it is numerically stable and the accuracy loss is only slightly larger than 1 bit per squaring in this case. That is, provided that your ciphertext is well formed (all values are in the expected range and the scaling factor is close to the primes that will be consumed). I have a few hypothesis on what might be going on, but I cannot help you further without a way to reproduce the behavior you are experiencing.

[Tokubara]

Thank you for your reply. Here, I provide the steps to reproduce the issue with sorting.zip.

sorting.go is the source file for homomorphic sorting, where the sorting range is [0, 1]. The corresponding output is in output.txt, which logs the input and output ranges of each step of compare_and_swap (containing the homomorphic polynomial evaluation). The issue arises at step 43: although the input range is normal, the output range of compare_and_swap is incorrect, and the errors accumulate further in subsequent steps.

The main problem seems to be that the scalingFactor is too small (only 27). When scalingFactor is set to 29, the issue does not occur. However, my goal is to understand why a small scalingFactor causes this issue, so that I can determine the minimal scalingFactor required. When LogN = 15 (with a total of 105 steps), the issue persists even with scalingFactor = 40 at step 90+ or slightly over 100. The LogMessageRatio is also set too small in this case, as my primary goal is to reproduce the polynomial evaluation issue. Setting LogN = 10 is intended to reduce runtime as much as possible.

As mentioned earlier, during debugging, I identified that the issue stems from errors in polynomial computations, specifically in the power basis. I saved the decrypted values of the power basis file from one occurrence of the issue (the occurrence is deterministic, but the specific step varies randomly). Using the attached powerbasis.py script for analysis, the output is as follows:

expected[2] range: -0.9999999928869449, -0.9625143490258387
diff[2]: 0.018638933773025057, true diff[2]: 0.018638933773025057
expected[4] range: 0.8661340020319708, 1.03978110868536
diff[4]: 0.004416222405659642, true diff[4]: 0.07329515698264588
expected[8] range: 0.5003770154662512, 1.1568711345010807
diff[8]: 0.0674709138401457, true diff[8]: 0.27244350621864055
expected[16] range: -0.49924558109255, 1.5791634017183869
diff[16]: 0.8853176128645519, true diff[16]: 0.7220212099068561
expected[32] range: -0.9999022412427164, 2.0228715149046654
diff[32]: 7.575690266200164, true diff[32]: 5.118861169185298
expected[64] range: -0.999967847805954, 62.58803808708845
diff[64]: 178.03734650619083, true diff[64]: 115.05762010270007
expected[128] range: -0.9999998767323168, 26687.594806276396
diff[128]: 90550.77941527737, true diff[128]: 63910.07762459286
expected[256] range: -0.9999999974775441, 8169143635.889201
diff[256]: 19316395851.41295, true diff[256]: 11179696563.906868

Here, diff[i] represents the error calculated using the decrypted powerbasis[i>>1] and the formula result[i>>1]**2*2-1, which demonstrates the error for this multiplication. Meanwhile, true_diff[i] is the theoretical error calculated directly using powerbasis[1]. Due to the accumulation of errors across multiple steps, true_diff[i] is larger than diff[i].

If I missed providing any relevant information, please let me know.

[Pro7ech]

Ok, so the issue is way more straight forward than I though.

TLDR

A scaling factor of $\Delta=2^{27}$ is not sufficient to ensure numerical stability as well as well close primes for what you are doing and the only solution (if you want it to work with secure parameters, i.e. a with a larger $N$) is to increase the size of your scaling factor.

More Details

By default you will lose in the order of :

• Encoding: $\approx \log_{2}(2n)$ bits of precision just due to the encoding (the discretization of $\Delta\cdot\text{DFT}^{-1}(v)\in\mathbb{C}^{2n}$ into $\mathbb{Z}^{N}$),
• Squaring: $\approx 1$ to $1.5$ bit of precision per squaring.
• Primes: you will lose $\approx \log_{2}(\Delta/\min(q_{i}))$ bits. For $N=2^{10}$ and $\Delta=2^{17}$ this is negligible, but for $N=2^{16}$ it plays a noticeable role (because primes need to be congruent to 1 mod 2N).

Your degree is 511, so you need 8 squarings to reach $T_{256}(ct)$, that is with $\log_{2}(N) = 10$ (your parameterization) and $n = N/2$, you lose $\approx 18$ bits, i.e. only the $\approx 9$ first bits will be correct after the first iteration.

The issue is that if your values are slightly out of the interval $[-1, 1]$ at anytime during the computation of the powers, they will start to exponentially diverge. The smaller the precision, the higher chance this will happens and the fastest they will diverge, and this exactly is what you are experiencing.

This behavior is reinforced by the fact that your primes are small and the largest the Nth-root, the further they will be off the ideal scaling factor of $\Delta$, thus a stable scaling factor cannot be ensured by the polynomial evaluation algorithm, which amplifies the divergence.

So you want to increase the scaling factor for two reasons: to increase the gap between your values and the error coming from the fixed-point arithmetic and to reduce the ratio $\max(q_{i})/\min(q_{j})$. Note that the smaller the scaling factor, the less primes there are, and thus the further apart primes will be.

[Tokubara]

Thank you for your help and informative reply. It also clarified my confusion about why larger $N$ requires a much larger scaling factor (due to a larger $\log_{2}(\Delta)/\min(q_{i})$ and encoding error). However, I still have several questions:

1. Regarding the estimation of precision bits: if each squaring causes a loss of 1 to 1.5 bits of precision (which, I assume, is independent of $N$?), and sorting involves multiple iterations, where each iteration could result in an 8-bit precision loss, then theoretically, if $\Delta$ is 30 bits, there shouldn't be many significant bits left after just a few iterations. Yet, in practice, $\Delta = 30$ is sufficient to complete 45 iterations with relatively small errors. This is very confusing to me. Additionally, does the precision loss from Encoding and Primes only happen once? In other words, during multiple iterations, is it true that we only need to consider these sources of precision loss once?

2. I still don't understand why multiplication during power basis computation introduces such significant errors. I understand that during power basis computation, the differences can diverge exponentially, but why does a single multiplication cause so much error? For instance, when computing pb[16] from pb[8] (even though pb[8] already has substantial error), theoretically, pb[16] should equal 2*pb[8]**2-1. Yet, the computed pb[16] has a maximum error of 0.8853176128645519 and a root-mean-square error (RMSE) of 0.05992065366096618 compared with 2*pb[8]**2-1. How can such large errors be explained? Is it due to insufficient precision bits?

3. I'm really interested in your method for estimating precision bit loss—it seems very useful. I used to think that an accurate noise model was necessary for precision estimation, but your approach seems simpler and works well. Could you share more information about this method (e.g., a reference paper)?

[Pro7ech]

1. Your circuit has self-correcting properties. For example in your application there is a Chebysehv polynomial that maps values from [-2, 2] to [0, 1], which squishes the error in this interval. If what follows has an error growth that doesn't make the values to fall outside of [-2, 2] before the next call of the polynomial, it will again squish the error and you can do it indefinitely.
2. Fixed point arithmetic isn't friendly to adding two values that have a substantial difference in norm. This is amplified by the fact that arithmetic is effectively carried in the IDFT domain with polynomial convolution. The the standard deviation of this polynomial gets larger (i.e. it has spikes), then it will corrupt smaller values with noise even if they are in different slots.
3. This is the result of one of our work Practical q-IND-CPA-D-Secure Approximate Homomorphic Encryption, which notably has an accurate noise estimator for CKKS. I don't think the estimator is public yet, but it should soon I think since there is a plan to put a new and updated version of the paper online, along with it.