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&lt;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.
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)&amp;=D(E(m_1)\cdot E(m_2)\bmod n^2)&amp;&amp;\text{and}\\
(m_1-m_2\bmod n)&amp;=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&lt;n/2$ then we have
$$\begin{align}
m_1+m_2&amp;=D(E(m_1)\cdot E(m_2)\bmod n^2)&amp;&amp;\text{and}\\
m_1-m_2&amp;=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&lt;m&lt;n/2$, then $D'(E(m))=m$; and for all messages $m_1$ and $m_2$:
$$\begin{align}
[m_1+m_2]_n&amp;=D'(E(m_1)\cdot E(m_2)\bmod n^2)&amp;&amp;\text{and}\\
[m_1-m_2]_n&amp;=D'(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$
If $-n/4&lt;m_1&lt;n/4$ and $-n/4&lt;m_2&lt;n/4$ then we have
$$\begin{align}
m_1+m_2&amp;=D'(E(m_1)\cdot E(m_2)\bmod n^2)&amp;&amp;\text{and}\\
m_1-m_2&amp;=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.