Symmetric-key Corruption Detection : When XOR-MACs Meet Combinatorial Group Testing

Kazuhiko Minematsu and Norifumi Kamiya

Abstract

We study a class of MACs, which we call corruption detectable MAC, that is able to not only check the integrity of the whole message, but also detect a part of the message that is corrupted. It can be seen as an application of the classical Combinatorial Group Testing (CGT) to message authentication. However, previous work on this application has inherent limitation in communication. We present a novel approach to combine CGT and a class of linear MACs (XOR-MAC) that enables to break this limit. Our proposal, XOR-GTM, has a significantly smaller communication cost than any of the previous ones, keeping the same corruption detection capability. Our numerical examples for storage application show a reduction of communication by a factor of around 15 to 70 compared with previous schemes. XOR-GTM is parallelizable and is as efficient as standard MACs. We prove that XOR-GTM is provably secure under the standard pseudorandomness assumptions.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.ESORICS 2019
DOI
10.1007/978-3-030-29959-0_29
Keywords
MACCorruption DetectionCombinatorial Group TestingXOR-MAC
Contact author(s)
k-minematsu @ ah jp nec com
kamiya @ bc jp nec com
History
Short URL
https://ia.cr/2019/1127

CC BY

BibTeX

@misc{cryptoeprint:2019/1127,
author = {Kazuhiko Minematsu and Norifumi Kamiya},
title = {Symmetric-key Corruption Detection : When XOR-MACs Meet Combinatorial Group Testing},
howpublished = {Cryptology ePrint Archive, Paper 2019/1127},
year = {2019},
doi = {10.1007/978-3-030-29959-0_29},
note = {\url{https://eprint.iacr.org/2019/1127}},
url = {https://eprint.iacr.org/2019/1127}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.