# Paillier subtraction for negative result

I am trying to figure out subtraction on Paillier.

From what I read so far, given $m_1$ smaller than $m_2$ ($m_1<m_2$) I can compute $E(m_2-m_1)$ as $E(m_2)\cdot E(m_1)^{-1}$ where $E(m_1)^{-1}$ produce $-m_1$ when decrypted.

What is unclear to me is if I can calculate $E(m_1-m_2)$ which should result in a negative number when decrypted.

• Beware that strictly speaking, $E(m_2)\cdot E(m_1)^{-1}\bmod n^2$ is not $E(m_2-m_1)$, but something among the many values that could have been obtained as $E(m_2-m_1)$. Also, when $0<m_1<n$, it does not hold that $D(E(m_1)^{-1}\bmod n^2)=-m_1$ per the usual definition of decryption in Pailler; what's obtained is $n-m_1$.
– fgrieu
May 22 '18 at 13:46

In Pailler encryption, it holds for all messages $m_1$ and $m_2$, and whatever randoms[*] are used by encryption, that: \begin{align} (m_1+m_2\bmod n)&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\ (m_1-m_2\bmod n)&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align} where the modular inverse $E(m_2)^{-1}$ is computed modulo $n^2$, that is in $\Bbb Z_{n^2}^*$.
If $0\le m_2\le m_1<n/2$ then we have \begin{align} m_1+m_2&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\ m_1-m_2&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align}
When the sign of $m_1-m_2$ is unknown, we can define a modified Pailler cryptosystem. Encryption is unchanged, or/and we can compute $E(m)$ as $E(m\bmod n)$ when $m$ is negative. Decryption is modified to $D'(c)=[D(c)]_n$ with by definition $[x]_n=((x+\lfloor n/2\rfloor)\bmod n)-\lfloor n/2\rfloor$.
Whatever random[*] is used by encryption, if $-n/2<m<n/2$, then $D'(E(m))=m$; and for all messages $m_1$ and $m_2$: \begin{align} [m_1+m_2]_n&=D'(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\ [m_1-m_2]_n&=D'(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align} If $-n/4<m_1<n/4$ and $-n/4<m_2<n/4$ then we have \begin{align} m_1+m_2&=D'(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\ m_1-m_2&=D'(E(m_1)\cdot E(m_2)^{-1}\bmod n^2) \end{align} I fail to find who first extended Paillier encryption to subtraction, or/and to signed values with that variant $[x]_n$ of the $x\bmod n$ operator; but this is simple and natural enough that my guess is it has been independently rediscovered several times. The notation $[x]_n$ is often used in homomorphic encryption, at least since Craig Gentry and Shai Halevi Implementing Gentry's Fully-Homomorphic Encryption Scheme (extended abstract in proceedings of Eurocrypt 2011).
[*] Restrict the random integer $r\in\big[0,n^2\big)$ used by encryption to be coprime with $n$; that's overwhelmingly likely if $n$ is hard to factor.