2

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.

James
  • 181
  • You know the inputs and you know the output, so what’s stopping you from just trying every “operation” and seeing if it fits? – Zhen Lin Jul 01 '22 at 04:26
  • I will add that as an additional specification to the question: it should be assumed that there are potentially infinite possible operations and as such you may never find the fitting operation by trial and error. – James Jul 01 '22 at 04:28
  • There is still something not clear about your question. What problem are you really trying to solve here? – Zhen Lin Jul 01 '22 at 07:42
  • I will add in the scenario to the question @ZhenLin for extra clarification. – James Jul 01 '22 at 07:58
  • Essentially we want to be able to perform calculations on 'encrypted' forms of A and B, and 'decrypt' it afterwards to get the result we are after. – James Jul 01 '22 at 08:03
  • That’s the whole point of homomorphic encryption. But what does that have to do with guessing the operation performed? – Zhen Lin Jul 01 '22 at 08:14
  • @ZhenLin you mentioned the idea of "just trying every 'operation' and seeing if it fits". But considering there are perhaps infinite possible operations we can't really try every operation till it fits. In my scenario you either don't know the operation that has been performed, or you lack the computational ability to perform the operation yourself. – James Jul 01 '22 at 10:25
  • I believe a simplification of this question is to ask if you have (A + C) * (B + C) is there any way to change it to A * B (which I believe might be impossible). This is because XOR is modular addition. – James Jul 01 '22 at 11:55
  • I still don't see an answerable question here. Forget about encryption for the moment – or imagine that by sheer misfortune $C = 0$. Then it seems you are asking, given $A, B, y$, what operation $$ satisfies $A B = y$? There is far too little information to determine $$. Even if we restrict to the four basic arithmetical operations, imagine that $A = B = 2$ and $y = 4$. Is $$ going to be $+$ or $\times$? – Zhen Lin Jul 01 '22 at 12:08
  • 2
    The only way you could possibly determine A*B from the given data would be if ^ is right-distributive over the operation * in which case the equation is (A*B)^C=y and you can XOR both sides with C to get A*B=y^C. Otherwise, there is very little information to determine the result you seek. You need to know at least some property of * to manipulate the equation and isolate the A*B part that you need. – Prasun Biswas Jul 01 '22 at 12:34
  • I used the keyword of 'distributivity' that you mentioned and found that XOR is not distributive over any operation (including itself). Also the reason I avoided making any specification for * (beyond multiplication as an example) is because if one knows what this operation is there is almost no use case for homomorphic encryption (why not just perform the function yourself if you know what the function is). I am assuming that these functions only use addition or multiplication, but in differing manners. – James Jul 02 '22 at 02:46
  • So... your actual question is, what is the use of homomorphic encryption? That's not mathematics, that's engineering. – Zhen Lin Jul 03 '22 at 00:58
  • 1
    No, my actual question is still about the distributivity of XOR over any operations (which I now understand to be impossible, hence my question is answered and so I will be writing up an answer for the question soon). I only raised the example of homomorphic encryption to help frame my question (why I had the condition that you don't know the operations that have been used). – James Jul 03 '22 at 01:44

1 Answers1

-1

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.

James
  • 181
  • 2
    What are "all the bitwise operations"? AND does not distribute over NAND: (0 AND 0) NAND (0 AND 0) = 1, but (0 NAND 0) AND 0 = 0. – Zhen Lin Jul 08 '22 at 23:14