Security Considerations

 

Given a number of disclosed SEALs, we can derive the probability that an adversary can find a valid BiBa signature using standard combinatorial techniques. In Appendix A we derive that a tight upper bound of the probability $P$_f of the adversary to forge a signature after a single trial is

$P$_f = {rk(n-1)^r-kn^r-1}

where $r$ is the number of SEALs that the adversary knows.

Clearly the more SEALs the adversary has, the higher the probability that it can forge a BiBa signature. The security of the BiBa signature scheme relies on the fact that the signer knows many more SEALs than an adversary. We leverage the birthday paradox threshold, also known as the birthday bound. Intuitively, when we throw $t$ balls uniformly randomly into $n$ bins, when the number $t$ is below the birthday bound (approximately $2n$), two-way collisions are rare. But as $t$ grows larger than the birthday bound, the number of collisions increases rapidly.

 

$k$ $n$ $P$_f $k$ $n$ $P$_f

$2$ $762460$ $2-19.5403$ $13$ $192$ $2-91.0196$

$3$ $15616$ $2-27.8615$ $14$ $168$ $2-96.1001$

$4$ $3742$ $2-35.6088$ $15$ $151$ $2-101.3377$

$5$ $1690$ $2-42.8912$ $16$ $136$ $2-106.3119$

$6$ $994$ $2-49.7855$ $17$ $123$ $2-111.0802$

$7$ $672$ $2-56.3539$ $18$ $112$ $2-115.7250$

$8$ $494$ $2-62.6386$ $19$ $104$ $2-120.6079$

$9$ $384$ $2-68.6797$ $20$ $96$ $2-125.1143$

$10$ $310$ $2-74.4851$ $21$ $89$ $2-129.5147$

$11$ $260$ $2-80.2237$ $22$ $83$ $2-133.8758$

$12$ $222$ $2-85.7386$ $23$ $78$ $2-138.2788$

 

We assume the signer has $t=1024$ SEALs, and the attacker has $r\; =\; k$ SEALs which is the number of SEALs disclosed after the signer signs one message. Let $P$_S denote the probability that the signer can find a signature after one trial with $t$ SEALs, and $P$_f denotes the probability that an adversary can forge a signature after one trial knowing $r$ SEALs. A high value for $P$_S means the signer is likely to produce a signature on the message and hence signing is efficient. For the remainder of this paper we set $P$_S = 0.5, such that the signer can find a signature after $2$ tries on average. A low value for $P$_f means that it is unlikely for an attacker to produce a valid signature, and indicates the security of the scheme. Table 1 shows the $P$_f value for different instances with varying parameters $n$ and $k$. In Section 5 we discuss methods on how to choose the BiBa parameters, and we discuss the resulting communication and computation costs. We would like to point out the high level of security BiBa achieves with only a few collisions. Based on the requirements of the NESSIE project [15], a BiBa signature scheme that uses an $11$-way collision would provide sufficient security.

An adversary has two main ways to collect SEALs to forge signatures. First, the adversary simply collects SEALs disclosed in signatures generated by the signer. Second, the adversary tries to find SEALs by brute-force computation to invert the PRF $F$ used to authenticate the SEALs. In our analysis, however, we assume that the latter attack is impractical, such that the adversary only knows the SEALs that the signer discloses with a signature.