Selection of BiBa Parameters

We assume that the sender has $t=1024$ SEALs. Let $P$_f denote the probability that an attacker can find a signature with one trial of one message knowing at most $r$ SEALs. The security parameter is generally expressed as the expected number of hash function operations that an adversary has to perform to forge a signature [15]. For BiBa, the minimum number of hash function operations to forge a signature is $2/P$_f, for simplicity we use $1/P$_f.

Let $P$_S denote the probability that the sender can find a signature in one trial. The expected number of tries that the sender performs to find a signature is $1/P$_S. Without loss of generality we set $P$_S = 0.5.

To achieve good security, the sender can disclose approximately up to $\gamma =10\%$ of the SEALs. Each signature reveals $k$ SEALs. The sender knows $t$ SEALs, so it can produce $\nu =\; \gamma t/k$ signatures in a time period. As we discuss in Section 3, the sender needs to wait for time $\delta$ until it can disclose the SEALs of the next time period. Hence it needs multiple BiBa instances, if it wants to send more than $\nu$ messages per time period $\delta$. Given the packet sending rate $\beta$, the number of BiBa instances needed is $\delta \beta /\nu$.

We now discuss how we choose $n$ and $k$. The choice of $k$ directly determines the signature size. We can derive the number of bins $n$ from $k$ and the probability $P$_S that the sender finds a signature after one trial. Figure 5 shows how $P$_S decreases as we increase $n$.

  
Figure 5: Probability of finding a twelve-way collision when throwing $1024$ balls into $x$ bins.

Once we fix $n$ and $k$ we can derive the number of SEALs that the sender can disclose such that the adversary has at most a probability of $P$_f to forge a signature. Figure 6 depicts the probability distribution to find a signature given a certain number of SEALs. As we can see in Figure 6(a), $P$_f quickly decreases as the sender decreases the number of SEALs it discloses. If $P$_f is too high (insufficient security) for a $k$-way collision, we need to increase $k$.

 
   

Figure 6: Probability of finding a signature given $x$ SEALs. These probabilities are for the scheme $k=12,\; n=222$.