Division in paillier cryptosystem

Question

Is division possible in the Paillier Cryptosystem? i.e. given a the cipher-text $C$ of an integer $M$ the plain-text divisor $D$, and only the public key, can one compute the cipher-text of $M/D$ ?

Answer 1

In general, no. There are, however, specific conditions that, when met, make it possible.

Working Mod $\phi(N^2)$

If given $D^{-1} \bmod{\phi(N^2)}$, then $\mathcal{E}(M/D)$ can be computed. So the question remains, when is computing $D^{-1} \bmod{\phi(N^2)}$ possible?

It is only possible if $gcd(D, \phi(N^2))=1$. Note that $\phi(N^2)=N\cdot \phi(N)=N\cdot(p-1)\cdot(q-1)$. Since $N=p\cdot q$, $N$ is odd, but $p-1$ and $q-1$ are even. Thus, for any even $D$, $gcd(D, \phi(N^2))\neq 1$. So, $D$ can never be even.

For odd $D$, it will work if the condition I specified holds.

If $D\nmid M$ ($D$ does not divide $M$), even if the $gcd=1$, the result will not necessarily make sense.

So, it will work under a few conditions, but in general it will not.

Update, Working Mod $N$

As PulpSpy points out, one can also work Mod $N$. In that case, $gcd(D,N)=1$ for all $D\neq p,q$ (in most every practical case). So, the math works, but you still have issues in practice when $D\nmid M$.

Answer 2

Yes (and always).

Given $\mathsf{Enc}(a)$ and $b$, you can compute $\mathsf{Enc}(a \cdot b^{-1} \bmod{n})$ by simply computing $\hat{b}=b^{-1} \bmod{n}$ and $Enc(a)^\hat{b} \bmod{n^2}$.

Paillier encryption is built on the bijeective mapping from $(x,y)\in \mathbb{Z}_n \times \mathbb{Z}_n^*$ to:

$E_{g,n}(x,y)=g^x y^n \bmod{n^2}$.

Generator $g$ is chosen to enforce that $x$ remains in $\mathbb{Z}_n$ (i.e., there exists a $y$ that makes $x$ unique in $\mathbb{Z}_n$). Specifically, it has order $\alpha n$ for a positive $\alpha < \mathrm{LCM}(p-1,q-1)$. A simple optimization is to set $\alpha=1$ by choosing $g=n+1$.

Regardless of variant, in the encryption scheme, $x$ is the message and thus $\mathbb{Z}_n$ is the message space. Contrary to the other answers, this allows $b$ to be generally inverted $\bmod{n}$ (except when 0 or in the negligible case that it is either $p$ or $q$).

---

Given the confusion, I did a sanity check in Mathematica to make sure (I picked small safe primes but you can set them using RandomPrime):

p = 23;
q = 83;
n = p*q;
lam = LCM[p - 1, q - 1];

L[u_] := Quotient[u - 1, n];

Trap[y_] := L[PowerMod[y, lam, n^2]];

g = RandomInteger[{1, n}];
While[GCD[Trap[g], n] != 1, g = RandomInteger[{1, n}]]

Enc[m_] := Module[{r, c},
  r = RandomInteger[{1, n - 1}];
  c = Mod[PowerMod[g, m, n^2]*PowerMod[r, n, n^2], n^2]
  ]

Dec[c_] := Mod[Trap[c]*PowerMod[Trap[g], -1, n], n];

m = RandomInteger[{1, n - 1}];
s = RandomInteger[{1, n - 1}];
si = PowerMod[s, -1, n];
c = PowerMod[Enc[m], si, n^2];
Dec[c] == Mod[m*si, n]

---

This answer is the result of a crash course in Paillier. I typically work in the discrete logarithm setting. Feel free to edit if there are any errors (you probably do know more than me).

Answer 3

One alternative that hasn't been mentioned, which may possibly be of interest, is doing plain old integer division in Paillier. The protocol is non-trivial, but, perhaps surprisingly, can be done somewhat efficiently. There was a paper at FC12:

On Secure Two-party Integer Division [PDF]