Assume we want to broadcast signed video on the Internet. The system requirements are as follows:
The high packet drop rate makes it difficult for signature packets to reach the receiver. To increase the likelihood of signature packets to arrive, we send them twice -- but within a delay, since packet loss is correlated. If we approximate the loss probability by assuming the signature packet losses are uncorrelated if they are sent within a delay, the probability that one of them arrives is approximately . Since the packet loss is so high and verification delay relatively short, we send a a signature packet every packets. This translates to about signatures per second, which we consider as a low computational overhead. We assume that the signature packets have about the same size as the data packets, so in bytes we can fit one -bit RSA signature and the bit hash of previous packets.
We chose these parameters based on good engineering practice. To find better parameters for the number of chunks that the hash is split into and the number of chunks required to verify the packet, we used a simulation. The simulation shows that the best combination for this case uses bytes per packet to insert chunks of two bytes of the hash of previous packets. Including the signature packets, the average communication overhead is about bytes per packet. The simulation predicts the average verification probability over the final packets of , with the minimum verification probability .