Extension A provides low receiver computation overhead and low communication overhead, but it does not tolerate packet loss. The basic BiBa broadcast authentication protocol has a high receiver computation overhead because the majority of the SEALs are never used in a signature, so to authenticate a SEAL the receiver needs to recompute many SEALs in a one-way SEAL chain until it reaches a previously stored SEAL. We solve this problem in extensions A and B by using every SEAL of each one-way SEAL chain in a BiBa signature.
In this scheme we use the concept of SEAL boundary, which Figure 4 depicts. The SEALs above the boundary are disclosed, and they serve as commitment to the SEALs on the other side of the boundary. The sender and receiver always know the current SEAL boundary. The sender only uses SEALs that are directly adjacent to (below) the boundary. After each BiBa signature the sender and receiver extend the SEAL boundary past the newly disclosed SEALs.
Figure: Using one-way chains to construct SEAL
This scheme would not be secure if an adversary could slow down the data traffic to the receiver, and collect enough packets such that it knows a large number of SEALs on the lower side of the perceived SEAL boundary of the receiver. This large number of SEALs would enable the adversary to spoof subsequent data traffic, because the adversary continuously receives fresh SEALs that the sender discloses. This illustrates that the sender and receiver need to be time synchronized, such that the receiver knows the sending schedule of the packets.
As an additional security measure, the sender can also sign all the SEALs directly above the current SEAL boundary with the message signature. This mechanism would ensure the receiver that it knows the correct SEAL boundary.