Welcome to the resource topic for 2024/929
Title:
Combining Outputs of a Random Permutation: New Constructions and Tight Security Bounds by Fourier Analysis
Authors: Itai Dinur
Abstract:We consider constructions that combine outputs of a single permutation \pi:\{0,1\}^n \rightarrow \{0,1\}^n using a public function. These are popular constructions for achieving security beyond the birthday bound when implementing a pseudorandom function using a block cipher (i.e., a pseudorandom permutation). One of the best-known constructions (denoted SXoP$[2,n]) XORs the outputs of 2 domain-separated calls to \pi$.
Modeling \pi as a uniformly chosen permutation, several previous works proved a tight information-theoretic indistinguishability bound for SXoP$[2,n]$ of about q/2^{n}, where q is the number of queries. On the other hand, tight bounds are unknown for the generalized variant (denoted SXoP$[r,n]$) which XORs the outputs of r>2 domain-separated calls to a uniform permutation.
In this paper, we obtain two results. Our first result improves the known bounds for SXoP$[r,n]$ for all (constant) r \geq 3 (assuming q \leq O(2^n/r) is not too large) in both the single-user and multi-user settings. In particular, for q=3, our bound is about \sqrt{u}q_{\max}/2^{2.5n} (where u is the number of users and q_{\max} is the maximal number of queries per user), improving the best-known previous result by a factor of at least 2^n.
For odd r, our bounds are tight for q > 2^{n/2}, as they match known attacks. For even r, we prove that our single-user bounds are tight by providing matching attacks.
Our second and main result is divided into two parts. First, we devise a family of constructions that output n bits by efficiently combining outputs of 2 calls to a permutation on \{0,1\}^n, and achieve multi-user security of about \sqrt{u} q_{\max}/2^{1.5n}. Then, inspired by the CENC construction of Iwata [FSE’06], we further extend this family to output 2n bits by efficiently combining outputs of 3 calls to a permutation on \{0,1\}^n. The extended construction has similar multi-user security of \sqrt{u} q_{\max}/2^{1.5n}.
The new single-user (u=1) bounds of q/2^{1.5n} for both families should be contrasted with the previously best-known bounds of q/2^n, obtained by the comparable constructions of SXoP$[2,n]$ and CENC.
All of our bounds are proved by Fourier analysis, extending the provable security toolkit in this domain in multiple ways.
ePrint: https://eprint.iacr.org/2024/929
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 .