Let $E(m)$ a be the encryption operation using Paillier encryption scheme. Let $N$ be the public key and $p$ be a large prime number, such that $p<N$.

Question: Is there any protocol, that given $E(m)$ can compute homomorphic $\mod p$, so after decryption we would a message in $\mathbb{F}_p$?

Or is there any multi-party computation protocol that can do it?


Is there any protocol, that given $E(m)$ can compute homomorphic $E(m \bmod p)?$

If there were a way to perform that operation (for any $p>1$ relatively prime to $N$) without the Pallier private key being involved, then you have just shown that Pallier is Fully Homomorphic; that is, you can homomorphicly implement any computation; at the very least, by doing homomophic circuit evalutation.

One approach to show this is to implement a NAND function, which we can do as follows:

$$\textit{NAND}(x, y) = 1 + p^{-1} \cdot ( \lambda(x + y) \bmod p - \lambda(x+y))$$


  • All the operations are done homomorphically, for example, $x + y$ means the homomorphic addition of $x$ and $y$

  • $\lambda$ is an integer $p > \lambda \ge p/2$

  • $p^{-1}$ is the multiplicative inverse of $p$ modulo $N$

All the computations included in the NAND definition are additions, subtractions, multiplications by the constants $\lambda$ and $p^{-1}$ (all of which can be performed homomorphicly within Pallier), and the $\bmod p$ operation, which we are assuming also can be performed homomorphicly.

And, if we evaluate NAND (assuming that $x, y$ are constrained to be either 0 or 1, we find that if either $x, y$ are encrypted 0 (or both are), NAND evaluated to encrypted 1; if both are 1, it evaluates to an encrypted 0.

And, NAND is known to be complete; we can construct any circuit be a sufficiently large pile of them. That is, we can design a circuit to evaluate our function (e.g. SHA-3), and then give as inputs as a series of encrypted 0's and 1's, and get the output as a series of encrypted 0's and 1's.

  • $\begingroup$ Thank you, but the answer is not very clear, so I guess it is not possible? $\endgroup$
    – user153465
    Aug 9 '16 at 18:23
  • 2
    $\begingroup$ @user153465: I haven't shown that it's not possible - I have shown that if it's possible, then you have a Very Significant Result. $\endgroup$
    – poncho
    Aug 9 '16 at 18:26
  • $\begingroup$ thank you. But it is possible when we use FHE? $\endgroup$
    – user153465
    Aug 9 '16 at 18:31
  • 1
    $\begingroup$ @user153465: FHE, by definition, allows you to evaluation any function homomorphically, so yes... $\endgroup$
    – poncho
    Aug 9 '16 at 18:36
  • 1
    $\begingroup$ @DanielApon: actually, it's not hard to extend this proof to show that Pallier, along with (just about) any nonlinear homomorphic function, (that is, a function that can't be expressed in the form $cX+d \bmod N$), is FHE; the "just about" term is there to handle odd cases where knowledge of where the nonlinearity happens would allow you to factor $N$ (and hence can't be disclosed). $\endgroup$
    – poncho
    Aug 10 '16 at 10:44

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.