Score:1

What are limits of Modulus Switching in BFV encryption?

es flag

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.

Hilder Vitor Lima Pereira avatar
us flag
What is $e'$ here? The noise of the ciphertext after the modulus switching? How do you compute its norm?
muhammad haris avatar
es flag
wouldn't infinity norm of $e'$ will be around $5$ bits?
Hilder Vitor Lima Pereira avatar
us flag
It depends on $N$, the degree of the cyclotomic ring, but usually this norm is larger than 5 bits.
muhammad haris avatar
es flag
can you refer me to some resource that I could read to know how is it calculated
Hilder Vitor Lima Pereira avatar
us flag
I added it as an answer. Hope it will helps you.
Score:1
us flag

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$.

muhammad haris avatar
es flag
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?
Hilder Vitor Lima Pereira avatar
us flag
@muhammadharis yes, if $N$ is not too big, this should be good.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.