Cred că am înțeles greșit ceva despre limitele derivate pentru eroarea de comutare a cheii în CKKS. Mă voi referi la hârtie inițială, dar limite similare au fost derivate în toate variantele pe care le-am analizat.
Punctul meu special de confuzie este cu $B_{\mathsf{mult}}(\ell)$ (la pagina 12, ca parte a lemei 3), care este definit a fi $P^{-1}q_\ell B_{\mathsf{ks}}$, Unde $B_{\mathsf{ks}} = O(N\sigma)$ Am inteles (aici $N$ este gradul RLWE aproximativ și $\sigma$ este abaterea standard a zgomotului). Confuzia mea este că înțeleg asta
- $q_\ell := p^\ell q_0$ pentru numere întregi fixe $p, q$
- $P$ este descris ca o anumită funcție a $\lambda, q_L$ (acest lucru este descris în algoritmul KeyGen, la pagina 11).
Oricum, cantitatea $B_{\mathsf{mult}}(\ell)$ este prezentat ca fiind destul de mic.
La pagina 14 se precizează că cantitatea
$$p^{\ell'-\ell}B_{\mathsf{mult}}(\ell)+B_{\mathsf{scale}} = O(N)$$
Unde $\ell'$ este un nivel la care trecem în timpul unei înmulțiri.
Din asta, se pare că am avea asta $$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'})$$
Aceasta este aproximativ problema mea --- se pare că $P$ trebuie să fie destul de mare (potențial $\Omega(q_L)$, în funcție de câte niveluri se pierde pe înmulțire), și nu văd nicio discuție reală despre cum să alegi $P$ "destul de mare". Deci intrebarile mele sunt:
În criptosistemul CKKS, cum este constanta $P$ (utilizat la generarea cheii de evaluare) ales? În special, cât de mare este în mod concret (în comparație cu lucruri precum $q$ și $p$, care sunt adesea descrise în mod explicit)?
