2
$\begingroup$

CKKS is a levelled scheme, because the rescale $\lfloor\frac{x}{\Delta}\rceil$ operation requires truncating a modulus to be efficiently evaluated, and rescale is (usually) needed after every multiplication to control noise growth.

But I don't understand why rescale have to decrease ciphertext modulus. In residue number system it is probably hard to divide without removing ciphertext modulus, but would it be right that under (integer) high precision arithmetic system, we just have to naively divide each coefficient of ciphertext with $\Delta$ (with integer division), hence achieving FHE without need of bootstrapping?

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

If your question is why we don't implement the CKKS scheme in the ring $\mathbb R[X]/(X^n+1)$ rather than $R/qR$ where $R=\mathbb Z[X]/(X^n+1)$, it is because the learning with errors problem can be solved over $\mathbb R$ e.g. by using the linear least-squares method.

Improve this answer
$\endgroup$
5
  • $\begingroup$ No, the scheme is still in integer module q. By high precision arithmetic I mean rather than storing coefficients in Residue Number System (via chinese remainder theorem), store them naively by single number (e.g. BigNum in Java), and perform rescale by naively integer division. $\endgroup$
    – xade93
    Jan 20 at 1:52
  • 1
    $\begingroup$ @xade93 you'll run out of precision eventually. All FHE operations have some "precision loss cost" (ish). The only way known to regain precision is bootstrapping. If you have some fixed computation you want to do though, setting parameters large enough so you can tolerate the precision loss without bootstrapping can be a decent efficiency optimization. $\endgroup$
    – Mark
    Feb 8 at 18:59
  • $\begingroup$ @Mark Oh that makes sense! So is it right to say since error grows at least 1 bit each time, regardless of whether we truncates the LSB or not we can only evaluate linear depth circuit without bootstrapping (with respect to the modulus size). Then we might as well truncate to prevent ciphertext size grow exponentially with depth. Which means the shrink modulus step is not necessary for correctness of bootstrapping, it exists merely to prevent linear growth of ciphertext $\endgroup$
    – xade93
    Feb 13 at 5:39
  • $\begingroup$ Not exactly. Modulus switching was actually first introduced to control noise growth during repeated multiplications. Roughly, often noise grows from $(e, e') \mapsto ee'$. If we first scale both of these down by some intermediate value $p$, this growth becomes $(e/p, e'/p)\mapsto (ee')/p^2$, i.e. linearly scaling down moduli incurs quadratic savings in noise growth. This is somewhat imprecise of course, but it shows the main idea of how it can do more than just give better efficiency. This is also because you can't "infinitely scale up $q$". Larger $q\implies$ less secure LWE $\implies$ $\endgroup$
    – Mark
    Feb 13 at 8:37
  • $\begingroup$ requirements for larger $n$. For any such $q$ you can probably find an $n$ that works, but it is a little complex. $\endgroup$
    – Mark
    Feb 13 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.