How can one model the behaviour of CKKS decryption noise?

Question

I am trying to program a simulator for CKKS. It is a "simulator", in the sense that

1. there is actually no encryption involved, but
2. to a person seeing only the plaintexts (before encryption and after decryption) and with knowledge of the oblivious operations performed between them, the simulator is statistically indistinguishable from an actual CKKS implementation.

The reason I need this is that I am trying to design a system that will use quite large amounts of CKKS operations -- much more than I can reasonably run at the moment -- and I want a quick and efficient simulator that I can use to determine at the current design stages that the final system will work properly. I have so far been using a simple simulator that injects no noise into the homomorphic operations, so simply returns the exact true answer when a value is decrypted (if not too many homomorphic operations have been performed). This was great for determining that I'm not using too many operations and that my values will, in the end, be properly decryptable. However, I'm now at a point in my work where I need to be sure that the noise injected by the CKKS algorithm won't make the overall system unusable (despite all ciphertexts being decryptable).

How should I model the noise that my simulator should inject when decrypting? How does this noise change when applying the various homomorphic operations? What is the shape of the noise distribution? (e.g., it uniform in a range? Is it normal?) And how do I compute its scale?

If it makes a difference: my software will ultimately be using the CKKS implementation in the SEAL library, so the simulator should produce (statistically) the same noise as that particular implementation.

Any help would be appreciated. Thanks!

Answer 1

How should I model the noise that my simulator should inject when decrypting? How does this noise change when applying the various homomorphic operations? What is the shape of the noise distribution? (e.g., it uniform in a range? Is it normal?) And how do I compute its scale?

There are certain techniques that people use, but they are in some combination

• overly pessimistic (but provably correct), or
• overly optimistic (e.g. underestimates the size of the error experimentally).

See Costache, Curtis, Hales, Murphy, Ogilvie, and Player for a decent survey of things. They have some heuristics that the noise is approximately Gaussian, though "approximate" here is only in a loose sense. Even after a single multiplication, their data shows that the noise is closer to approximately Gaussian than it is to the worst-case bounds, but there is a (multiplicative) gap in the size of the error of $\approx 2^{6}$, e.g. their heuristic underestimates the size of the error by a large (in my eyes) amount.

You seem mostly interested in this from a usability perspective. It is also important for security in the $\mathsf{IND}\text{-}\mathsf{CPA}^{\mathsf{D}}$ security model. This was first introduced by Li and Micciancio, who noticed that an adversary who can observe

• input ciphertexts $m$,
• computations $C$, and
• approximate homomorphic computations $m' = \mathsf{Dec}_{sk}(\mathsf{Eval}_{ek}(C, \mathsf{Enc}_{pk}(m)))$

may recover the secret key of CKKS. In the context of your problem, this means that the noise distribution that you want to simulate depends on secret information (the secret key $sk$, as well as the (secret) errors of various ciphertexts), and is not simulatable without this information.

If you use an $\mathsf{IND}\text{-}\mathsf{CPA}^{\mathsf{D}}$ secure variant of CKKS (see Li, Micciancio, Schultz-Wu, Sorrell), the noise distribution is now publicly simulatable, but larger. In particular, if you knew the noise of CKKS was at most $\lVert e\rVert_2 \leq t$ before, it grows to size $\approx \sqrt{N_Dn}t2^{s/2}$ for

• $N_D$, the number of decryption queries you will do,
• $n$, the (CKKS) ring degree,
• $s$, a user-selected parameter parameterizing the desired security level. Practically one should probably choose $s\approx 64$ as a rule-of-thumb, but one can choose lower (or higher) $s$ depending on the target application.

There is the caveat that LMSS22 requires (provable, overly pessimistic) bounds on $t$, so $t$ in the above formula is larger than what one might heuristically estimate the error to be.