Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  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).

share|improve this answer
    
yes but like mikeazo pointed out, the answer does not make sense if $b\nmid a$ –  user996522 Mar 13 '12 at 4:33
    
And the light came... Thanks for your patience. –  fgrieu Mar 13 '12 at 8:38
1  
@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. –  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]

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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