Abstract

The aggregate message authentication code (aggregate MAC) is a cryptographic primitive which can compress MAC tags on multiple messages into a short aggregate MAC tag. Furthermore, the sequential aggregate MAC can check not only the validity of multiple messages but also the (sequential) order of messages. In this paper, we introduce a new model of sequential aggregate MACs (SAMACs) where an aggregation algorithm generates a sequential aggregate tag depending only on any multiple and independent MAC tags with no secret-key, and we formally define security in this model. We also propose a generic construction of sequential aggregate MACs starting from any MACs without changing the structure of the MACs. This property is useful to make the existing networks more efficient by combining the aggregation algorithm with various MAC schemes already existing in the networks. Furthermore, by extending the results of SAMAC, we also introduce a sequential aggregate MAC which has detecting functionality (SAMD). The SAMD enables us to specify an invalid message or an invalid order of a certain message. We formalize the security of SAMD and provide a generic construction of SAMD in the random oracle model from any MACs and non-adaptive group testing protocols with formal security proofs.