I am wondering if you have an input $x_{1}$ and you XOR it with an unknown random second input $x_{2}$, is it safe to say that the resulting $x_{1}\oplus x_{2}$ will be random ?

The final idea would be to first fix all the $x_{i}$ for $i>0$ so that one cannot change its $x_{i}$ afterwards, then set $x_{0}$ to a random value. Then, person 1 $p_{1}$ gets a value $a_{1}=x_{0}\oplus x_{1}$, $p_{2}$ gets $a_{2}=x_{2}\oplus a_{1}$... In the end person $p_{i}$ gets the value $a_{i}=x_{i}\oplus a_{i-1}$ $\forall i$

The point of this is to choose someone at random among them so we could pick $p_{min}$ where $a_{min} = min_{i}(a_{i})$.

Do you think it would be safe to choose someone at random in this way ? We probably need to make sure that two different people won't have the same $x_{i}$ otherwise there could be two people with the same $a_{i}$ value but apart from that I don't see any weakness where one could improve its chances at being the chosen one, do you see one?

Edit: I have to add that all of the $x_{i}$ will also be picked at random otherwise there would be a clear link between one $x_{i}$ and the previous $a_{i-1}$.

  • $\begingroup$ random x-or non-random is random. secret x-or non-secret is secret. $\endgroup$ – kelalaka Apr 27 at 13:49
  • $\begingroup$ Alright thank you $\endgroup$ – Dayu Apr 27 at 15:26
  • $\begingroup$ What's the end goal? To pick a random person out of $n$ persons? What's your attack model? Who can view which messages? Who may conspire together? $\endgroup$ – cisnjxqu Apr 27 at 15:49
  • $\begingroup$ Being random is not enough, but if $x_2$ is uniformly distributed over $\{0,1\}^n$ then $x_1 ⊕ x_2$ is uniformly distributed over $\{0,1\}^n$ regardless of distribution of $x_1$ $\endgroup$ – Manish Adhikari Apr 28 at 6:34
  • $\begingroup$ Yes the end goal is to pick a random person out of $n$. You consider that some of them may want to be acting together to force the election of one of them but the vast majority is honest. Also, nobody can see the value of any $a_{i}$ because homomorphic encryption will be used all along. Therefore, one has to encrypt its $x_{i}$ homomorphically before computing the XOR with the previous $a_{i}$ and passing the homomorphic result to the next one who will do the same and so on. $\endgroup$ – Dayu Apr 28 at 7:37

I am wondering if you have an input $x_{1}$ and you XOR it with an unknown random second input $x_{2}$, is it safe to say that the resulting $x_{1}\oplus x_{2}$ will be random ?

Yes, this is literally what proofs of the security of one-time pads come down to. Informally it comes down to the following observations:

  1. If $x_2$ is random, then it means that each of its bits is 0 or 1 with equal probability and independent of all other bits in $x_2$;
  2. If $x_2$ has those properties, then $x_1 \oplus x_2$ also must.

And this really comes down that after the XOR, for each bit in $x_1$ you get with equal probability, either the original bit from $x_1$ or the flipped bit, and that you XOR all of the bits independently of all other ones.

  • $\begingroup$ Alright thanks, I should be able to use it in my case then and the focus has to be on making sure $x_{2}$ is really random and impossible to force to some value. $\endgroup$ – Dayu Apr 28 at 9:19

If plaintext $p$ is a variable with any distribution over $\{0,1\}^n$ and $k$ is an independent uniform random variable over $\{0,1\}^n$ then ciphertext $c = p ⊕ k$ is a uniform random variable over $\{0,1\}^n$.

  • 2
    $\begingroup$ This is only true if $p$ and $k$ are independent. If they have any correlation between them then it doesn’t hold. As an extreme example, let $p$ and $k$ be equal (but uniform). Then their XOR is always zero. $\endgroup$ – Chris Peikert Apr 28 at 11:28
  • $\begingroup$ @ChrisPeikert Uniform random implies that it is independent. $\endgroup$ – forest Apr 29 at 0:11
  • 1
    $\begingroup$ No, it doesn’t. Independence is a separate matter from the marginal distributions of the two variables. $\endgroup$ – Chris Peikert Apr 29 at 0:13
  • $\begingroup$ @ChrisPeikert I've edited the answer. However I was under the impression that two random variables are by definition independent, as is a random variable and a non-random variable (regardless of distribution). $\endgroup$ – forest Apr 29 at 0:15

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.