1
$\begingroup$

I'm trying to implement a naive version of CKKS in Python. It was great until I start implementing the modulus.

For this kind of schemes, the modulus $q$ is in the range $(-q/2,q/2]$. How does this work?

In CKKS paper (I think BGV and others do the same) use something like this (a toy example): $c = m (mod$ $q)$. Where $c$ and $m$ are polynomials, so the coefficients of m are mod q. So c and m are congruent mod q.

So for each coefficient $n$ (if the range of mod is the typical $[0,1,...q-1]$), a way is to solve:

$n = m*q + R$

Where $m$ is the greatest integer that makes $n<m*q$ and $R$ is the remainder that solves the equation being this the same reminder that for c, so n is the result for the coefficient.

But if the modulus range is other like I say, how is this done? The intuition says me that is like wrapping the number in a ''clock'' that starts in -q/2+1 and goes up to q/2 before starting again. But I don't know how to apply this intuition for negative numbers that are smaller than -q/2.

For example which is the answer of -771 (mod 1280)

$\endgroup$

1 Answer 1

-1
$\begingroup$

If you first have some modulus function $x\bmod q$ that always returns a value in $[0, q)$, it is straightforward to switch this to your desired modulus function, for example one can define

$$x\bmod^{\pm} q := (x\bmod q) - \lfloor q/2\rfloor.$$

This is to say that to get a modulus function that returns a value in $[c, c+q)$ rather than $[0,q)$, it suffices to (manually) shift the result of calling the standard modulus function.

$\endgroup$
6
  • $\begingroup$ This was my first attempt and didn't work.... So I have a bug in other please! At least I know that the mod was not the problem. $\endgroup$
    – mmazz
    Nov 19, 2022 at 13:13
  • $\begingroup$ For some programming languages there is a difference between "modulus" and "remainder", usually with how they treat negative inputs. I would try to look into the documentation of your programming language for this, as it is likely the issue. $\endgroup$
    – Mark Schultz-Wu
    Nov 19, 2022 at 20:37
  • $\begingroup$ Thats true. I think that Python %, implementes modulus, so thats its correct. Tell me if what I think its correct. The idea of this congruence in the new interval its that $c\equiv x\pmod q$, its to find witch $c \in (-q/2, q/2]$ has the same modulus that $m \bmod q$? For what I understand $q/2\bmod q=q/2$, but if at that I subtract $q/2$ will give me a wrong answer (for what I understand). What I'm missing? $\endgroup$
    – mmazz
    Nov 21, 2022 at 15:04
  • $\begingroup$ If your issue is one of the rounding boundary, i.e. $(-q/2, q/2]$ vs $[-q/2, q/2)$, you could simply add/subtract 1 from the result as necessary. $\endgroup$
    – Mark Schultz-Wu
    Nov 21, 2022 at 16:14
  • 1
    $\begingroup$ @mmazz: one way to implement $c \in (-q/2, q/2]$ (given a % operation that gives a result in $[0, q)$ is $c = ((x + (q/2-1)) \% q) - (q/2-1)$ $\endgroup$
    – poncho
    Dec 19, 2022 at 19:13

Your Answer

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

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