### 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.

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.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
palash @ isical ac in
History
2009-02-03: last of 2 revisions
See all versions
Short URL
https://ia.cr/2009/047 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}
} Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.