# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication  
For the purposes of this section, we assume that we have a multicast group with a sender \(S\) and a set \(\mathcal{R}\subseteq\mathcal{N}\) of \(r\) receivers. We study the problem of authenticating the origin of multicast messages; each member of \(\mathcal{R}\) must be able to filter out the messages that do not originate from \(S\).  
We differentiate between \(\mathcal{R}\) and \(\mathcal{N}\) in order to take the following into account. Note that a ciphertext can be authenticated in front of a broader set than just the set of nodes that are able to decrypt it, that is, confidentiality of the message can be protected independently from its integrity; one of the methods described in Section 3 can be utilized for this purpose. This allows us to study sender authentication on its own as an orthogonal problem. Initially, for authentication purposes, the nodes can be preloaded with the keys corresponding to a few sets \(\mathcal{R}\) determined by the deployment of the nodes.  
For flexibility reasons, it is advantageous to include all of \(\mathcal{N}\) as one of these sets; in case a new group with receiver set \(\mathcal{R}\) must be established, the freshly generated keys for \(\mathcal{R}\) can be broadcast by \(S\) using encryption, as in Section 3, except authenticated in front of everyone (all of \(\mathcal{N}\)), or some \(\mathcal{R}^{\prime}\supset\mathcal{R}\) if there are preloaded keys for \(\mathcal{R}^{\prime}\). After decrypting the messages, the nodes from \(\mathcal{R}\) may switch to the new authentication keys. In Section 4.3, we shall see how much communication volume can be saved if the sender switches from authenticating in front of \(\mathcal{N}\) to authenticating in front of a subset \(\mathcal{R}\). Nevertheless, the smaller the set of nodes knowing the keys, the more limited the impact of node capture.  
We are concerned with the situation where digital signatures of \(S\) cannot be used to prove the message origin due to channel bandwidth constraints. Message authentication codes based on a symmetric key \(K\) shared by \(S\) and the nodes in \(\mathcal{R}\) can protect the integrity of the messages against external adversaries, but are unfortunately useless against an internal adversary, as a malicious node can create messages and their authentication codes in the same way as \(S\) and send them to selected nodes in \(\mathcal{R}\). This may create chaos in network operation.  
An additional difficulty is the admissible length of message authentication codes. We assume that there might be a strict upper bound on their length and that the bound might be (much) lower than the length of standard message authentication codes. Thus, we identify two high-level approaches to authenticating the origin of messages when restricted to symmetric cryptography. One is to amortize the cost of sender authentication by chaining messages together with cryptographic commitments. By subsequently opening these commitments, the sender proves that the entire chain of messages originated from the same source. If there is a strong proof of origin for the first message, then all the messages in the chain are authenticated robustly. This is the idea behind the TESLA protocol, explicated in Section 4.1. Another approach is to append authentication tags to each message. These tags rely on some secrets shared between the sender \(S\) and specific subsets of receivers \(\mathcal{R}\), ensuring that no node from \(\mathcal{R}\) could forge all tags. An efficient construction of this kind is proposed in Section 4.3.