Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
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! –  Dave Dec 18 '13 at 1:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.