Constructions of Beyond-Birthday Secure PRFs from Random Permutations, Revisited - Jiehui Nan; Ping Zhang; Honggang Hu (Entropy, 2021)
In CRYPTO 2019, Chen et al. showed how to construct pseudorandom functions (PRFs) from random permutations (RPs), and they gave one beyond-birthday secure construction from sum of Even-Mansour, namely <semantics>SoEM22</semantics> in the single-key setting. In this paper, we improve their work by proving the multi-key security of <semantics>SoEM22</semantics>, and further tweaking <semantics>SoEM22</semantics> but still preserving beyond birthday bound (BBB) security. Furthermore, we use only one random permutation to construct parallelizable and succinct beyond-birthday secure PRFs in the multi-key setting, and then tweak this new construction. Moreover, with a slight modification of our constructions of tweakable PRFs, two parallelizable nonce based MACs for variable length messages are obtained.