Tight Indistinguishability Bounds for the XOR of Independent Random Permutations by Fourier Analysis
Itai Dinur, Ben-Gurion University, Israel
Abstract
The XOR of two independent permutations (XoP) is a well-known 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 best-known asymptotic information-theoretic indistinguishability bound for the XoP construction is , derived by Eberhard in 2017, where is the number of queries and is the block length.
A generalization of the XoP construction outputs the XOR of independent permutations, and has also received significant attention in both the single-user and multi-user settings. In particular, for , the best-known bound (obtained by Choi et al. [ASIACRYPT'22]) is about in the single-user setting and in the multi-user setting (where is the number of users and is the number of queries per user).
In this paper, we prove an indistinguishability bound of for the (generalized) XoP construction in the single-user setting, and a bound of in the multi-user setting. In particular, for , we obtain the bounds and in single-user and multi-user settings, respectively. For the corresponding bounds are and . All of these bounds hold assuming (or ).
Compared to previous works, we improve all the best-known bounds for the (generalized) XoP construction in the multi-user setting, and the best-known bounds for the generalized XoP construction for in the single-user setting (assuming ). For the basic two-permutation XoP construction in the single-user setting, our concrete bound of stands in contrast to the asymptotic bound of by Eberhard.
Since all of our bounds are matched (up to constant factors) for by attacks published by Patarin in 2008 (and their generalizations to the multi-user 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.
@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},
url = {https://eprint.iacr.org/2024/338}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.