# 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\)
However, the elements \(\{1,2\}\) must be separated, and none of the sets above separates them; thus, we need two additional sets and \(\mathcal{SF}\) must contain at least five sets altogether, which is a contradiction. Suppose now that there exists a set with three elements in \(\mathcal{SF}\). Without loss of generality, let these elements be \(\{1,2,3\}\) and consider the remaining elements 4, 5, 6, and 7. As \(\Psi(4)=4\), we need four sets to separate these remnants. As \(\{1,2,3\}\) does not separate any pair of elements from \(\{4,5,6,7\}\), \(\mathcal{SF}\) consists of at least \(1+4=5\) sets in total, which again is a contradiction. Finally, suppose there is a set \(F\in\mathcal{SF}\) consisting of at least four elements. To separate these elements, we need at least four additional sets. Again, \(\mathcal{SF}\) would have at least five elements, which is a contradiction. \(\Psi(i)=5\) **for \(i=8,9,10\):**: It suffices to present a separating family for \(r=10\); however, we will show slightly more. Specifically, we shall identify all separating families for \(r=10\) with five elements. Similar to the case with \(r=6\), we show that there is only one solution up to some trivial transformations. Let us start with a simple observation:  
**Lemma 4**. : _If \(V_{1},\ldots,V_{t}\) is a separating family for \(\mathcal{R}\), then \(\mathcal{R}\setminus V_{1},\ldots,\mathcal{R}\setminus V_{t}\) is also a separating family for \(\mathcal{R}\)._  
Figure 7: An optimal separating family for six nodes consisting of four sets \(F_{1},\ldots,F_{4}\). **Proof. ** For \(i,j\in\mathcal{R}\), we have to find \(u\) such that \(i\in\mathcal{R}\setminus V_{u}\) and \(j\
ot\in\mathcal{R}\setminus V_{u}\). As \(V_{1},\ldots,V_{t}\) is a separating family, there is \(u\) such that \(V_{u}\) separates \(j\) from \(i\), that is, \(j\in V_{u}\) and \(i\
ot\in V_{u}\). Then, \(j\
ot\in\mathcal{R}\setminus V_{u}\) and \(i\in\mathcal{R}\setminus V_{u}\), as required. Let \(U_{1},\ldots,U_{5}\) be a separating family for \(\{1,\ldots,10\}\). Observe that no \(U_{i}\) contains \(7\) or more elements. Indeed, suppose that \(|U_{5}|=\ell\), where \(\ell\geq 7\). Consider \(U^{\prime}_{1}=U_{1}\cap U_{5}\),..., \(U^{\prime}_{4}=U_{4}\cap U_{5}\). Then, \(U^{\prime}_{1},\ldots,U^{\prime}_{4}\) must separate every \(a,b\in U_{5}\). However, it is impossible to find a separating family with \(4\) sets for an \(\ell\)-element set (\(\ell\geq 7\)), as \(\Psi(7)=5\). Let us now assume that \(|U_{5}|=6\) and, without loss of generality, let \(U_{5}=\{1,2,3,4,5,6\}\). Consider \(U^{\prime}_{i}=U_{i}\cap U_{5}\) for \(i\leq 4\), as before. Clearly, \(\{U^{\prime}_{1},\ldots,U^{\prime}_{4}\}\) is a separating family for \(\{1,2,3,4,5,6\}\). Therefore, without loss of generality (see the case with \(r=6\) above), we may assume that \(U^{\prime}_{1}=\{1,2,3\}\), \(U^{\prime}_{2}=\{1,4,5\}\), \(U^{\prime}_{3}=\{2,4,6\}\), \(U^{\prime}_{4}=\{3,5,6\}\). The sets \(U_{1},\ldots,U_{4}\) can be obtained by adding some number of elements \(7\), \(8\), \(9\), \(10\) to \(U^{\prime}_{1},\ldots,U^{\prime}_{4}\). First, observe that no \(a\geq 7\) can belong to only one set \(U_{i}\); indeed, in this case \(a\) would not be separated from other elements of \(U_{i}\). Thus, we assume that \(a\) belongs to two sets, say, \(U_{i},U_{j}\). However, \(U^{\prime}_{i}\cap U^{\prime}_{j}\
eq\emptyset\). If \(b\in U^{\prime}_{i}\cap U^{\prime}_{j}\), then we would be unable to separate \(a\) from \(b\). Of course, \(a\) cannot belong to all \(U_{1},\ldots,U_{4}\), as we would be unable to separate elements in \(\{7,8,9,10\}\setminus\{a\}\) from \(a\). Thus, we may conclude that \(a\) belongs to three of the sets \(U_{1},\ldots,U_{4}\). In order to guarantee that \(7,8,9,10\) are separated from each other, each must be missing in a separate set.