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&lt;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&gt;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 &gt; \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.