# Homomorphic OR operations

Is there an encryption scheme that provides efficient homomorphic OR operations at the ciphertext space? Of course any fully homomorphic encryption can be used but I do not require or want additional homomorphic operations.

For any $x,y$ represented by $\{0, 1\}$, $x \lor y = 1 - (1-x)(1-y)$. It follows, any one-multiplication homomorphic scheme would do. It also follows, just additively homomorphic scheme would be not enough.

• I can't get your formula. why you do not just write x+y-xy. And if this circuit is translated to an OR than you do not need just an additively homomorphic scheme but a multiplicative at the same time... – curious Dec 19 '15 at 18:25
• @curious Yes, $x+y-xy$ is equivalent. Please note that full homomorphic is stronger than one-multiplication additive homomorphic scheme. – Vadym Fedyukovych Dec 19 '15 at 21:01
• @curious Formula suggested is easy to extend to multiple inputs. – Vadym Fedyukovych Dec 19 '15 at 21:14
• Perhaps more usefully, as Ricky Demer suggests in his answer, if you invert the representation so that false = 1 and true = 0, then $x \lor y$ is simply $xy$. – Ilmari Karonen Dec 20 '15 at 0:10

To be very concrete: you can use the BGN crypto system that allows addition and a single multiplication. Alternatively, you can use this scheme by Gentry-Halevi-Vaikunathan based on LWE that also allows a single multiplication.

• So i just need an additive homomorphic scheme?Then pailier will work?No because the ciphertext space has many elements. So how E(1)+E(1) will result in E(1) at the ciphertext space?By quadratic residuosity you mean the GM scheme?I thought that was only XOR homoorphic – curious Dec 19 '15 at 18:30
• Sorry, I didn't read the question properly. You need OR and not XOR. GM and lattices won't work. I have completely changed the answer. – Yehuda Lindell Dec 19 '15 at 18:35

The way in which it follows that "any one-multiplication homomorphic scheme would do" is
false = 1 ​ and ​ true = 0 .
Similarly, schemes that can do more multiplications can in that way
be used for correspondingly many more OR operations.

If a 1/n probability of false negatives is acceptable, then
a ​ $($$\mathbb{Z}/n\mathbb{Z}$$,\hspace{-0.05 in}+)$-homorphic scheme would be enough:
false = 0 ​ ​ ​ and ​ ​ ​ true ​ = ​ random element ​ .
(Note that n will usually be exponential in the security parameter.)
Furthermore, even for an already-generated key pair, that probability can be reduced to
1$\hspace{-0.03 in}\big/\hspace{-0.05 in}\big(\hspace{-0.02 in}n^{\hspace{.04 in}j}\hspace{-0.03 in}\big)$ by using $\hspace{.04 in}j$ independent ciphertexts, and anyone can decrease $\hspace{.04 in}j$ by dropping some of
the ciphertexts, and a ciphertext whose $\hspace{.04 in}j$ is $\hspace{.04 in}j_0$ can be ORed with a ciphertext whose $\hspace{.04 in}j$ is $\hspace{.04 in}j_1$ to produce a ciphertext whose $\hspace{.04 in}j$ is ​ $\hspace{.04 in}j_0 \hspace{-0.03 in}+ j_1 \hspace{-0.03 in}-\hspace{-0.03 in}1$ ​ by [arbitrarily designating a "primary" from each] and [homomorphically adding each [pair with one from each] that includes at least of the primaries].

• I don't get it very clearly. It the truth table of or 3/4 entries are 1 and 1 is zero. If you multiply the elements then 3/4 entries become zero and 1/4 is one. From the cases it becomes 0 when multiplying only one is correct (0*0) and the others (0*1),(1*0) they do give the wrong result, because the OR gives 1. – curious Dec 19 '15 at 18:39
• Can you elaborate? i have 0,1 and the or equals 1 and not 0 as it would be if i multiplied – curious Dec 19 '15 at 18:47
• If you "have 0,1" then the or be true, which is "0 as it would be if" you multiplied. $\hspace{1.36 in}$ (See ​ ​ ​ " ​ false = 1 ​ and ​ true = 0 . ​ ".) ​ ​ ​ ​ ​ ​ ​ ​ – user991 Dec 19 '15 at 19:57
• Consider true=1, false=0 encoding. OR is false iff all inputs are false. Now $(1−x)(1−y)$ is true iff all multipliers are 1, so that variables be 0. – Vadym Fedyukovych Dec 19 '15 at 21:12