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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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.
answered Dec 19, 2015 at 10:51
-
$\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$– curiousDec 19, 2015 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$ Dec 19, 2015 at 21:01
-
$\begingroup$ @curious Formula suggested is easy to extend to multiple inputs. $\endgroup$ Dec 19, 2015 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$ Dec 20, 2015 at 0:10
$\begingroup$
$\endgroup$
2
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.
answered Dec 19, 2015 at 17:19
-
$\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$– curiousDec 19, 2015 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$ Dec 19, 2015 at 18:35
$\begingroup$
$\endgroup$
4
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].
-
$\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$– curiousDec 19, 2015 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$– curiousDec 19, 2015 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$– user991Dec 19, 2015 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$ Dec 19, 2015 at 21:12