Aggregate message authentication codes (AMACs) with on-the-fly verification
Aggregate message authentication codes (AMACs) merge multiple authenticators for multiple receivers in multicast networks. We investigate this security notion, revise the definition, derive the lower bound, and present a generic construction through Bloom filters. Different from former research, we especially focus on the new property of AMACs: on-the-fly verification, which means that given the aggregated tag, each single message can be verified without obtaining other messages, i.e., the time for verifying a single message takes time complexity \(\mathcal{O }(1)\), compared to regular MAC schemes. We derive the security lower bound of such type of AMACs and present a generic approach to build them from essentially any standard MAC scheme by Bloom filter technique. Moreover, we achieve the theoretical lower bound on security strength by adopting optimal compressed Bloom filters.
aggregation authentication bloom filters broadcast authentication merkle tree