I believe I am misunderstanding something about the bounds derived for the key switching error in CKKS. I will refer to the initial paper, but similar bounds have been derived in all variants I have looked into.

My particular point of confusion is with $B_{\mathsf{mult}}(\ell)$ (on page 12, as part of lemma 3), which is defined to be $P^{-1}q_\ell B_{\mathsf{ks}}$, where $B_{\mathsf{ks}} = O(N\sigma)$ I understand (here $N$ is the RLWE degree roughly, and $\sigma$ is the noise standard deviation). My confusion is that I understand that

  1. $q_\ell := p^\ell q_0$ for fixed integers $p, q$
  2. $P$ is described as some function of $\lambda, q_L$ (this is described in the KeyGen algorithm, on page 11).

Anyway, the quantity $B_{\mathsf{mult}}(\ell)$ is presented as being fairly small. On page 14, it is stated that the quantity

$$p^{\ell'-\ell}B_{\mathsf{mult}}(\ell)+B_{\mathsf{scale}} = O(N)$$

where $\ell'$ is a level that we switch down to during a multiplication. From this, it seems that we would have that $$p^{\ell'-\ell}B_{\mathsf{mult}}(\ell) = p^{\ell'-\ell}P^{-1}q_\ell N\sigma = O(N)\implies P = \Omega\left(\sigma \frac{q_\ell}{p^{\ell-\ell'}}\right) = \Omega(\sigma q_{\ell'})$$

This is roughly my issue --- it seems that $P$ has to be quite large (potentially $\Omega(q_L)$, depending on how many levels one loses per multiplication), and I see no real discussion for how to choose $P$ "large enough". So my questions are:

In the CKKS cryptosystem, how is the constant $P$ (used in generating the evaluation key) chosen? In particular, how large is it concretely (in comparison to things like $q$ and $p$, which are often explicitly described)?

  • $\begingroup$ Have you managed to figure out the answer of your question. I'm actually having the same question as you. Also, I just wonder whether if P has any relation to the security of the CKKS scheme? $\endgroup$
    – user102060
    Commented May 28, 2022 at 13:55
  • $\begingroup$ @user102060 I haven't. If I were going to investigate this further I'd just check the source of SEAL of PALISADE, but I no longer need the answer. $\endgroup$
    – Mark Schultz-Wu
    Commented May 28, 2022 at 22:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.