Logical OR operation in a homomorphic additive cryptosystem

Question

Suppose we have a cryptosystem homomorphic for addition (say Paillier's). Is there a way to perform a logical OR operation between two binary values (with a binary result).

We can, of course, obtain the encoded result of addition between two values (by multiplying the encoded values):

$Enc(x + y) = Enc(x) \cdot Enc(y)$

and that gives us something close to a logical OR, except if both $x$ and $y$ have value $1$, in which case the result will be $2$, when it should be $1$.

Therefore another way to solve the problem might be to figure a homomorphic function: $F: \{1, 2\} \rightarrow 1; 0 \rightarrow 0$.

Does such a function exist?

Conversely, is there any way to prove that a true logical OR operation would break some fundamental properties/limitations of (non-full) homomorphic cryptosystems (and that I am wasting my time looking for one)?

Answer 1

Well, the problem is with logical OR and subtraction (which Pallier can also do), you've got FHE; that is, you can compute any combinatorial function of encrypted (binary) inputs.

Here's how it works, you can construct the NAND function:

$NAND(x, y) = (Enc(1) - x)\ OR\ (Enc(1) - y)$

If we limit $x$ and $y$ to being either encrypted 0, or encrypted 1, then the result of this is an encrypted 1 unless $x$ and $y$ are both an encrypted 1; in that case, the result will be an encrypted 0.

The $NAND$ function is complete; that is, we can create any combinatorial circuit using enough of them.