Is XOR distributive over any operations?

6.6k Views Asked by At

Given (A ^ C) * (B ^ C) = y where ^ is equivalent to XOR and * is equivalent to some operation (i.e. multiplication), is there any way of determining what A * B would have been equal to? It is assumed that you know A, B, C, and y, but that you don't know the operation * being used.

Is there any additional operations that could be included into the equation for y such as modulo?

Edit: It should be assumed that there are potentially infinite variations of *, hence trial and error of all possible operations might be impossible.

Edit: The scenario here is that person P has 'encrypted' A and B using XOR operations with C (encryption is a very loose word here). Person P now wants person Q to perform some function (i.e. multiplication) on A and B without decrypting them (i.e. fully homomorphic encryption). Having performed the function, person Q gives the result y back to person P who will 'decrypt' y to get the true result they are after.

1

There are 1 best solutions below

1
On

XOR is not distributive over any operations (including itself). Out of all the bitwise operations only AND is distributive over all other bitwise operations such that (A & C) * (B & C) is equivalent to (A * B) & C where * is a bitwise operation. If * is any operation however, there is no bitwise operation that will help in this case. However, since & does not have an inverse you cannot use this fact to produce the equation y inv& C = A * B.