Efficient Public-Key Distribution

Sending the public key to all receivers is a potential bottleneck. In the schemes we discuss in this paper, the public key size is on the order of $10$ Kbyte for each BiBa instance. We now present a trick that makes public key distribution efficient for the sender, but requires a longer time to bootstrap receivers. The intuition is that receivers can collect SEALs while they receive signed messages, and reconstruct the one-way SEAL chains and the one-way salt chain. Periodically, the sender broadcasts a message containing the hash of all SEALs and the salt of one time period, signed with a traditional digital signature scheme, for example RSA [22]. Once the receiver collects all SEAL chains, it can authenticate them with the digital signature and authenticate subsequent traffic. This assumes that the receiver is already time synchronized with a maximum time synchronization error $\delta$. The well-known coupon collector problem predicts how long the receiver needs to wait: After collecting $tlog(t)$ random SEALs, it has one SEAL of each one-way chain with high probability, where $t$ is the number of SEAL chains. In the schemes we consider in this paper $t=1024$, hence the receiver needs to collect about $7098$ SEALs. In our first example, the sender discloses $64$ SEALs in each time period, so the receiver needs to collect SEALs during $110$ time periods.