# Can I subtract 2 ciphertexts in FHE exactly?

In most FHE schemes, for a polynomial $$m_1$$,

$$enc(m_1) = a_1*s + e_1 + m_1$$

Suppose I have $$enc(m_1),enc(m_2)$$. Can I subtract them exactly? Sum works, but subtraction is:

$$enc(m_1) - enc(m_2) = (a_1-a_2)*s + e_1-e_2 + m_1-m_2$$

In the case where $$e_1-e_2$$ is negative, this gives us problems in the decryption (cleaning of small error bits by shift right). Example:

$$enc(m_1) - enc(m_2) - (a_1-a_2)*s = e_1-e_2 + m_1-m_2$$

the final step for decryption would be $$upper(e_1-e_2 + m_1-m_2)$$ but if $$e_1-e_2$$ is negative, it's actually a very large positive (2's complement or in this case, modulus complement), so upper will not work.

Another way would be to transform $$enc(m_2)$$ into $$enc(-m2)$$ homomorphically, then do $$enc(m_1)+enc(m_2)$$ but to do this in some schemes, subtraction is needed, so it won't work.

• I think there is a misconception about which polynomials are used. Coefficients are defined in a ring with representatives centered around 0, e.g., each coefficient is an integer in $\{-q/2+1, ..., 0, ..., q/2\}$. There is no problem on coefficients being on the left part (what you call "negative"). Decryption works as long as some internal value has coefficients close to 0. I think the issue you mention is more an encoding problem, but decryption should not care about this, it only understands polynomials in proper rings. Commented Jul 1, 2022 at 9:59

What @zugzwang wrote is indeed correct and here I will expand it a bit more. The basic idea is that there are many ways to represent coefficients in $$\mathbb{Z}_q$$. Using integers $$[0, q-1]$$ is one way, and using integers in $$[-q/2 + 1, \dots, 0, \dots, q/2]$$ is another way. If you view your subtraction operation in the second representation then it works out.
Specifically, to encrypt a value you typically do something like do $$E(m) = a \cdot s + \Delta m + e$$ where $$a$$ is a random public ring element, $$s$$ is the secrete key, $$\Delta$$ is a scaling factor and $$e$$ is the added noise. But for the homomorphic operations to be correct, $$e$$ has to be "small" as you said. Coefficients in $$e$$ is sampled from a discrete Gaussian distribution with a mean of 0. Typically $$e$$ only takes values from $$\{-1, 0, 1\}$$ and majority of the coefficients are 0. Now if we do subtraction, we get $$c_0 - c_1 = (as + \Delta m_0 + e_0) - (as + \Delta m_1 + e_1) = as + \Delta(m_0 - m_1) + (e_0 - e_1)$$ During decryption you subtract $$as$$ and then round. But $$(e_0-e_1)$$ is still small so you can recover the plaintext.
Note that in some implementation, the $$[0,q-1]$$ representation is still used, so coefficients of $$e$$ would be from $$\{q-1, 0, 1\}$$. Then you need to do rounding in a different way. If the message is a bit, then you need to round the value to $$1$$ if it's between $$(q/4, 3q/4)$$, otherwise you round it to $$0$$.
• what if e is from -10 to 10 (for example) and \Delta=1? BFV uses high Delta but for TFHE, Delta=1, then we have the subtraction problem I mentioned Commented Jul 9, 2022 at 1:04
• There might some misunderstanding, TFHE doesn't use $\Delta=1$. For plaintext space $t$ you set $\Delta=q/t$. Also there are other types of encoding for float or approximate arithmetic. If your error grows too large then you can't decrypt anymore. Commented Jul 9, 2022 at 20:54
• try with $m_1 = 30$, $m_2=1$, $\Delta=2^7$, $e_1=2$, $e_2=6$, then $e_1-e_2+m_1-m_2 = -4 + (30<<7)-(1<<7) \implies (-4 + (30<<7)-(1<<7))>>7 = 28 \neq 30-1 = 29$ Commented Jul 11, 2022 at 17:12
• The $-4$ was supposed to be in the lower bits of $(30<<7)-(1<<7)-4$ but it ends in the higher bits, because the $-4$ in the subtraction borrows all the 0 bits of $(30<<7)-(1<<7)$ until it finds a $1$ Commented Jul 11, 2022 at 17:12
• if $-4$ were in the lower bits like $+4$, then $>>7$ would correctly decrypt everything, but $-4$ ends up eating one bit of the encoded message Commented Jul 11, 2022 at 17:14