Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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!
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$.
