Paper 2022/1609

Forking Sums of Permutations for Optimally Secure and Highly Efficient PRFs

Avijit Dutta, Institute for Advancing Intelligence, TCG-CREST, Kolkata, India
Jian Guo, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Eik List, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

The desirable encryption scheme possesses high PRF security, high efficiency, and the ability to produce variable-length outputs. Since designing dedicated secure PRFs is difficult, a series of works was devoted to building optimally secure PRFs from the sum of independent permutations (SoP), Encrypted Davies-Meyer (EDM), its Dual (EDMD), and the Summation-Truncation Hybrid (STH) for variable output lengths, which can be easily instantiated from existing permutations. For increased efficiency, reducing the number of operations in established primitives has been gaining traction: Mennink and Neves pruned EDMD to FastPRF, and Andreeva et al. introduced ForkCiphers, which take an n-bit input, process it through a reduced-round permutation, fork it into two states, and feed each of them into another reduced-round permutation to produce a 2n-bit output. The constructions above can be used in secure variable-length modes or generalizations such as MultiForkCiphers. In this paper, we suggest a framework of those constructions in terms of the three desiderata: we span the spectrum of (1) output length vs. PRF security, (2) full vs. round-reduced primitives, and (3) fixed- vs. variable-length outputs. From this point of view, we identify remaining gaps in the spectrum and fill them with the proposal of several highly secure and efficient fixed- and variable-output-length PRFs. We fork SoP and STH to ForkPRF and ForkSTH, extend STH to the variable-output-length construction STHCENC, which bridges the gap between CTR mode and CENC,and propose ForkCENC, ForkSTHCENC, ForkEDMD, as well as ForkEDM-CTR as the variable-output-length and round-reduced versions of CENC, STH, FastPRF, and FastPRF's dual, respectively. Using recent results on Patarin's general Mirror Theory, we have proven that almost all our proposed PRFs are optimally secure under the assumption that the permutations are pairwise independent and random and STH achieves the optimal security depending on the output length. Our constructions can be highly efficient in practice. We propose efficient instantiations from round-reduced AES and back it with the cryptanalysis lessons learned from existing earlier analysis of AES-based primitives.

Available format(s)
Secret-key cryptography
Publication info
Provable security H-coefficient technique sum of permutations AES Forkcipher
Contact author(s)
avirocks dutta13 @ gmail com
guojian @ ntu edu sg
eik list @ ntu edu sg
2022-11-21: approved
2022-11-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Avijit Dutta and Jian Guo and Eik List},
      title = {Forking Sums of Permutations for Optimally Secure and Highly Efficient PRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1609},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.