8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – curious Dec 19 '15 at 18:25
  • $\begingroup$ @curious Yes, $x+y-xy$ is equivalent. Please note that full homomorphic is stronger than one-multiplication additive homomorphic scheme. $\endgroup$ – Vadym Fedyukovych Dec 19 '15 at 21:01
  • $\begingroup$ @curious Formula suggested is easy to extend to multiple inputs. $\endgroup$ – Vadym Fedyukovych Dec 19 '15 at 21:14
  • 2
    $\begingroup$ 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$. $\endgroup$ – Ilmari Karonen Dec 20 '15 at 0:10
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – curious Dec 19 '15 at 18:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Yehuda Lindell Dec 19 '15 at 18:35
4
$\begingroup$

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].

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – curious Dec 19 '15 at 18:39
  • $\begingroup$ Can you elaborate? i have 0,1 and the or equals 1 and not 0 as it would be if i multiplied $\endgroup$ – curious Dec 19 '15 at 18:47
  • $\begingroup$ 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 . ​ ".) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Dec 19 '15 at 19:57
  • $\begingroup$ 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. $\endgroup$ – Vadym Fedyukovych Dec 19 '15 at 21:12

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.