Threat Model and security guarantee

We design our schemes to be secure against a powerful adversary with the following capabilities:

• Full control over the network. The adversary can eavesdrop, capture, drop, resend, delay, and alter packets.
• The adversary has access to a fast network with negligible delay.
• The adversary's computational resources may be very large, but not unbounded. In particular, this means that the adversary can perform efficient computations, such as computing a reasonable number of pseudo-random function applications and MACs with negligible delay. Nonetheless the adversary cannot invert a pseudorandom function (or distinguish it from a random function) with non-negligible probability.

The security property we guarantee is that the receiver does not accept as authentic any message $M$_i unless $M$_i was actually sent by the sender. A scheme that provides this guarantee is called a secure stream authentication scheme.

Note that the above security requirements do not include protection against message duplication. Such protection can (and should) be added separately by standard mechanisms, such as nonces or serial numbers. Schemes I-III below do have protection against message duplication. Note also that we do not address denial-of-service attacks.