Streams and Broadcasts
Suppose we wish to broadcast a stream to a set of users securely. How can we achieve integrity? We cannot use MAC’s, otherwise the users could forge packets to each other. We cannot sign the entire stream: this solution is vulnerable to packet loss, and also the whole stream would have to be buffered for verification. We cannot sign each packet individually, as this is too inefficient.
Method 1 (Combinatorial)
We describe a simple scheme based on families of coverfree subsets. It is a too inefficient for practical purposes.
There are \(n\) users and a single source. The source has several MAC keys \(K_1, ..., K_m\), where \(m\) will be determined later.
The \(i\)th receiver has a set of keys \(S_i \subseteq \{K_1,...,K_m\}\).
To send a message \(M\), the source transmits \(M, MAC_{K_1}(M) ,..., MAC_{K_m}(M)\).
Recipient \(i\) accepts a packet \(P\) if all the MAC’s corresponding to their set \(S_i\) verify.
At the bare minimum, we want 1security, that is, any user \(j\) should not be able to forge a packet for any other user \(i\), so we must have \(S_i \nsubseteq S_j\). The best way to do this is to use all subsets of size \(m/2\) from the set of keys, so we need \(n = \left( \array { m \\ m/2 } \right) \), so \(m = O(\log n)\).
More generally, for \(t\)security (i.e. so that no group of \(t\) users can forge a packet), we require a family of \(t\)coverfree subsets, which can be done with \(m = O(t^2 \log n)\). Thus the packet size is quadratic in \(t\). It can be shown that a smaller packet size implies nonrepudiation, that is, a MAC that short would in fact be a signature.
Method 2 (TESLA)
This solution uses time for security. Assume the total clock skew is \(\Delta\), and that the total routing time is less than or equal to some time \(T\).
We use hash chains, i.e:
For setup, give \(K_m\) to all recipients, for some sufficiently large \(m\). The source has \(K_0\). Then:
Time \(1\): send \(M_1, MAC_{K_{m1}}(M_1)\)
Time \(2\): send \(M_2, MAC_{K_{m2}}(M_2)\)
…
Time \(T\): send \(M_T, MAC_{K_{mT}}(M_T)\). By this stage, all users should have received \(M_1, MAC(M_1)\).
…
Time \(T + \Delta\): send \(M_{T+\Delta}, MAC_{K_{mT\Delta}}(M_{T+\Delta})\), and also send \(K_{m1}\)
…
Time \(2T + \Delta\): all users can validate \(M_1\)
To validate the first packet:

Check that \(K_m\) is in the hash chain

Verify \(MAC_{K_{m1}}(M_1)\)

Reject \(M_1\) if received after time \(T+\Delta = T_{local}\)
Note that this scheme requires the users to buffer packets for \(T\) time steps.
It has been shown [JacobsonCoppersmith] that one can construct a hash chain where computing any element of it takes time \(O(\log n)\) in \(O(\log n)\) space.
Method 3 (Signing) [Wong and Lam]
Signing every packet is too expensive, but signing many packets is vulnerable to packet loss. The solution is to sign many packets at once but verify them individually.
For example, suppose we have four packets \(p_1,...,p_4\). We construct a hash tree (diagram will be here when Mozilla supports SVG :) (e.g. if we label the tree nodes \(n_1,...,n_7\), we have
and transmit the packet plus enough nodes of the tree to derive the root node:

send \(p_1, n_2, n_6, sign(n_7)\)

send \(p_2, n_1, n_6, sign(n_7)\)

send \(p_3, n_4, n_5, sign(n_7)\)

send \(p_4, n_3, n_5, sign(n_7)\)
The overhead is \(O(\log n)\) hashes plus a signature per packet.
However, this method requires buffering at the source. We can use onetime signatures to alleviate this.
OneTime Signatures are signatures that can be constructed and verified very quickly, but can only be used once (or a few times).
For example [Lamport], consider the following scheme:

Private key: \(x_1^0,...,x_{160}^0, x_1^1,...,x_{160}^1\).

Public key: \(H(x_1^0),...,H(x_{160}^0), H(x_1^1),...,H(x_{160})^1)\)

Sign(\(M\)): compute \(SHA1(M) = h \in \{0,1\}^{160}\). The signature is \(x_1^{h_1} ,..., x_{160}^{h_{160}}\) where \(h_i\) is the \(i\) bit of \(h\).
Another example. BiBa OTS (Bins and balls):

Let \(n\) be the security parameter. Let \(H\) be a hash function \(H:\{0,1\}^* \rightarrow \{0,1\}^m\) where \(m \ll n\).

Private key: \(x_1,...,x_n \in \{0,1\}^k\)

Public key: \(SHA1(x_1),...,SHA1(x_n)\)

Sign(\(M\)): find \(1 \le i\lt j\le n\) such that \(H(Mx_i) = H(Mx_j)\). The signature is \((x_i, x_j)\) ("Find two balls that hit the same bin.")
We can now remove the buffering problem as follows. Build a hash tree from the public keys \(PK_1,...,PK_n\) of some onetime signature scheme. Sign the tree and transmit the public keys with signatures (so we commit to public keys instead of packets), and simply sign each packet.
Method 4: Expanders
Build a directed acyclic graph (DAG) using the packets as nodes. Then proceed as in the previous scheme, except this time we use a hash DAG, instead of a hash tree.
To resist up to \(t\) packets being lost, we need a graph that remains connected even if \(t\) nodes are removed.
An \(\epsilon\)expander graph \((V,E)\) is a graph such that for all \(S \subseteq V\), we have \(neighbour(S) \ge (1+\epsilon) S\) if (?) \(S \le V / (1+\epsilon)\).
There exist methods of constructing constant degree \(d\) expanders on \(n\) nodes such that removing \(n^\epsilon\) nodes for some constant \(\epsilon\) does not disconnect the graph.