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


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

  • $\begingroup$ Why no? If you just don't care about the remainder, isn't it like a multiplication with the inverse, which can be seen as a constant multiplication, thus able to be homomorphically evaluated by a Paillier encryption circuit? $\endgroup$
    – curious
    Oct 14 '13 at 10:24

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

  • $\begingroup$ yes but like mikeazo pointed out, the answer does not make sense if $b\nmid a$ $\endgroup$
    – user996522
    Mar 13 '12 at 4:33
  • 2
    $\begingroup$ @user996522 It depends on how you define "makes sense." If $a/b = c$, then $c \cdot b=a$. It is the same thing here. If you compute $a/b$ under encryption, you will get the encryption of the value $c$ such that $c \cdot b \bmod{n} = a$. You can think of it as "discrete division" akin to a discrete logarithm. $\endgroup$
    – PulpSpy
    Mar 13 '12 at 14:50

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]


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.