For graph-based authentication, the main challenge is how to design a Directed Acyclic Graph (DAG)
with lowest overhead, highest verification probability and lowest sender and receiver delay.
However, there are tradeoffs between these performance criteria, which are summarized below.
- Computation complexity: The number of hash operations and signature operations required at the
sender and receiver. Note that computing a signature is much more complex than computing a hash.
- Overhead size: The extra bytes introduced by stream authentication, including the hashes and
signatures appended to the packets. The overhead size is determined by the number of edges in
the authentication graph. Note that a signature is much bigger in size than a hash.
- Verification percentage (or verification probability): the percentage of verifiable packets
among all the received packets. Intuitively, the more redundant paths a packet has to the
signature packet, the higher the probability of being verified.
- Sender delay: The delay at the sender (in number of packets) from the time when the packet
is produced by the encoder to the time that all authentication data appended to this packet
is ready. Real-time communication scenario requires low sender delay. For non-real-time
scenario, e.g., pre-encoded content for VOD applications, it is not important because the
sender has priori knowledge of all packets.
- Receiver delay: The delay at the receiver (in number of packets) from the time a packet is
received to the time that it can be verified. For authenticated video, each packet must be
received and pass the verification before its playout deadline.