1
$\begingroup$

I want to understand the limits of modulus switching in BFV.

Lets assume $q$ represents ciphertext modulus and $t$ represents plaintext modulus. $q$ is set to a $60$ bit value and $t$ is set to $20$ bits value.

Now we are given a BFV ciphertext $c$ based on above parameter choices. Also assume that due to holomorphic operations, the noise e in $c$ is around $35$ bits.

Now can I switch this ciphertext to modulus $q'$ which is of $30$ bits.

Note switched ciphertext should still be valie as $q'>2t|e'|$, where |e'| is infinity norm of error in switch ciphertext ~ around $5$ bits.

$\endgroup$
5
  • $\begingroup$ What is $e'$ here? The noise of the ciphertext after the modulus switching? How do you compute its norm? $\endgroup$ Commented Apr 9, 2022 at 15:00
  • $\begingroup$ wouldn't infinity norm of $e'$ will be around $5$ bits? $\endgroup$
    – LWE-13
    Commented Apr 9, 2022 at 23:25
  • $\begingroup$ It depends on $N$, the degree of the cyclotomic ring, but usually this norm is larger than 5 bits. $\endgroup$ Commented Apr 10, 2022 at 18:13
  • $\begingroup$ can you refer me to some resource that I could read to know how is it calculated $\endgroup$
    – LWE-13
    Commented Apr 11, 2022 at 20:05
  • 1
    $\begingroup$ I added it as an answer. Hope it will helps you. $\endgroup$ Commented Apr 12, 2022 at 7:13

1 Answer 1

2
$\begingroup$

In short

Consider you are working on the ring $R_Q = \mathbb{Z}_Q[X] / \langle X^N + 1 \rangle$. As a rule of thumb, you have to consider that the noise after modulus switching is larger than $N$. In particular, it will never have only 5 bits, as in your example, because $N$ is typically larger than $2^{13}$ in the FV scheme.

In more detail.

Let's say you have an RLWE ciphertext $c = (a, b) \in R_Q^2$, with $b = a\cdot s + e + (q / t) \cdot m$, as in the FV scheme.

Similarly to what is explained in this answer, but using polynomials instead of vectors, after we perform a modulus switching from $Q$ to some $q$, we get a new ciphertext with noise term given by

$$e' := e \cdot q / Q + \epsilon' + \epsilon \cdot s$$

where both $\epsilon'$ and $\epsilon$ are polynomials with coefficients in the interval $[-1/2,\, 1/2]$.

Usually, it is true that the new error $e'$ is close to the scaled error $e \cdot Q / q$ because the other terms are small compared to this one. However, when the scaled error becomes too small, that is no longer true, as $\epsilon \cdot s$ starts to dominate the norm of $e'$, and this is the "limit of modulus switching". In more detail, the norm of $\epsilon \cdot s$ can be as big as $N \cdot || \epsilon || \cdot || s ||$. So, even using binary or ternary keys (thus $|| s || = 1$), we have $N \cdot || \epsilon || \cdot || s || = N \cdot || \epsilon || \approx N/2$.

$\endgroup$
2
  • $\begingroup$ Thanks yeah its very clear to me now, I missed the rounding errors. So with this information, it looks like we can have $q'$ of around $35$ bits (just to be on safe side) in my above example? $\endgroup$
    – LWE-13
    Commented Apr 12, 2022 at 19:42
  • $\begingroup$ @muhammadharis yes, if $N$ is not too big, this should be good. $\endgroup$ Commented Apr 12, 2022 at 20:16

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.