4
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Indeed, you're right. Completely forgot about NAND. That would indeed negate the non-FHE condition. At least now I know there's no point searching! $\endgroup$ – Dave Dec 18 '13 at 1:50

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.