Key Switching Error in CKKS

ng flag

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.