# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Two Malicious Receiver Nodes
It can be seen from Figure 12 that there are exactly three pairs of sets \(F_{a}\), \(F_{b}\) with disjoint traces: \((F_{1},F_{3})\), \((F_{4},F_{5})\), \((F_{2},F_{6})\). Let \(i\geq 5\); then, \(i\) belongs to either a single \(F_{a}\), to (\(F_{1}\) and \(F_{3}\)), to (\(F_{4}\) and \(F_{5}\)), or to (\(F_{2}\) and \(F_{6}\)). Now, we can exclude the case with \(r\leq 8\), as an element \(i\geq 5\) may belong to at most two sets \(F_{a}\) for \(a\leq 5\). Per Claim 4, \(i\) belongs to at least three different sets from \(\mathcal{SF}\), and must belong to \(V^{\prime}\). We can conclude that \(V^{\prime}\) contains all elements \(1,\ldots,8\); then, we can eliminate \(V^{\prime}\) from \(\mathcal{SF}\) without changing the two-separation property. This is a contradiction, as we have assumed that \(\mathcal{SF}\) is minimal. Now, we continue for \(r=9\). First, we exclude the first option from Corollary 4. For \(i=5,\ldots\), element \(i\) must belong to two different sets \(F_{j}\). Proof. : We assume that \(i\in F_{a}\) and \(i\
ot\in F_{b}\) for \(b\
eq a\). First, we consider the case with \(i\in V^{\prime}\). If \(r=9\), then additionally \(i\in U\). Now, we take \(j_{1}\in F_{a}\cap V\) and an arbitrary \(j_{2}\geq 5\), \(j_{2}\
eq i\). Then, \(i\) cannot be separated from \(j_{1},j_{2}\). Indeed, \(V^{\prime}\) and \(F_{a}\) cannot be used for separation, as \(j_{1}\in V,F_{a}\), while \(U\) cannot be used for separation either, as \(j_{2}\in U\). Now, assume that \(i\
ot\in V\). Then, \(i\) belongs to at most two sets from \(\mathcal{SF}\) (namely, \(U\) and \(F_{a}\)), which per Claim 4 is impossible. Figure 12: Three possible pairs of sets \(F_{a}\) with disjoint traces; each pair is shown in a different color. The elements \(5,6,7,8,9\) fall into categories depending on which sets \(F_{a}\) they belong to. By Corollary 4 and Claim 9, there are only three options. Thus, there are \(i,j\geq 5\) belonging to the same sets \(F_{a},F_{b}\). As they both belong to \(U\), the only difference may be \(V\) (say, \(i\in V\) and \(j\
otin V\)); then, \(j\) cannot be separated from \(i\), which is a contradiction. This concludes the proof in Case 1A. **Case 1B. **_The traces are as described by Case B (Figure 11)._  
Now, we consider only the case \(r=9\), as eight sets have already been identified in \(\mathcal{SF}\): \(V^{\prime}\), \(W_{1}\),..., \(W_{7}\). Each element \(5,\ldots,9\) must be included in some of them. The following claim can be shown in the same way as Claim 8:  
**Claim 10**. : _For every \(i\leq 4\) and \(j=5,\ldots,9\), there is at most one a such that \(i,j\in W_{a}\)._  
Because in Case 1B there is no additional set \(U\), we may proceed as follows:  
**Claim 11**. : _Let \(j\geq 5\); then, there are at least three sets \(W_{i}\) such that \(j\in W_{i}\)._  
**Proof. ** Conversely, we can assume that \(j\) belongs to \(W_{i_{1}}\) and \(W_{i_{2}}\) only (or even only to \(W_{i_{1}}\)). Let us take arbitrary \(a,b\leq 4\) such that \(a\in W_{i_{1}}\) and \(b\in W_{i_{2}}\). Then, \(j\) cannot be separated from \(a,b\). Indeed, \(W_{i_{1}}\) cannot be used, as \(a\in W_{i_{1}}\), \(W_{i_{2}}\) cannot be used because \(b\in W_{i_{2}}\). Potentially, \(j\) may belong to \(V^{\prime}\); however, it cannot be used for separation, as \(a,b\in V\subseteq V^{\prime}\). Let \(\mathcal{F}_{j}\) be the collection of sets \(W_{i}\) such that \(j\in\mathcal{F}\). We can observe the following:  
* \(W_{1}\
ot\in\mathcal{F}_{j}\); indeed, \(W_{1}\) is incident \(W_{6},W_{4},W_{2},W_{5}\), meaning that they would not belong to \(\mathcal{F}_{j}\). Only \(W_{3}\) and \(W_{7}\) are left, but they are incident, and only one of them can belong to \(\mathcal{F}_{j}\). Thus, we would end up with two sets in \(\mathcal{F}_{j}\), which is contrary to Claim 11. * In the same way, we argue that \(W_{3}\
ot\in\mathcal{F}\). * \(W_{4}\
ot\in\mathcal{F}_{j}\); indeed, if \(W_{4}\in\mathcal{F}_{j}\), then \(W_{1},W_{6},W_{2},W_{3}\
ot\in\mathcal{F}_{j}\), as they are incident to \(W_{4}\).