# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Two Malicious Receiver Nodes
It turns out that at least six or seven sets are needed, depending on the case. 3. We consider how the 2-separating property can be fulfilled when we add the remaining elements: * If seven subsets are already in \(\mathcal{SF}\) to separate on \(V\), there are eight sets with \(V^{\prime}\) altogether. Thus, the minimal \(r\) to consider is \(9\). Note that the elements \(5,6,\ldots,9\) must be added somehow to already identified elements of \(\mathcal{SF}\) in such a way that the 2-separation property is fulfilled. We aim to show that this is impossible. * If there are six elements in \(\mathcal{SF}\) to separate within \(V\), then the proof is similar, but we must take into account an additional element of \(\mathcal{SF}\) not identified so far if \(r=9\). For \(r=8\), all sets are already named. **Definition 7**. : _For \(F\in\mathcal{SF}\) let the trace of \(F\) on \(V\), or simply trace, be defined as \(\mathsf{Tr}(F)=F\cap V\)._  
**Claim 6**. : _If \(F\in\mathcal{SF}\) and \(|\mathsf{Tr}(F)|\geq 2\), then each \(i\in\mathsf{Tr}(F)\) belongs to at least four different sets from \(\mathcal{SF}\), that is, to at least two sets different from \(V\) and \(F\)._  
Proof. : Assume that there is at most one such set, which we call \(F^{\prime}\). Then, take \(i^{\prime}\
eq i\) such that \(i\in F^{\prime}\) and \(j\in\mathsf{Tr}(F)\), \(j\
eq i\). Then, \(i\) cannot be separated from \(i^{\prime},j\). We consider two cases depending on the number of elements in a maximal trace. **Case 1**. : _No trace contains more than two elements._  
Let \(m\) be the number of elements from \(V\) that are members of a trace with two elements:  
1. Each trace has cardinality \(1\); per Claim 6, there are eight traces (two per element), meaning that together with \(V\) there are at least nine sets in \(\mathcal{SF}\). Consequently, \(r>9\). 2. Two nodes belong to traces of cardinality \(1\), meaning that they correspond to four different sets. The remaining two nodes, say, \(1,2\), belong to one or more sets with trace \(\{1,2\}\). As in the proof of Claim 6, we can conclude that, apart from these sets, \(1\) belongs to at least two more sets from \(\mathcal{SF}\). Indeed, if there is only one such set \(F\), we take \(i\in F\), \(i\
eq 1\). Then, \(1\) cannot be separated from \(i\) and \(2\). If no such \(F\) exists, then the argument is even easier: we cannot separate \(1\) from \(2\). The same holds for \(2\). Thus, the number of sets with nonempty traces in \(V\) is at least \(4+1+4=9\). With \(V\), we have identified ten different sets in \(\mathcal{SF}\). Consequently, \(r>10\). 2. If, say, \(1,2,3\) belong to traces of cardinality \(2\) while \(4\) does not, then per Claim 6 there are two sets with the trace \(\{4\}\). Per Claim 6, each element \(1,2,3\) belongs to three different sets (apart from \(V\)). Thus, when counting with repetitions, there are nine sets. As traces are of cardinality at most \(2\), there are at most three two-element traces: \(\{1,2\}\), \(\{2,3\}\), \(\{1,3\}\). If they occur once, they cover six out of nine sets with repetitions counted above. Then, the number of sets in \(\mathcal{SF}\) is at least \(1+2+3+3=9\), and consequently \(r>9\). However, if a trace \(\{1,2\}\) appears twice, then we need an additional set at \(1\) (and at \(2\) as well). Thus far, there is no set in \(\mathcal{SF}\) that would separate \(1\) from \(2\) and \(3\). We are again left with three sets (with repetitions) and a newly identified set in \(\mathcal{SF}\). Continuing in this way, it can be seen that we shall always conclude that \(r>9\). 3. For each \(i\), there are at least three different sets in \(\mathcal{SF}\setminus\{V\}\). Counting with repetitions, there are in total \(4\cdot 3=12\) sets. Each set with a two-element trace is counted twice, and there are no traces with more than two elements that would be counted more than twice. Thus, there are at least six sets in \(\mathcal{SF}\setminus\{V\}\).