1

A $XOR$ $K$ is given. Both $A$ and $K$ are unknowns.

Can the value of $K$ be guessed? Can the values of $K$ can be deduced if the size of $A$ & $K$ are known? What is the smallest set on which bruteforcing can be performed to get the value of $K$?

Pardon if I was unclear.

I have the following problem

Problem: A ,A xor B , B xor C, C xor K are shared between four people to arrive into the secret K by XORing all the above values together.

In a special case A is not available (the first value). Would any of the participants be able to deduce the value of K in that case?

hax
  • 111
  • what do you mean by the size of $A$ and $K$ ? – Asinomás Aug 01 '16 at 22:34
  • You talk about XOR and sets in the same problem. Do you mean "symmetric difference" (of sets), and not the logical operator XOR? –  Aug 01 '16 at 22:54

1 Answers1

1

Assuming you mean sets and symmetric difference $A \Delta K =(A \setminus K) \cup (K \setminus A)$, there is NOTHING that knowing $A \Delta K$ can tell you about $K$ if you don't know anything about $A$. That is because given $K$, you can get ALL the possible results for $A \Delta K$ by varying $A$. (If you want the result $X$, there is exactly one $A$ that will give $A \Delta K = X$, namely $A = X \Delta K$).

The answer is the same if you meant XOR and logical variables (propositions).

  • Pardon if I were unclear. I have the following problem

    Problem: A ,A xor B , B xor C, C xor K are shared between four people to arrive into the secret K by XORing all the above values together.

    In a special case *A is not available (the first value). Would any of the participants be able to deduce the value of K in that case?

     – hax Aug 02 '16 at 01:19
  • @hax - no, if you have no information about A, then you can't deduce ANYTHING about any part of the second term in "A XOR " even if you know fully the result of the XOR operation. Suppose you know the "secret" Z. If you want to make the result to be F, for ANY F, the key A could be Z XOR F. You don't know A, and you don't know Z, you only know F - then Z can be ANYTHING. –  Aug 02 '16 at 13:41
  • Thank you. That cleared it :) – hax Aug 07 '16 at 04:33