Cryptology ePrint Archive: Report 2021/679

Permutation Based EDM: An Inverse Free BBB Secure PRF

Avijit Dutta and 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.

Category / Keywords: secret-key cryptography / Public Permutations, EDM, PDMMAC, Expectation Method

Original Publication (in the same form): IACR-FSE-2022

Date: received 24 May 2021, last revised 25 May 2021

Contact author: avirocks dutta13 at gmail com, mridul nandi at gmail com, suprita45 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210525:182900 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]