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
- $q_\ell := p^\ell q_0$ for fixed integers $p, q$
- $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)?
