Tight security analysis of the public permutation-based \(\mathsf{PMAC\_Plus} \) (Q6605894)

Pseudo-random functions (PRF) are one of the fundamental building blocks of modern cryptography. Therefore, it is paramount to have secure and efficient constructions.\N\NSome of the most commonly used block cipher-based PRFs offer a security bound of up to \(2^{n/2}\) adversarial queries, where \(n\) is the block size. These constructions are said to provide birthday-bound security. In practice, instantiating birthday bounds secure PRF constructions with block ciphers that have a moderate block size can offer enough security. For example, in the case of instantiating the PMAC construction with AES-128, we obtain that \(2^{48}\) adversarial queries are needed for breaking the scheme with a success probability of \(2^{-10}\), assuming that the longest message is \(2^{16}\). Note that, in constrained environments, message sizes are often less than \(1 \text{MB} = 2^{23}\) bits.\N\NHowever, the growing trend of designing lightweight ciphers suitable for constrained environments (e.g. Internet of Things devices) leads to the need to construct PRFs that provide beyond-birthday-bound security. For instance, if we take the same PMAC construction and instantiate it with PRESENT (a lightweight block cipher), the security is reduced to only \(2^{16}\) adversarial queries. Therefore, it is not secure to instantiate birthday-bound secure PRFs with lightweight block ciphers. In this context, several such constructions have emerged.\N\NThe authors of this paper give an extensive overview of them. They also argue that block cipher-based designs are over-engineered and that simpler alternatives are available namely permutation-based constructions. A comparison between permutation-based PRFs and MACs is provided in terms of the number of permutations/keys, and the overall security margin.\N\NIn this context, the authors remark that previous beyond-the-birthday-bound secure PRF proposals based on permutations rely on an almost-xor-universal hash function. As a result, implementing such designs requires more resources than a design based solely on a permutation. This is exactly the solution proposed by the authors: a design based solely on a public permutation that achieves beyond birthday-bound security. Therefore, making it suitable for lightweight cipher instantiations. Additionally, their proposal is constructed such that it is parallel.\N\NAlthough the proposed solution is simple, the authors take great care to rigorously prove the security of the scheme, devoting 23 out of 35 pages to the security proof and complementary key-recovery attack. It is important to note that the provided security bound is tight.