International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: The Exact Security of PMAC with Two Powering-Up Masks

Authors:
Yusuke Naito , Mitsubishi Electric Corporation, Kanagawa
Download:
DOI: 10.13154/tosc.v2019.i2.125-145
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8316
Search ePrint
Search Google
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 Ω(q2/2n) 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 Ω(q2m /2n + qv/2n) for qm MAC queries and qv verification queries (forgery attempts). The tight upper bound of the PRF-security O(q2/2n) of PMAC was given by Gaži 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 two powering-up masks that uses two random values for the masking scheme. Using the structure of the powering-up masking scheme, we show that the PMAC has the tight upper bound O(q2/2n) for PRF-security, which answers the open problem (1), and the tight upper bound O(q2m /2n + qv/2n) for MAC-security, which answers the open problem (2). Note that these results deal with two-key PMACs, thus showing tight upper bounds of PMACs with single-key and/or with one powering-up mask are open problems.
BibTeX
@article{tosc-2019-29507,
  title={The Exact Security of PMAC with Two Powering-Up Masks},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 2},
  pages={125-145},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8316},
  doi={10.13154/tosc.v2019.i2.125-145},
  author={Yusuke Naito},
  year=2019
}