Score:1

# Key Switching Error in CKKS

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)?