Efficient Message Authentication Codes with Combinatorial Group Testing
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
- PDF / 376,715 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 113 Downloads / 231 Views
Abstract. Message authentication code, MAC for short, is a symmetrickey 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 O(m + t) computation for m data items and t tests, irrespective of the underlying test matrix we use, under a natural security model. This greatly improves efficiency from naively applying a black-box MAC for each test, which requires O(mt) time. Based on existing group testing methods, we also present experimental results of our proposal and observe that ours runs as fast as taking single MAC tag, with speed-up from the conventional method by factor around 8 to 15 for m = 104 to 105 items. Keywords: Message authentication code testing · Data corruption · Provable security
1
·
Combinatorial group
Introduction
Message authentication code (MAC) is a symmetric-key cryptographic function for authenticity. A MAC function, F , takes a secret key K and a message M to produce a tag T = F (K, M ). A legitimate user with key K first takes (M, T ) and later verifies the validity of a tuple (M , T ), which may be corrupted from (M, T ), by computing T = F (K, M ) and checking if T = T holds or not. While MAC-based integrity check is simple and efficient, if verification fails one can not obtain any further information on what part of message is corrupted. On the other extreme side, by partitioning data into m items, say 4K-byte sectors of c Springer International Publishing Switzerland 2015 G. Pernul et al. (Eds.): ESORICS 2015, Part I, LNCS 9326, pp. 185–202, 2015. DOI: 10.1007/978-3-319-24174-6 10
186
K. Minematsu
HDD, and taking tags for each item, we can always identify all corrupted items. However this can be impractical due to a huge impact to the storage. This tread-off between the number of tags and the information on corruption can be improved by taking multiple MAC tags for overlapping parts of data items. If we carefully choose overlapping parts it allows us to identify the corrupted items if they are few. This is an interesting application of combinatorial group testing (CGT) to message authentication, as pointed out by literatures in various applications areas. Here, CGT is a method to identify defectives from a large number of samples using group tests (see Du and Hwang [15] for a goo
Data Loading...
