8
$\begingroup$

Basic question about XOR and entropy - given a set $S$ of pseudo-random numbers in the range $[0,b]$, will XORing them produce a new pseudo-random number in $[0,b]$ or will the operation decrease the entropy? In the case that some numbers in $S$ not being random. e.g. selected according to some deterministic process - how does this effect the randomness of the XORed result? Would also appreciate links to any relevant math/crypto lit about these kind of problems.

Thanks so much!

$\endgroup$
  • $\begingroup$ "XORing them"--with what? Among themselves? With something else? $\endgroup$ – user47922 Jun 10 '17 at 1:15
  • 1
    $\begingroup$ Sorry for not being clear enough - XORing the numbers themselves. $\endgroup$ – avive Jun 10 '17 at 12:06
14
$\begingroup$

Assuming that $b = 2^k-1$ for some positive integer $k$, XORing two (or more) numbers in the range $[0,b]$ will indeed yield a number in the same range.

If the numbers are random, uniformly distributed over the range and independent, then the result will also be random and uniformly distributed. In fact, we can even prove a stronger result saying that if even one of the numbers is random and uniformly distributed over the whole range, and independent of the others, then the result will be random and uniformly distributed.

(There are a variety of ways to prove this. Probably the most straightforward way is to observe that the map $x \mapsto x \oplus c$ is a bijection over the range $[0,b]$ regardless of the value of the constant $c$. Thus, if $x$ is uniformly distributed over the range, then so is $x \oplus c$; and since this is true for any constant $c$, it's also true even if $c$ itself is a random variable, as long as it doesn't depend on $x$. For the specific case of XOR, you can also first show the same result for each bit of the number, i.e. reduce the problem only to the case $b=1$, and then generalize to multiple bits.)

Effectively the same result also holds, basically by definition, even if the numbers are only pseudorandom, i.e. computationally indistinguishable from true random numbers. That's because, if the result of XORing them was not indistinguishable from a truly random number, then this would provide an efficient way to distinguish the original numbers from truly random ones, thus showing that they weren't really pseudorandom in the first place.

Note, however, the the assumption of independence (or indistinguishability from independent random numbers) is important. Otherwise, there are trivial counterexamples, like picking a truly random number $x$ uniformly from $[0,b]$, and then letting $y = x$. Thus, both $x$ and $y$ on their own are truly random and uniformly distributed, but $x \oplus y = x \oplus x = 0$.

$\endgroup$
  • $\begingroup$ Thank you very much for your thoughtful explanation! Regarding independence - can you please try to clarify your last point point? Assuming some of the numbers are not independent random numbers, for example, chosen by some kind of consensus algorithm, and only one of the numbers is guaranteed to independent and pseudorandom from all other numbers - is the XORing result in this case pseudorandom or not? Your first part of the answer indicates that it will hold while the last paragraph mentions an assumption of independence of all numbers. $\endgroup$ – avive Jun 10 '17 at 12:17
  • 1
    $\begingroup$ Yes, it's sufficient for one of the numbers to be independent from the others (and uniformly distributed). For example, if you have three numbers $x$, $y$ and $z$, with $x$ being uniformly distributed and independent of $y$ and $z$, then the map $x \mapsto x \oplus y \oplus z$ is still a bijection for any values of $y$ and $z$. Thus, since each value of $x \in [0,b]$ is equally likely, regardless of what values $y$ and $z$ take, then each value of $x \oplus y \oplus z$ will also be equally likely. $\endgroup$ – Ilmari Karonen Jun 10 '17 at 12:28
  • $\begingroup$ I add a blogpost by djb: blog.cr.yp.to/20140205-entropy.html $\endgroup$ – ddddavidee Jun 10 '17 at 17:07
  • $\begingroup$ I have a question regarding the answer given above. You say that XORing random numbers in a sequence with themselves will generate another random sequence. But more specifically, does the order in which the XORing is done matter? Will I be able to XOR the first number with all others, the second with all others and so on following this pattern and still get randomness? Or is the XORing operation also required to be between random pairs in order to actually generate a random sequence? Thanks for your help! $\endgroup$ – Giulia Ippoliti Nov 28 at 2:41
  • $\begingroup$ @GiuliaIppoliti: I'm not sure I understand what you're asking. The XOR operation is commutative and associative (just like ordinary addition), so the order in which you XOR the numbers doesn't change the result: $a \oplus b = b \oplus a$ and $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ for all $a$, $b$, $c$. Also, I did not say that "XORing random numbers in a sequence with themselves will generate another random sequence" (whatever that means). I said that XORing (any) two or more independent uniformly distributed random numbers will produce a (single) uniformly distributed random number. $\endgroup$ – Ilmari Karonen Nov 28 at 7:30

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.