Paper 2024/338
Tight Indistinguishability Bounds for the XOR of Independent Random Permutations by Fourier Analysis
Abstract
The XOR of two independent permutations (XoP) is a wellknown construction for achieving security beyond the birthday bound when implementing a pseudorandom function using a block cipher (i.e., a pseudorandom permutation). The idealized construction (where the permutations are uniformly chosen and independent) and its variants have been extensively analyzed over nearly 25 years. The bestknown asymptotic informationtheoretic indistinguishability bound for the XoP construction is $O(q/2^{1.5n})$, derived by Eberhard in 2017, where $q$ is the number of queries and $n$ is the block length. A generalization of the XoP construction outputs the XOR of $r \geq 2$ independent permutations, and has also received significant attention in both the singleuser and multiuser settings. In particular, for $r = 3$, the bestknown bound (obtained by Choi et al. [ASIACRYPT'22]) is about $q^2/2^{2.5 n}$ in the singleuser setting and $\sqrt{u} q_{\max}^2/2^{2.5 n}$ in the multiuser setting (where $u$ is the number of users and $q_{\max}$ is the number of queries per user). In this paper, we prove an indistinguishability bound of $q/2^{(r  0.5)n}$ for the (generalized) XoP construction in the singleuser setting, and a bound of $\sqrt{u} q_{\max}/2^{(r  0.5)n}$ in the multiuser setting. In particular, for $r=2$, we obtain the bounds $q/2^{1.5n}$ and $\sqrt{u} q_{\max}/2^{1.5n}$ in singleuser and multiuser settings, respectively. For $r=3$ the corresponding bounds are $q/2^{2.5n}$ and $\sqrt{u} q_{\max}/2^{2.5n}$. All of these bounds hold assuming $q < 2^{n}/2$ (or $q_{\max} < 2^{n}/2$). Compared to previous works, we improve all the bestknown bounds for the (generalized) XoP construction in the multiuser setting, and the bestknown bounds for the generalized XoP construction for $r \geq 3$ in the singleuser setting (assuming $q \geq 2^{n/2}$). For the basic twopermutation XoP construction in the singleuser setting, our concrete bound of $q/2^{1.5n}$ stands in contrast to the asymptotic bound of $O(q/2^{1.5n})$ by Eberhard. Since all of our bounds are matched (up to constant factors) for $q \geq 2^{n/2}$ by attacks published by Patarin in 2008 (and their generalizations to the multiuser setting), they are all tight. We obtain our results by Fourier analysis of Boolean functions. Most of our technical work involves bounding (sums of) Fourier coefficients of the density function associated with sampling without replacement. While the proof of Eberhard relies on similar bounds, our proof is elementary and simpler.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2024
 Contact author(s)
 dinuri @ bgu ac il
 History
 20240415: revised
 20240226: received
 See all versions
 Short URL
 https://ia.cr/2024/338
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/338, author = {Itai Dinur}, title = {Tight Indistinguishability Bounds for the {XOR} of Independent Random Permutations by Fourier Analysis}, howpublished = {Cryptology ePrint Archive, Paper 2024/338}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/338}}, url = {https://eprint.iacr.org/2024/338} }