Paper 2024/929

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 π:{0,1}n{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 π. Modeling π as a uniformly chosen permutation, several previous works proved a tight information-theoretic indistinguishability bound for SXoP[2,n] of about q/2n, where q 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Contact author(s)
dinuri @ bgu ac il
History
2024-06-12: approved
2024-06-10: received
See all versions
Short URL
https://ia.cr/2024/929
License
Creative Commons Attribution
CC BY

BibTeX

@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.