Division in paillier cryptosystem

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

-

3 Answers

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

-

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

-
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]

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 56, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8705954551696777, "perplexity_flag": "middle"}