I'm curious about the homomorphic properties of Paillier. So, basically if I have $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha) \cdot \textsf{Enc}(\textsf{pk}, \alpha^{-1}))$, I will get as result $\alpha + \alpha^{-1}$. But, does it also mean that if I have $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha)^{\textsf{Enc}(\textsf{pk}, \alpha^{-1})})$, then the result will be $\alpha \cdot \alpha^{-1}$, which will basically cancel each other, and will be left with 1?

up vote 5 down vote accepted

No, there is no reason that $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk},\alpha)^{\textsf{Enc}(\textsf{pk}, \alpha^{-1})})$ would be $\alpha\cdot\alpha^{-1}$, including when we spread $\bmod N$ or $\bmod N^2$ here and there.

What does apply is: for overwhelmingly most $\alpha$ and $k$ in $\Bbb Z$, it holds that $\textsf{Dec}(\textsf{sk},\textsf{Enc}(\textsf{pk}, \alpha)^k\bmod N^2)=k\cdot\alpha\bmod N$. We could take $k=\alpha^{-1}\bmod N$ and get $\textsf{Dec}(\textsf{sk},\textsf{Enc}(\textsf{pk},\alpha)^{(\alpha^{-1}\bmod N)}\bmod N^2)=1$, but that's not useful anyway, since $\alpha^{-1}\bmod N$ reveals $\alpha\bmod N$.

Criticism of the question:

  • It is not defined in which group it is computed $\alpha^{-1}$, and that matters.
  • $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha) \cdot \textsf{Enc}(\textsf{pk}, \alpha^{-1}))$ will be $\alpha+\alpha^{-1}\bmod N$, which may or may not be $\alpha+\alpha^{-1}$.
  • Thanks for the clarification. – tinker Nov 14 at 11:14

Given two plaintexts $\alpha$ and $\beta$, Pailler cryptosystem $\mathcal{E}$ homomotphic property is: $\mathcal{E}(\alpha)\times \mathcal{E}(\beta)=\mathcal{E}(\alpha+\beta)$. So, $\mathcal{E}(\alpha)^n=\mathcal{E}(n\alpha)$. In your example, $n=\mathcal{E}(\alpha^{-1})$ and thus after decryption you will have $\mathcal{E}(\alpha^{-1})\times \alpha$ ans not $\alpha^{-1} \times \alpha$. This is a high level answer, but you need to define the modulo $N$ of your system.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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