The SEALs

The signer precomputes values that it subsequently uses to generate BiBa signatures. These values are random numbers generated in a way that the receivers can instantly authenticate them with the public key (which is sometimes referred to as public validation information in this context). We call these precomputed values SEALs, short for SElf-Authenticating vaLues. The property that we need for SEALs is that the verifier can efficiently authenticate the SEAL based on the public key, and that it is computationally infeasible for an adversary to find a valid SEAL given a public key. The simplest approach is to use the PRF $F$ as a commitment scheme. Given a SEAL $s$, the public key is $f$_s = F_s(0). If the verifier learns $f$_s in an authentic fashion, it can easily authenticate $s$ by verifying $F$_s(0) = f_s. In BiBa the signer needs multiple SEALs, so a public key could consist of multiple commitments.

Another alternative for SEAL authentication is a Merkle hash tree (so the SEALs would be the leaf nodes of the tree and the public key is the root node of the tree) [12]. We discuss this approach in Appendix B.

In the case of broadcast authentication, we describe efficient methods to generate and authenticate SEALs in Section 3. For now we simply assume that the signer has $t$ precomputed SEALs $s$₁, s₂, &ldots;, s_t, and receivers know the authentic commitment $F$s_i(0) of each SEAL so they can efficiently authenticate each SEAL they receive.