Paper 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.
- Keywords
- PRFTweakable PermutationFeistelH-Coefficient TechniqueMirror Theory
- Contact author(s)
-
avik chakraborti @ tcgcrest org
bishumathynwa @ gmail com
nilanjan datta @ tcgcrest org
avirocks dutta13 @ gmail com
letterstoashwin @ gmail com
sougata mandal @ tcgcrest org
hrithik nandi @ tcgcrest org
mridul nandi @ gmail com
sahaa1993 @ gmail com - History
- 2025-08-20: approved
- 2025-08-16: received
- See all versions
- Short URL
- https://ia.cr/2025/1486
- License
-
CC0
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}
}
