1
$\begingroup$

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

$\endgroup$

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.