Homomorphic $\bmod p$ operation

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

where:

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

• Thank you, but the answer is not very clear, so I guess it is not possible? – user153465 Aug 9 '16 at 18:23
• @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. – poncho Aug 9 '16 at 18:26
• thank you. But it is possible when we use FHE? – user153465 Aug 9 '16 at 18:31
• @user153465: FHE, by definition, allows you to evaluation any function homomorphically, so yes... – poncho Aug 9 '16 at 18:36
• @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). – poncho Aug 10 '16 at 10:44