1. Constructions of Beyond-Birthday Secure PRFs from Random Permutations, Revisited
- Author
-
Honggang Hu, Jiehui Nan, and Ping Zhang
- Subjects
Pseudorandom number generator ,Discrete mathematics ,Parallelizable manifold ,biology ,Computer science ,beyond birthday bound ,Science ,Physics ,QC1-999 ,General Physics and Astronomy ,Construct (python library) ,Random permutation ,Variable length ,biology.organism_classification ,Astrophysics ,Article ,GeneralLiterature_MISCELLANEOUS ,QB460-466 ,Chen ,nonce based MACs ,Tweaking ,H-Coefficient technique ,Cryptographic nonce ,multi-key security - Abstract
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 SoEM22 in the single-key setting. In this paper, we improve their work by proving the multi-key security of SoEM22, and further tweaking SoEM22 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.
- Published
- 2021
- Full Text
- View/download PDF