Combining Outputs of a Random Permutation: New Constructions and Tight Security Bounds by Fourier Analysis
Itai Dinur, Ben-Gurion University of the Negev
Abstract
We consider constructions that combine outputs of a single permutation 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) XORs the outputs of 2 domain-separated calls to .
Modeling as a uniformly chosen permutation, several previous works proved a tight information-theoretic indistinguishability bound for SXoP of about , where is the number of queries. On the other hand, tight bounds are unknown for the generalized variant (denoted SXoP) which XORs the outputs of domain-separated calls to a uniform permutation.
In this paper, we obtain two results. Our first result improves the known bounds for SXoP for all (constant) (assuming is not too large) in both the single-user and multi-user settings. In particular, for , our bound is about (where is the number of users and is the maximal number of queries per user), improving the best-known previous result by a factor of at least .
For odd , our bounds are tight for , as they match known attacks. For even , 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 bits by efficiently combining outputs of 2 calls to a permutation on , and achieve multi-user security of about . Then, inspired by the CENC construction of Iwata [FSE'06], we further extend this family to output bits by efficiently combining outputs of 3 calls to a permutation on . The extended construction has similar multi-user security of .
The new single-user () bounds of for both families should be contrasted with the previously best-known bounds of , obtained by the comparable constructions of SXoP and CENC.
All of our bounds are proved by Fourier analysis, extending the provable security toolkit in this domain in multiple ways.
@misc{cryptoeprint:2024/929,
author = {Itai Dinur},
title = {Combining Outputs of a Random Permutation: New Constructions and Tight Security Bounds by Fourier Analysis},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/929},
year = {2024},
url = {https://eprint.iacr.org/2024/929}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.