**On Approximating Addition by Exclusive OR**

*Palash Sarkar*

**Abstract: **Let $X^{(1)},X^{(2)},\ldots,X^{(n)}$ be independent and uniformly distributed over the
non-negative integers $\{0,1,\ldots,2^i-1\}$; $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.

**Category / Keywords: **secret-key cryptography /

**Date: **received 27 Jan 2009, last revised 3 Feb 2009

**Contact author: **palash at isical ac in

**Available format(s): **PDF | BibTeX Citation

**Note: **We would like to thank Willi Meier for pointing out an earlier work (from Crypto 1990) of his (co-authored with Othmar Staffelbach). This revision explains the relation between the eprint report and the earlier work.

**Version: **20090203:125433 (All versions of this report)

**Short URL: **ia.cr/2009/047

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]