# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Two Malicious Receiver Nodes
Theorem 1: _For \(r\leq 9\), every 2-separating family consists of at least \(r\) sets._  
Although one may be tempted to prove the result from Theorem 1 by a kind of exhaustive search for small values of \(r\), it is not directly possible. The number of non-empty families of subsets of \(\{1,\ldots,9\}\) consisting of 8 sets is \({2^{9}-1\choose 8}\approx 2^{56}\). Proof: Assume that there is a 2-separating family with less than \(r\) sets and that \(r\) is minimal with this property. Let \(\mathcal{SF}\) be the corresponding 2-separating family for \(r\) elements with less than \(r\) sets, and additionally assume that the number of elements in \(\mathcal{SF}\) is minimal for all families with the above property. Claim 2: \(\mathcal{SF}\) _does not contain singleton sets._  
Proof: Indeed, if \(\{i\}\in\mathcal{SF}\), then we can remove \(i\) from the set considered and \(\{i\}\) from \(\mathcal{SF}\). The resulting family is a 2-separating family for the elements that are left. Note that the number of elements and the number of sets in \(\mathcal{SF}\) have been reduced by one. Consequently, the obtained 2-separating family contains at most \((r-1)-1=r-2\) sets for \(r-1\) elements. Contradiction to the assumption that \(r\) is minimal! Thus, we can conclude that each element of \(\mathcal{SF}\) contains at least two elements. Claim 3: \(\mathcal{SF}\) _contains \(r-1\) sets._  
Proof: Let us remove an arbitrary element (also from the sets of \(\mathcal{SF}\)). The resulting family is a 2-separating family for the remaining elements. Per Claim 2, the number of the sets in the family is the same as before, but the number of the elements is \(r-1\). As \(r\) is minimal, \(\mathcal{SF}\) must contain \(r-1\) sets to avoid a contradiction. Claim 4: _Each element \(i\) must belong to at least three sets from \(\mathcal{SF}\). If there are exactly three sets, then their intersection is \(\{i\}\). If there are four sets and two intersect not only on \(i\), then the two remaining ones intersect on \(i\) only._  
Proof: Assume that \(U_{1},U_{2}\) are the only sets from \(\mathcal{SF}\) such that \(i\in U_{1},U_{2}\). Because \(|U_{1}|,|U_{2}|\geq 2\), there are elements \(j_{1}\in U_{1},j_{2}\in U_{2},j_{1},j_{2}\
eq i\). However, in this case \(i\) cannot be separated from \(j_{1}\) and \(j_{2}\). For the second case, we assume that \(U_{1},U_{2},U_{3}\) are the only sets from \(\mathcal{SF}\) such that \(i\in U_{1},U_{2},U_{3}\). Assuming that \(j\in U_{1}\cap U_{2},j\
eq i\), we can take arbitrary \(j^{\prime}\in U_{3},j^{\prime}\
eq i\) (this is possible because \(|U_{3}|\geq 2\)). Then, \(i\) cannot be separated from \(j\) and \(j^{\prime}\). Assume that \(U_{1},U_{2},U_{3},U_{4}\) are the only sets from \(\mathcal{SF}\) such that \(i\in U_{1},U_{2},U_{3},U_{4}\). Let \(j\in U_{1}\cap U_{2}\) and \(j^{\prime}\in U_{3}\cap U_{4}\). Then, \(i\) cannot be separated from \(j,j^{\prime}\). Claim 5: _Without loss of generality, we may assume that there are no \(U,U^{\prime}\in\mathcal{SF}\) such that \(U\subset U^{\prime}\)._  
Proof: If \(U\subset U^{\prime}\), then we may replace \(U^{\prime}\) by \(U^{\prime}\setminus U\). After the change, \(\mathcal{SF}\) will still be a 2-separating family. In this way, we can remove all cases where one set from family \(\mathcal{SF}\) is contained in another set. Let us count with repetitions the number of elements in the sets of \(\mathcal{SF}\). As each element appears at least three times, the total count is at least \(3r\). On the other hand, \(\mathcal{SF}\) is a family of at most \(r-1\) sets, meaning that there must be a set in \(V\in\mathcal{SF}\) with at least four elements. Let \(V^{\prime}\) be this set. The plan for the next steps is as follows:  
1. \(V^{\prime}\) may contain more than four elements; let \(V\) be its four-element subset. Without loss of generality, we assume that \(V=\{1,2,3,4\}\). 2. We consider \(\mathcal{SF}\) on \(V\) and show how many different sets from \(\mathcal{SF}\) are needed to guarantee the 2-separation property for the elements of \(V\).