I have some difficulty in understanding how BGV’s modulus switching can preserve correctness after cipher-cipher multiplication. Suppose we have two BGV ciphertexts encrypting the following:
If we multiply them, the result encrypts:
M1M2 + t*(M1E2 + M2E1) + t^2(E1E2)
We can do modulus switch by multiplying by q’/q, where I suppose q’/q =1/ t. After modulus switching, we get a ciphertext that encrypts the following:
M1M2/t + (M1E2 + M2E1) + t*E1E2
The error got reduced from “t*(M1E2 + M2E1) + t^2(E1E2)” to “(M1E2 + M2E1) + t*(E1E2)”. However, The plaintext got corrupted from “M1M2/t” to M1M2". Also, the error “(M1E2 + M2E1)” gets mixed into the plaintext area. This is not a valid ciphertext that encrypts M1M2. because if we do modulus reduction on “M1M2/t + (M1E2 + M2E1) + t*E1E2”, we don’t get M1M2.
I wonder if someone could explain where my understanding when wrong.
There is a lot to unpack here, but the complete story can be drawn from these two resources: BGV and GHS. I highly recommend reading both papers if you are interested in BGV. And if you want to understand how BGV is implemented in OpenFHE, this work is recommended.
As shown in the BGV paper, the factors (q_0, q_1, \ldots, q_L) of the ciphertext coefficient modulus are chosen such that q_i \equiv~1 \pmod{t}. This way, the message (which lives in \mathbb{Z}_t) does not get affected by scaling - since you are, sort of, scaling by 1.
There are also different ways of implementing BGV multiplication to resolve that issue and enable efficient modulus switching, do refer to the referenced papers for further details.
Thanks a lot for your useful resources and explanations. I read the original BGV paper, and I understand the part that each q_i ≡ 1 mod t. However, I don’t understand why this property leads to the fact that scaling factor to the plaintext is 1. If we rescale a ciphertext from modulus q5 to q4 for example, then we have to multiply the ciphertext components by q4/q5. Then, the multiplied ciphertext’s plaintext value:
I don’t understand why the scaling factor applied to (q4/q5)M1M2 is practically 1M1M2 mod t. Do you mean that q4/q5*M1M2 ≡ M1M2 mod t? I don’t understand why this is true. Since q4 ≡ q5 ≡ 1 mod t, we can mathematically re-write q4 and q5 as follows:
q4 = 1 + k4t (for some integer k4)
q5 = 1 + k5t (for some integer k5)
However, q5/q4M1M2 = (1 + k5t) / (1 + k4t)M1M2 is not necessarily M1M2 mod t, I think, because the rounded value of (1 + k5t) / (1 + k4t) is not necessarily 1 mod t. For example, the rounded value of (1 + k5t) / (1 + k4t) could be 0, and then this value is not equal to 1 mod t. Or is it that I am misunderstanding how rescaling works in BGV?
Start with a set of small primes: q_0,q_1,\ldots,q_L;
Compose the ladder of moduli, one moduli for each level i as, Q_i=\Pi_{j=0}^iq_j.
Modulus Switching switches the ciphertext from modulus Q_j to modulus Q_i with i<j and results in an encryption of Q_i/Q_j\cdot m \pmod{t}. Note Q_i|Q_j and you will end up with something like 1/q_{j}\cdot m\pmod{t}, if i and j are consequtive.
Thanks for your reply again and I understand that after modulus switch from Q_j to Q_i, the plaintext portion will be updatd from m (mod t) to m/q_j (mod t). In other words, the plaintext portion will be updated from m + kt (for some integer k) to m/q_j + kt/q_j. However, m/q_j + kt/q_j (mod t) is not the same as m + kt mod t. For example, suppose the following:
m = 10
t = 23
Q_i = 47
Q_j = 4770
Then,
Q_i mod t = 47 mod 23 = 1
Q_j mod t = 4770 mod 23 = 1
t is a prime number
However:
m/q_j + kt/q_j mod t = 10/70 + 0 mod t = 1/7, which is not m (=10).
So, I don’t understand why 1/q_j * m (mod t) is equal to m.
I think what you are saying is that if:
Q_i mod t ≡ Q_j mod t ≡ 1
, then:
m * Q_i * Q_j^{-1} mod t ≡ m * 1 * 1 mod t ≡ m mod t
The above is true. However, modulus switching is not the same as multiplying Q_i * Q_j^{-1} to m modulo t, but numerically multiplying the decimal value Q_i / Q_j to m and rounding it to the nearest integer (if the modulus switching formula works the same way as the one for BFV). Since Q_i < Q_j, Q_i/Q_j will be some decimal value smaller than 1, and thus ROUND(m * Q_i/Q_j) will be some value smaller than m. Therefore, ROUND(m * Q_i/Q_j) modulo t is not m (although m * Q_i * Q_j^{-1} ≡ 1 mod t). In order to get correct decryption after modulo switching from Q_j to Q_i, the following should be true:
[ [ ROUND(m * Q_i / Q_j) ]_{Q_i} ]_t = m.
However, I think the above is not true, because ROUND(m * Q_i / Q_j) is some value smaller than m, and thus modulo-reducing ROUND(m * Q_i / Q_j) by t is some value smaller than m.
Hopefully, there will be some part that I am mis-understanding how BGV modulus rescaling works, but I don’t know where I went wrong…
Please read the BGV paper more carefully. The scale operation is defined in Definition 6. You must ensure that the coefficients of the ciphertext are exact multiples of the scaling factor (what you divide by). You can do that by adding multiples of the plaintext modulus (denoted by r in the paper).
Or find the exact multiple of the plaintext modulus for each coefficient c_j as follows: -c_j \cdot InverseMod[t,q_i]\pmod{q_i}
Note that, AFAIK, almost all existing implementations of BGV implement the variant in the GHS paper.
I am sorry for my slow understanding. I carefully reviewed the paper and I think now I fully understand it. I provided a step-by-step proof on why ((A, B) \bmod q_{l}) \bmod t = ((A', B') \bmod q_{l-1}) \bmod t = m, which is slightly more detailed than the paper. Please correct me if this is wrong anywhere.
BGV Background
n-degree Plaintext Polynomial:M
n-degree Noise Polynomial:E
n-degree Ciphertext Polynomials:A, B
Plaintext Modulus:t, which is some power of some prime
Ciphertext Modulus Ladder:q_l = p_0\cdot p_1\cdots \cdot p_l
, where each p_i is a prime (to use CRT) and p_0 \equiv p_1 \equiv p_2 \equiv \cdots \equiv p_l \equiv 1 \bmod t
Half Decrption Formula:(AS + B) \bmod q_l = M + t\cdot E
Full Decryption Formula:((AS + B) \bmod q_l) \bmod t = M
We can rewrite the half decryption formula’s modulo q_l reduction as follows: AS + B - kq_l = M + t\cdot E
,where -kq_l takes the role of modulo reduction of (AS + B) by q_l, with some integer k.
BGV Modulus Switch
We find new polynomials A' and B' as follows:
Among all possible A' such that A' \equiv A \bmod t, choose the one whose each term’s coefficient is the closest integer to that of polynomial \dfrac{q_{l-1}}{q_l}\cdot A
Among all possible B' such that B' \equiv B \bmod t, choose the one whose each term’s coefficient is the closest integer to that of polynomial \dfrac{q_{l-1}}{q_l}\cdot B
Once such A' and B' are found, then the modulus-switched new ciphertext is: (A', B') \bmod q_{l-1}
Lemma
Full decryption of (A', B') \bmod q_{l-1} outputs our same original plaintext M as follows: ((A'S + B') \bmod q_{l-1}) \bmod t = M
Proof
Remember: (AS+ B - kq_l) \bmod t = M
In the above relation, we plug in the followings: A \equiv A' \bmod t B \equiv B' \bmod t q_{l} \equiv q_{l-1} \bmod t
Then, we get: (A'S+ B' - kq_{l-1}) \bmod t = M
Now, we will prove: A'S + B' - kq_{l-1} = (A'S + B') \bmod q_{l-1}
We can derive the following: A'S + B' - kq_{l-1} = (q_{l-1}/q_l)\cdot (AS+ B - kq_l) + (A' - (q_{l-1}/q_l)\cdot A)\cdot S + (B' - (q_{l-1}/q_l)\cdot B)
By |P|, we denote a polynomial whose each term’s coefficient is an absolute-valued one of P.
Now, notice the following relation: |A'S + B' - kq_{l-1}| = |(q_{l-1}/q_l)\cdot (AS+ B - kq_l) + (A' - (q_{l-1}/q_l)\cdot A)\cdot S + (B' - (q_{l-1}/q_l)\cdot B)| \leq |(q_{l-1}/q_l)\cdot(AS+ B - kq_l)| + |(A' - (q_{l-1}/q_l)\cdot A)\cdot S| + |(B' - (q_{l-1}/q_l)\cdot B)| = (q_{l-1}/q_l)\cdot |(AS+ B) - kq_l| + |(A' - (q_{l-1}/q_l)\cdot A)\cdot S| + |(B' - (q_{l-1}/q_l)\cdot B)|
Since AS + B - kq_l = M + t\cdot E, the following holds: |AS + B - kq_l| = |M + t\cdot E|. Therefore, (q_{l-1}/q_l)\cdot |AS + B - kq_l| = (q_{l-1}/q_l)\cdot |t\cdot E + M|. For polynomial |t\cdot E + M|, its each term’s coefficient is expected to be smaller than q_l (because otherwise, the noise budget q_{l} will run out). This means that for polynomial (q_{l-1}/q_l)\cdot |t\cdot E + M|, its each term’s coefficient is expected to be smaller than q_{l-1}. Since (q_{l-1}/q_l)\cdot |AS + B - kq_l| = (q_{l-1}/q_l)\cdot |t\cdot E + M|, the same is true for (q_{l-1}/q_l)\cdot |AS + B - kq_l| (i.e., its each term’s coefficient is expected to be smaller than q_{l-1}).
For polynomial |B' - (q_{l-1}/q_l)\cdot B|, its each term’s coefficient is maximum t, because B' \equiv B \bmod t.
For polynomial |(A' - (q_{l-1}/q_l)\cdot A)\cdot S|, its each term’s coefficient is maximum t\cdot n, because A' \equiv A \bmod t, and the (n-1)-degree polynomial S's each coefficient is either \{-1, 0, 1\}.
Combining all these, for polynomial |A'S + B' - kq_{l-1}|, its each term’s coefficient is maximum q_{l-1} + (t + 1)\cdot n. We can boldly assume that polynomial t \cdot E's each term’s coefficient is smaller than q_{l} - (t + 1)\cdot n, which is true in most cases if E is not extremely close to running out of its noise budget q_l. Then, for polynomial |A'S + B' - kq_{l-1}|, its each term’s coefficient is smaller than q_{l -1}.
For polynomial |A'S + B' - kq_{l-1}|, if its each term’s coefficient is smaller than q_{l-1}, then it must be the case that A'S + B' - kq_{l-1} = (A'S + B') \bmod q_{l-1}.
Based on Step 1 and Step 2, we reach the following relation: ((A'S+ B') \bmod q_{l-1}) \bmod t = (A'S+ B' - kq_{l-1}) \bmod t # by applying Step 2 = M # by applying Step 1
Since ((A'S+ b') \bmod q_{l-1}) \bmod t = M, (A', B') \bmod q_{l-1} is a ciphertext whose modulus is switched from q_l \rightarrow q_{l-1} and yet decrypts to our same original plaintext M.