Paper 2025/1486 Original: eprint.iacr.org/2025/1486 ↗
Naor-Reingold goes Beyond-the-Birthday-Bound
Abstract
Construction of efficient and provably-secure (T)PRPs and (fixed/variable input-length) PRFs has been one of the central open problem in modern symmetric-key cryptography. Many Feistel-based constructions has been proposed and analysed to solve this problem. Inspired by some recent works, in this paper, we revisit the problem of constructing provably secure Feistel constructions using permutations as the round functions. More specifically, following the idea of Naor and Reingold, we try to reduce the number of inner permutations used by replacing them with cheap hash functions, without sacrificing optimal security. We affirmatively show that with the use of a suitable hash function along with a four-round Feistel construction, which uses only three independent permutations, one can achieve optimally secure (T)PRPs and PRFs.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2025-08-16: last updated
- 2025-08-16: published
- Short URL
- https://ia.cr/2025/1486
- License
- https://creativecommons.org/publicdomain/zero/1.0/
BibTeX
@misc{cryptoeprint:2025/1486,
author = {Avik Chakraborti and Bishwajit Chakraborty and Nilanjan Datta and Avijit Dutta and Ashwin Jha and Sougata Mandal and Hrithik Nandi and Mridul Nandi and Abishanka Saha},
title = {Naor-Reingold goes Beyond-the-Birthday-Bound},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1486},
year = {2025},
url = {https://eprint.iacr.org/2025/1486}
}