4
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ What was the field for this $-$ operation? $\endgroup$ – SEJPM♦ Apr 3 '18 at 16:59
  • $\begingroup$ @SEJPM, Integer ring. $\endgroup$ – Meysam Ghahramani Apr 3 '18 at 17:28
  • 1
    $\begingroup$ Do you have a link to the article available? (for context) $\endgroup$ – puzzlepalace Apr 3 '18 at 17:55
  • 2
    $\begingroup$ That's strange; for one, you need to define what $\oplus$ does when given a negative integer. For another, well, in secret sharing schemes, you typically need to derive your secret parameters using an equidistributed probability distribution (as nonuniform distributions tend to leak information); that's actually impossible over $\mathbb{Z}$ $\endgroup$ – poncho Apr 3 '18 at 19:17
  • 3
    $\begingroup$ Maybe edit the question to add a reference to the article you are talking about? $\endgroup$ – Maeher Apr 4 '18 at 0:09
2
$\begingroup$

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

|improve this answer
$\endgroup$

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.