Aggregation schemes combine several MACs into a single value in order to
reduce the communication overhead. A prominent example is the MAC scheme by
Katz and Lindell (CT-RSA 2008) which supports aggregation in arbitrary order (as opposed
to many schemes allowing only sequential aggregation). Here we revisit their unforgeability
notion and discuss that the definitions do not prevent “mixing” attacks in which the adversary
combines several aggregates. In particular, we show concrete attacks on these schemes.

We thus provide the stronger security notion of aggregation unforgeability, capturing a much broader
class of combination attacks. We then present aggregation-unforgeable constructions somewhat lying
between non-ordered and sequential solutions. That is, we propose the notion of history-free sequential
aggregation, a refinement which basically says that the aggregation algorithm must not depend
on the preceding messages in the sequence but only on the shorter input aggregate and the local
message. We finally show how to build such history-free protocols.