Paper 2019/404
Efficient Message Authentication Codes with Combinatorial Group Testing
Kazuhiko Minematsu
Abstract
Message authentication code, MAC for short, is a symmetric-key cryptographic function for authenticity. A standard MAC verification only tells whether the message is valid or invalid, and thus we can not identify which part is corrupted in case of invalid message.
In this paper we study a class of MAC functions that enables to identify the part of corruption, which we call group testing MAC (GTM). This can be seen as an application of a classical (non-adaptive) combinatorial group testing to MAC.
Although the basic concept of GTM (or its keyless variant) has been proposed in various application areas, such as data forensics and computer virus testing, they rather treat the underlying MAC function as a black box, and exact computation cost for GTM seems to be overlooked.
In this paper, we study the computational aspect of GTM, and show that a simple yet non-trivial extension of parallelizable MAC (PMAC) enables
Note: Minor corrections on technical backgrounds, tables and figures.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Minor revision. ESORICS 2015
- Keywords
- Message authentication codeCombinatorial group testingData corruptionProvable security.
- Contact author(s)
- k-minematsu @ ah jp nec com
- History
- 2019-04-25: revised
- 2019-04-22: received
- See all versions
- Short URL
- https://ia.cr/2019/404
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/404, author = {Kazuhiko Minematsu}, title = {Efficient Message Authentication Codes with Combinatorial Group Testing}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/404}, year = {2019}, url = {https://eprint.iacr.org/2019/404} }