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.

  • $\begingroup$ 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$. $\endgroup$
    – 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.

  • $\begingroup$ That was very helpful, thanks you. In the original paper, only addition is explored. If possible, can you point out who introduced this property to Paillier so that I can reference it ? Thanks you. $\endgroup$ May 22 '18 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.