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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.