0
$\begingroup$

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

| improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ What do you mean by b+a? b XOR a? $\endgroup$ – DrLecter Sep 30 '14 at 12:09
  • $\begingroup$ 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 ? $\endgroup$ – user153465 Sep 30 '14 at 12:13
  • 1
    $\begingroup$ 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. $\endgroup$ – DrLecter Sep 30 '14 at 12:22
  • $\begingroup$ Basically I define the values (a and b) in Zp, accordingly the result in Zp $\endgroup$ – user153465 Sep 30 '14 at 12:29
  • 1
    $\begingroup$ What does XOR in $\mathbb{Z}_p$ mean? $\endgroup$ – mikeazo Sep 30 '14 at 13:03
5
$\begingroup$

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.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Paŭlo Ebermann Sep 30 '14 at 19:29
  • $\begingroup$ @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. $\endgroup$ – mikeazo Sep 30 '14 at 20:01
  • $\begingroup$ 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.) $\endgroup$ – Paŭlo Ebermann Sep 30 '14 at 20:41
  • $\begingroup$ Does not make sense, the answer got 4 points but the question that got -1 point !!! It means good answer for rubbish question !! $\endgroup$ – user153465 Oct 6 '14 at 19:46
  • $\begingroup$ @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. $\endgroup$ – mikeazo Oct 6 '14 at 19:58

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.