A problem in secret sharing and mixed operators over $\mathbb{Z}$

Question

Recently, I studied an article in which it was written that having $(A-B)\oplus C$ and $B\oplus C$, we cannot find $A$. The authors used this result to build a secret sharing scheme, but they did not provide any proof for this claim. In general case, is this claim correct?

Note that in special cases(as an example, in $GF(2^m)$), we can find $A$ easily(since $A-B=A+B=A\oplus B$).

Edit: I don't remember the exact link for my question, but the similar thing is in this paper.

Answer 1

I'll consider that 2's complement is used for negative numbers in $\Bbb Z$, or that $A\ge B\ge0$. Even with such provision, the question's claim is too imprecise to be settled:

having $(A-B)\oplus C$ and $B\oplus C$, we cannot find $A$

Fact is, what we learn about $A$ from $(A-B)\oplus C$ and $B\oplus C$ depends heavily on $D=(A-B)\oplus B$, which we can compute from the givens as $D=((A-B)\oplus C)\oplus(B\oplus C)$ (and this reduction of the two givens to the single $D$ did not change what we can learn from $A$, if nothing was known from $C$ we eliminated).

That information we get on $A$ from $D=(A-B)\oplus B$ varies from

• the low-order bit of $A$, which always matches the low-order bit of $D$;
• to (at least) the low-order $k$ bits of $A$: we can prove by induction that for any integer $k$, $D\equiv-1\pmod{2^k}\implies A\equiv-1\pmod{2^k}$;
• or even the whole of $A$: using 2's complement, when $D=-1$, $A$ can only be $-1$ and $B$ can take any value.

A true statement could be: for random choice of the low-order $k$ bits of $A$, $B$ and $C$, probability that we can determine with certainty the low-order $k$ bits of $A$ from $(A-B)\oplus C$ and $B\oplus C$ decrease as $O(2^{-k})$.