Paper 2021/679

Permutation Based EDM: An Inverse Free BBB Secure PRF

Avijit Dutta, Mridul Nandi, and Suprita Talnikar


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)
Secret-key cryptography
Publication info
Published by the IACR in FSE 2022
Public PermutationsEDMPDMMACExpectation Method
Contact author(s)
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
suprita45 @ gmail com
2021-05-25: revised
2021-05-25: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.