# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Optimal Values for Small Number of Nodes
#### 4.5.2 Exact Values of \(\Psi(r)\) for Small \(r\)
It can be matched with any of the remaining \(F_{i}\cap F\) intersections, namely, \(\{1,4,5\}\), \(\{2,4\}\), or \(\{3,5\}\). Unfortunately, none of these works:  
* If \(\{6,9,10\}\cup\{1,4,5\}\in SF\), then \(6\) cannot be separated from \(1\);
* If \(\{6,9,10\}\cup\{2,4\}\in SF\), then \(6\) cannot be separated from \(2\);
* If \(\{6,9,10\}\cup\{3,5\}\in SF\), then \(6\) cannot be separated from \(3\);  
which results in a contradiction. Now, let us assume that \(F\) contains six elements, say, \(6\), \(7\), \(8\), \(9\), \(10\), and \(11\), and let \(U\) be the complement of \(F\), namely, \(U=\{1,2,3,4,5\}\). Let \(F_{1}\), \(F_{2}\), \(F_{3}\), and \(F_{4}\) be the remaining sets of \(\mathcal{SF}\). As before, without loss of generality, we may assume that \(F_{1}\cap F=\{6,7,8\}\), \(F_{2}\cap F=\{6,9,10\}\), \(F_{3}\cap F=\{7,9,11\}\), and \(F_{4}\cap F=\{8,10,11\}\). Intersecting the \(F_{i}\)s with \(U\) results in \(\{1,2,3\}\), \(\{1,4,5\}\), \(\{2,4\}\), \(\{3,5\}\) (not necessarily in this order, and up to a permutation of \(1,2,3,4,5\)). Again, the question is whether the elements of \(U\) can be separated from the elements of \(F\). As the elements of \(U\) have changed, this is a different question than before. Again, without loss of generality, we may assume that \(F_{1}=\{1,2,3\}\cup\{6,7,8\}\in\mathcal{SF}\). Then, \(F_{1}\) cannot be used to separate \(1\) from \(6\), \(7\), or \(8\). The only other set that contains \(1\) and can be used to separate it from \(6\), \(7\), and \(8\) is \(\{1,4,5\}\). One \(F_{i}\in\mathcal{SF}\) is a sum of \(\{1,4,5\}\) with one of the sets \(\{6,9,10\}\), \(\{7,9,11\}\), or \(\{8,10,11\}\). Again, no matter what we choose, the resulting set will contain some \(j\in\{6,7,8\}\) and \(1\) will not be separated from \(j\). \(\Psi(15)=6\): Let us take the separating family \(\mathcal{SF}\) for \(r=10\) presented above, which consists of the sets \(F_{1}=\{1,3,6,7\}\), \(F_{2}=\{2,4,6,8\}\), \(F_{3}=\{1,2,5,9\}\), \(F_{4}=\{3,4,5,10\}\)  
\[\{1,2,3\},\{1,4,\ldots\},\{2,4,\ldots\},\{3,\ldots\}\,.\]1 An optimal separating family for ten nodes consisting of five sets \(F_{1},\ldots,F_{5}\). \(F_{5}=\{7,8,9,10\}\). We can create a family \(\mathcal{SF}^{\prime}\) for \(\{1,\ldots,15\}\) that consists of the following sets:  
\(F^{\prime}_{1}=F_{1}\cup\{11\}\), \(F^{\prime}_{2}=F_{2}\cup\{12\}\), \(F^{\prime}_{3}=F_{3}\cup\{13\}\), \(F^{\prime}_{4}=F_{4}\cup\{14\}\), \(F^{\prime}_{5}=F_{5}\cup\{15\}\), and \(F^{\prime}_{6}=\{11,12,13,14,15\}\). Let us first check whether \(\mathcal{SF}^{\prime}\) is a separating family. If \(i,j\leq 10\), then the separation property follows from the properties of \(\mathcal{SF}\). For \(i,j\geq 11\), it follows from the fact that each \(i\geq 11\) appears in a separate set in the list \(F^{\prime}_{1},\ldots,F^{\prime}_{5}\). If \(i\geq 11\) and \(j\leq 10\), then \(i\) is separated from \(j\) by \(F^{\prime}_{6}\). The only unclear case is that of \(i\leq 10\) and \(j\geq 11\). However, each \(j\geq 11\) appears in one of the sets \(F^{\prime}_{1},\ldots,F^{\prime}_{5}\), while \(i\) occurs in two such sets; thus, there is always a set \(F^{\prime}_{u}\) such that \(i\in F^{\prime}_{u}\) and \(j\
otin F^{\prime}_{u}\). \(\Psi(20)=7\)**:**: First, recall from Definition 5 that \(\Psi(20)\leq 7\). Thus, it suffices to show that \(\Psi(20)>6\). Conversely, we can assume that \(U_{1},\ldots,U_{6}\) is a separating family for \(\{1,\ldots,20\}\). First, we assume that some set, say, \(U_{6}\) contains at least eleven elements. Then, \(U^{\prime}_{i}=U_{i}\cap U_{6}\) for \(i\leq 5\) is a separating family for \(U\). This is impossible, as \(\Psi(11)=6\). If \(U_{6}\) contains at most nine elements, then \(V^{\prime}_{i}=U_{i}\setminus U_{6}\) for \(i\leq 5\) is a separating family for \(\{1,\ldots,20\}\setminus U_{6}\). This is a contradiction, as this set contains at least eleven elements. Thus, we conclude that each \(U_{i}\) is a ten-element set. Without loss of generality, we assume that \(U_{6}=\{1,\ldots,10\}\).