0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – zugzwang
    Commented Jul 1, 2022 at 9:59

1 Answer 1

1
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ 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 $\endgroup$
    – Rafaelo
    Commented Jul 9, 2022 at 1:04
  • $\begingroup$ 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. $\endgroup$
    – lamba
    Commented Jul 9, 2022 at 20:54
  • $\begingroup$ 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$ $\endgroup$
    – Rafaelo
    Commented Jul 11, 2022 at 17:12
  • $\begingroup$ 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$ $\endgroup$
    – Rafaelo
    Commented Jul 11, 2022 at 17:12
  • $\begingroup$ 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 $\endgroup$
    – Rafaelo
    Commented Jul 11, 2022 at 17:14

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.