Scope CKKS parameter selection

[j2kun]

We have discussed CKKS parameter selection for a while, but I wanted to collect some thoughts in an issue to help us decide what to do next.

• CCH+23 noise model is drafted in https://github.com/google/heir/pull/1685
• BCMNT25 noise model/noise estimator discussed in #2011
• We have a SimFHE target from https://github.com/google/heir/pull/1913. if we reworked it a bit we could try to use SimFHE (repeatedly, inside a pass) for estimating cost of a particular choice of parameters, as the basis of a parameter search.
• We will need to find a solution to providing CKKS intermediate value range bounds (https://github.com/google/heir/issues/1700) but can probably get away with hard-coding bounds on the input IR for a specialized domain like ML inference. This is needed to provide an accurate noise estimate.

Maybe if we get a SimFHE-in-the-loop pass working, we could avoid requiring intermediate value bounds and do a naive-ish sweep over the parameter space. One question I have is: if we had intermediate value bounds and a noise model like CCH+23 merged in, would SimFHE still be useful? Or would the analogous parameter selection techniques for BGV/BFV suffice for CKKS?

[j2kun]

CC @JianmingTONG @ZenithalHourlyRate

[Time0o]

I have an issue that I think might be closely related to this. In Optimization of Homomorphic Comparison Algorithm on RNS-CKKS Scheme the authors describe how to determine optimal polynomial degrees for approximating sign(x) (and thus <, max, ReLU) and as I understand it these are dependent on the required "precision" (which I assume in turn depends on the noise level at that point) and the depth consumption that can be tolerated.

If a noise model were integrated would it then be possible to add this to the parameter search space? I think currently polynomial approximation always uses a single polynomial to approximate such operations.

[j2kun]

@Time0o I think the one facet of your remark that we haven't scoped yet is how to determine the required precision, as that depends on the application. If the user provides precision bounds on the input, we might be able to propagate that through the IR...

[Time0o]

@j2kun My understanding of this is a bit rudimentary but I would imagine that if I e.g. want to evaluate a < b that is possible if the possible a's upper bound + noise < b's lower bound - noise or something like that, right? I suppose propagating bounds is simpler than estimating noise.

[ZenithalHourlyRate]

I suppose propagating bounds is simpler than estimating noise.

Just a remark. In CKKS estimating noise is interleaved with propagating bounds as the magnititude of the noise depends on the bound of the message.

Another remark I want to add is that, comparison op of a < b often assumes a, b in [0, 1] (e.g. the paper you posted), which the compiler actually has no information (or only has bad information). A simple example is that, if compiler range analysis find that a, b in [-1000,1000], how would compiler do. Can the compiler normalize it to [-1, 1]? Then what is the definition of precision at this time (we do not know user intention at intermediate place in the circuit) and the requirement for poly approx?

[Time0o]

@ZenithalHourlyRate Thanks that clears it up somewhat, I was also wondering about the [0, 1] bounds in that paper. Maybe the calculations can be adapted to other intervals, iirc they use it there because the polynomial approximation method they use also assumes [-1, 1].

[Time0o]

Maybe also important in this context: With the current polynomial interpretation algorithm it would not be possible to easily determine the required degree even if bounds and noise on the input operands are known, or would it? That seems like it might be an issue in general not just in the context of the paper I linked. Say we propagate bounds and know that a and b are potentially very close (maybe due to noise) and then want to determine a < b. Then we'd have to "guess" what polynomial degree is needed to create a sufficiently sharp sign(x) function with Carathéodory-Féjer.

[ZenithalHourlyRate]

iirc they use it there because the polynomial approximation method they use also assumes [-1, 1].

IMO the whole CKKS literature would assume the input in range [-1, 1]. With the fixed point arithmetic nature, by [-1, 1] we often have things in mind like 0.1, 0.9, etc but not 0.000001, so it is not exactly the range in the mathematical real line.

Say we propagate bounds and know that a and b are potentially very close (maybe due to noise) and then want to determine a < b. Then we'd have to "guess" what polynomial degree is needed to create a sufficiently sharp sign(x) function

I would additionally say that that a b potentially very close would be caused by the circuit that a = complex circuit A and b = complex circuit B and they are suddenly identical for some input (we may have no way to analyse it out), then it would be really hard to get the sign, as 0 evaluates to 0 in most approximation.

The noise compared with the message is usually small, like 2^{-15}.