Paper 2009/047
On Approximating Addition by Exclusive OR
Palash Sarkar
Abstract
Let $X^{(1)},X^{(2)},\ldots,X^{(n)}$ be independent and uniformly distributed over the nonnegative integers $\{0,1,\ldots,2^i1\}$; $S^{(n)}=X^{(1)}+X^{(2)}+\cdots+X^{(n)}$ and $L^{(n)}=X^{(1)}\oplus X^{(2)}\oplus \cdots\oplus X^{(n)}$. Denote the $i$th bits of $S^{(n)}$ and $L^{(n)}$ by $S^{(n)}_i$ and $L^{(n)}_i$ respectively. We show that as $i\rightarrow \infty$, $\pr[S^{(n)}_i=L^{(n)}_i]\rightarrow \gamma^{(n)}= \frac{1}{2}+\frac{2^{n+1}(2^{n+1}1)}{2(n+1)}\times\frac{b_{n+1}}{n!}$, where $b_n$ is the $n$th Bernoulli number. As a consequence, $\gamma^{(2r)}=1/2$ for every $r$; and we show that $\gamma^{(2r+1)}\rightarrow 1/2$ as $r\rightarrow \infty$. For small values of $r$, $\gamma^{(2r+1)}$ is significantly different from $1/2$; for example $\gamma^{(3)}=1/3$ and $\gamma^{(5)}=17/30$. The behaviour of $\gamma^{(n)}$ for even and odd values of $n$ was earlier shown by Staffelbach and Meier without actually obtaining the formula mentioned above. For every fixed $n\geq 2$, we give a simple method for computing $\pr[S^{(n)}_i=L^{(n)}_i]$ for each $i\geq 0$. The expression involving Bernoulli numbers is arrived at via the Eulerian number triangle which in turn arises in relation to the stationary distribution of a Markov chain formed by the carry values.
Note: We would like to thank Willi Meier for pointing out an earlier work (from Crypto 1990) of his (coauthored with Othmar Staffelbach). This revision explains the relation between the eprint report and the earlier work.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)
 palash @ isical ac in
 History
 20090203: last of 2 revisions
 20090129: received
 See all versions
 Short URL
 https://ia.cr/2009/047
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/047, author = {Palash Sarkar}, title = {On Approximating Addition by Exclusive OR}, howpublished = {Cryptology ePrint Archive, Paper 2009/047}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/047}}, url = {https://eprint.iacr.org/2009/047} }