### Permutation Based EDM: An Inverse Free BBB Secure PRF

Avijit Dutta, Mridul Nandi, and Suprita Talnikar

##### Abstract

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure $n$-bit to $n$-bit PRF constructions, i.e., \textsf{SoEM22} and \textsf{SoKAC21}, which are built on public permutations, where $n$ is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based $n$-bit to $n$-bit beyond the birthday bound secure PRF, which they refer to as \textsf{PDMMAC}. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based $n$-bit to $n$-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose $\textsf{pEDM}$, a single permutation based $n$-bit to $n$-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to $2^{2n/3}$ construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.

Available format(s)
Category
Secret-key cryptography
Publication info
Keywords
Public PermutationsEDMPDMMACExpectation Method
Contact author(s)
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
suprita45 @ gmail com
History
2021-05-25: revised
See all versions
Short URL
https://ia.cr/2021/679

CC BY

BibTeX

@misc{cryptoeprint:2021/679,
author = {Avijit Dutta and Mridul Nandi and Suprita Talnikar},
title = {Permutation Based EDM: An Inverse Free BBB Secure PRF},
howpublished = {Cryptology ePrint Archive, Paper 2021/679},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/679}},
url = {https://eprint.iacr.org/2021/679}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.