# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Two Malicious Receiver Nodes
Note that there are \(\frac{4.3}{2}=6\) different pairs of elements in \(V\); hence, the number of two-element traces is at most 6. We may conclude that for \(r\leq 9\) (up to a permutation of nodes) there are the following traces:  
1. \(\{1,2\}\), \(\{2,3\}\), \(\{3,4\}\), \(\{1,3\}\), \(\{2,4\}\), \(\{1,4\}\) (see Figure 10);
2. \(\{1\}\), \(\{1,2\}\), \(\{2,3\}\), \(\{3,4\}\), \(\{1,3\}\), \(\{2,4\}\), \(\{4\}\) (see Figure 11). Let the corresponding sets of \(\mathcal{SF}\) be called \(F_{1},\ldots,F_{6}\) in case (A) and \(W_{1},\ldots,W_{7}\) in case (B). As we also have the set \(V\), we find that \(r\geq 8\) in case (A) and \(r\geq 9\) in case (B). To show that \(r\) is higher, we can consider the elements 5, 6, 7, 8 (and 9). For each of them, there are at least three sets from \(\mathcal{SF}\) to which it belongs. Except for Case A and \(r=9\), these must be the already identified sets from \(\mathcal{SF}\). **Case 1A. **_The traces are as described by Case A (Figure 10)._  
Note that there might be an additional set \(U\in\mathcal{SF}\) if \(r=9\). **Claim 7**. : \(5,6,7,8,9\in U\)_._  
**Proof. ** Assume that 5 does not belong to \(U\). Then, there are at least three sets from the list \(V\), \(F_{1}\),..., \(F_{6}\) to which it belongs. We claim that in any case we can find two elements \(i,j\) that cannot be separated from 5. If 5 belongs only to \(V\), \(F_{a},F_{b}\), then we take \(i\in F_{a}\cap V\), \(j\in F_{b}\cap V\); \(V\) cannot be used to separate 5 from \(i,j\), as \(i,j\in V\), \(F_{a}\) cannot be used as \(i\in F_{a}\) and \(F_{b}\) cannot be used as \(j\in F_{b}\). This is a contradiction. Next, we assume that 5 belongs to three sets \(F_{a},F_{b},F_{c}\) (and possibly to \(V\)). However, if we take any three sets from \(F_{1},\ldots,F_{6}\), then they cannot be disjoint, as their traces are three two-element subsets of a four-element set \(\{1,2,3,4\}\). For, say, \(i\in F_{a}\cap F_{b}\cap V\) for some  
Figure 11: Traces in case B: Each trace is represented by an arch where the endpoints are the elements of a trace; \(W_{1},\ldots W_{7}\) are labels of the corresponding sets in \(\mathcal{SF}\). Figure 10: Traces in case A: Each trace is represented by an arch where the endpoints are the elements of a trace; \(F_{1},\ldots F_{6}\) are labels of the corresponding sets in \(\mathcal{SF}\). \(i\leq 4\), we can take any \(j\in F_{e}\), \(j\
eq 5\); obviously, \(5\) cannot be separated from \(i,j\), which is a contradiction. If \(5\) belongs to \(F_{a},F_{b},F_{c},F_{d}\), then we can use the fact that for any four two-element subsets of \(\{1,2,3,4\}\) there are \(i,j\leq 4\) such that each of these subsets contains either \(i\) or \(j\). Let \(i,j\) be such elements for the traces of \(F_{a},F_{b},F_{c},F_{d}\). Thus, \(5\) cannot be separated from \(i,j\), which is a contradiction. If \(5\) belongs to all sets \(F_{m}\) except for \(F_{a}\), then we take \(\{i,j\}=\{1,2,3,4\}\setminus F_{a}\). Again, \(5\) cannot be separated from \(i,j\), which is a contradiction. If \(5\) belongs to all sets \(F_{1},\ldots,F_{6}\), then no \(i\leq 4\) can be separated from \(5\), which is a contradiction. In every case, the assumption \(5\
ot\in U\) leads to a contradiction. Thus, we can conclude that \(5\in U\). By symmetry, the same argument applies to \(6,7,8,9\). Let \(i\geq 5\) and \(j\leq 4\). Then, there is at most one set \(F_{a}\) such that \(i,j\in F_{a}\). Proof. : To focus our attention, consider \(j=1\). There are three sets \(F_{a}\) containing \(1\): \(F_{1}\), \(F_{4}\), \(F_{6}\). Assume that \(i\in F_{1}\), \(F_{4}\). Then, consider separating \(1\) from \(4\) and \(i\); \(V\) and \(F_{6}\) cannot be used for separation, as they contain \(4\), while \(F_{1},F_{4}\) cannot be used because of \(i\). Due to symmetry, each case can be handled in a similar way. Per Claim 8, if \(j\geq 5\) and \(j\in F_{a}\), then \(j\
ot\in F_{b}\) for any \(b\) such that \(\mathsf{Tr}(F_{a})\cap\mathsf{Tr}(F_{b})\
eq\emptyset\).