Welcome to the resource topic for 2024/338
Title:
Tight Indistinguishability Bounds for the XOR of Independent Random Permutations by Fourier Analysis
Authors: Itai Dinur
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 information-theoretic indistinguishability bound for the XoP construction (due to Dutta, Nandi and Saha~[IEEE Trans. Inf. Theory]) is about q^2/2^{2n}, where q is the number of queries and n is the block length.
The XoP construction has also been recently analyzed in the multi-user setting and the best known bound for it (by Chen, Choi, and Lee~[CRYPTO’23]) is about \sqrt{u} q_{\max}^2/2^{2n}, where u is the number of users and q_{\max} is the number of queries per user.
A generalization of the XoP construction outputs the XOR of r \geq 2 independent permutations, and has also received significant attention.
In this paper, we improve all previous bounds obtained in the literature for the (generalized) XoP construction when q > 2^{n/2} (assuming q < 2^{n}/2). Specifically, for the basic XoP construction with r=2, we obtain an indistinguishability bound of q/2^{1.5n} in the single-user setting and \sqrt{u} q_{\max}/2^{1.5n} in the multi-user setting. Hence, if q_{\max} = \Theta(2^{n}) (and q_{\max} < 2^{n}/2), then our bound of \sqrt{u} q_{\max}/2^{1.5n} implies that the adversary’s advantage remains negligible as long as u = o(2^n). On the other hand, with the previous bound of \sqrt{u} q_{\max}^2/2^{2n}, the adversary’s advantage may already be a constant with a single user
(u=1).
For the generalized XoP construction, we obtain a bound of q/2^{(r - 0.5)n} in the single-user setting and \sqrt{u} q_{\max}/2^{(r - 0.5)n} in the multi-user setting. Consequently, the gap between our results and the best previous ones increases sharply with r. For example, the best-known bound for r = 3, obtained by Choi et al. [ASIACRYPT’22] (in the multi-user setting), is about \sqrt{u} q_{\max}^2/2^{2.5 n}, while we obtain \sqrt{u} q_{\max}/2^{2.5 n}.
Since all of our bounds are matched (up to constant factors) for q > 2^{n/2} 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. Yet, most of our technical work is not directly related to the analyzed cryptosystems. It rather involves analyzing fundamental Fourier properties of the density function associated with sampling without replacement from the domain \{0,1\}^n. We believe that this analysis is of broad interest.
ePrint: https://eprint.iacr.org/2024/338
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .