Paper 2020/731

The Exact Security of PMAC with Three Powering-Up Masks

Yusuke Naito

Abstract

PMAC is a rate-1, parallelizable, block-cipher-based message authentication code (MAC), proposed by Black and Rogaway (EUROCRYPT 2002). Improving the security bound is a main research topic for PMAC. In particular, showing a tight bound is the primary goal of the research, since Luykx et al.'s paper (EUROCRYPT 2016). Regarding the pseudo-random-function (PRF) security of PMAC, a collision of the hash function, or the difference between a random permutation and a random function offers the lower bound $\Omega(q^2/2^n)$ for $q$ queries and the block cipher size $n$. Regarding the MAC security (unforgeability), a hash collision for MAC queries, or guessing a tag offers the lower bound $\Omega(q_m^2/2^n + q_v/2^n)$ for $q_m$ MAC queries and $q_v$ verification queries (forgery attempts). The tight upper bound of the PRF-security $O(q^2/2^n)$ of PMAC was given by Gaž et el. (ToSC 2017, Issue 1), but their proof requires a 4-wise independent masking scheme that uses 4 $n$-bit random values. Open problems from their work are: (1) find a masking scheme with three or less random values with which PMAC has the tight upper bound for PRF-security; (2) find a masking scheme with which PMAC has the tight upper bound for MAC-security. In this paper, we consider PMAC with three powering-up masks that uses three random values for the masking scheme. We show that the PMAC has the tight upper bound $O(q^2/2^n)$ for PRF-security, which answers the open problem (1), and the tight upper bound $O(q_m^2/2^n + q_v/2^n)$ for MAC-security, which answers the open problem (2). Note that these results deal with two-key PMAC, thus showing tight upper bounds of PMACs with single-key and/or with two (or one) powering-up masks are open problems.

Note: This paper is an update version of our ToSC paper (The Exact Security of PMAC with Two Powering-Up Masks, ToSC 2019 Issue 2). In the ToSC paper, we considered PMAC with two powering-up masks, and claimed that the PMAC has the tight security bounds O(q^2/2^n) for PRF-security and O(q_m^2/2^n+q_v/2^n) for MAC-security. However, Nandi et al. pointed out a bug of the proofs. Hence, we change the masking scheme with three powering-up masks, and prove that the PMAC has the tight security bounds.