# Homomorphic encryption based on XOR

Consider the values $a$ and $b$ are encrypted as $c_1=(a \oplus D)$ and $c_2=(b \oplus D)$.

My question is: can we derive $b+a$ from any combination of $c_1$ and $c_2$?

Note:

1. I admit that the $D$ should have not been used for both $a$ and $b$. For now assume we can use it.

2. Basically I define the values ($a$ and $b$) in $Z_p$, accordingly the result in $Z_p$.

• What do you mean by b+a? b XOR a? Sep 30 '14 at 12:09
• a and b are two values (say message), we pick a random value D, then XOR (exclusive or) a and D we denote the result by C1 , we XOR b and D ,we denote the result C2. Now the question is whether given D , c1 and c2 can one compute a+b ? Sep 30 '14 at 12:13
• Its still not really answerable. YES: If you have an XOR homomorphic cipher (like Golderwasser-Micali), where the message space is $\{0,1\}$ (bits), then given c1 (as an encryption of a XOR d) and c2 (as an encryption of b XOR d), then the product of c1 and c2 modulo n gives a ciphertext to (a XOR d) XOR (b XOR d) = a XOR b (and a XOR b is addition in GF(2), so this can be seen as a+b). Clearly, a,b and d are bits. You need to be more precise in your definition of message space etc. Sep 30 '14 at 12:22
• Basically I define the values (a and b) in Zp, accordingly the result in Zp Sep 30 '14 at 12:29
• What does XOR in $\mathbb{Z}_p$ mean? Sep 30 '14 at 13:03

Based on the additional details in the comments, it seems like your question is: given $c_1=a\oplus d$ and $c_2=b\oplus d$, can we get $(a+b)\oplus d$. Where $a,b,d\in\mathbb{Z}_p$, $+$ is addition modulo $p$, and $\oplus$ is a bitwise XOR of the values, then taken modulo $p$.

Or put another way, is there an operation $\boxplus$, such that $(a\oplus d)\boxplus (b\oplus d)\equiv (a+b)\oplus d\bmod{p}$?

Hopefully I've understood the problem correctly.

The answer is no, except in the trivial case of $p=2$, or more generally (if $p$ is not necessarily a prime) when $p=2^q$ for some prime $q$. That is because in these two cases, in the finite field $\mathbb{Z}_p$, $\oplus$ and $+$ are traditionally the same operation (note that by $+$ I am not talking about integer addition modulo $p$, I am referring to addition in the finite field). Or put another way $+$ is defined as bitwise xor in these fields.

In the case where $p\neq 2$ and $p\neq 2^q$ for some prime $q$, the bitwise XOR destroys all algebraic structure necessary for there to be an operation $\boxplus$. Now, what you can do is use $+$ instead of $\oplus$. Then you have $(a+d) + (b+d) = (a+b) + (d+d)$ and to decrypt, subtract $(d+d)$. If doing this, you should use different $d$ values for each message. In other words $(a+d_1) + (b+d_2) = (a+b) + (d_1+d_2)$ and to decrypt, subtract $(d_1+d_2)$. The $d_i$ values must be randomly chosen.

Full disclosure: My answer is based on intuition. It might be hard to prove that $\boxplus$ does not exist, but it seems very unlikely that it does. Basically we need associativity between $\oplus$ and $\boxplus$ (i.e., $(a\oplus b)\boxplus c = a \oplus (b\boxplus c)$ and $\boxplus$ must be commutative ($a\boxplus b = b\boxplus a$). There are lots of candidates for commutativity, but I can't think of any for that type of associativity.

• But for $p = 2^q$, we have $(a \oplus d) \oplus (b \oplus d) = (a \oplus b) \neq (a \oplus b) \oplus d$ – or do you want to define $x \boxplus y := x \oplus y \oplus d$? Sep 30 '14 at 19:29
• @PaŭloEbermann re first comment, you mean $=(a\oplus b)\neq(a\oplus b)\oplus d$ right? I was more going along the question of the OP "can we derive b+a from any combination of c1 and c2". In this case, we can derive $a\oplus b$ from some combination of c1 and c2. Sep 30 '14 at 20:01
• yes, typo (now fixed). Yes, but the "field of order $2^q$" doesn't have the same addition (or multiplication) as the ring $\mathbb Z/_{2^q \mathbb Z}$, so you shouldn't talk about "$\bmod 2^q$" here. (It is now clearer after your edit.) Sep 30 '14 at 20:41
• Does not make sense, the answer got 4 points but the question that got -1 point !!! It means good answer for rubbish question !! Oct 6 '14 at 19:46
• @user153465 If I had to guess, I'd guess the - votes came for the original question since it had a lot of holes. I gave it a +1 after your clarifying comments were added in. Oct 6 '14 at 19:58