# 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\)
Thus, \(\mathcal{SF}\) consists of the following sets (where the dots '\(\ldots\)' stand for yet unknown element or elements):  
\[\{1,2,3\},\{1,\ldots\},\{2,\ldots\},\{3,\ldots\}\,.\]  
Element 4 must belong to at least two sets; otherwise, if 4 belonged only to \(F\in\mathcal{SF}\), it could not be separated from other elements from \(F\). It cannot belong to all of them, as then it would be impossible to separate 5 from 4. Thus, up to renaming the nodes, \(\mathcal{SF}\) consists of the following sets:  
\[\{1,2,3\},\{1,4,\ldots\},\{2,4,\ldots\},\{3,\ldots\}\,.\]  
Now, element 5 must go in the last set (as there is no set in \(\mathcal{SF}\) with only a single element), and the other 5 to either \(\{1,4,\ldots\}\) or \(\{2,4,\ldots\}\), providing the solutions \(\{\{1,2,3\},\{1,4,5\},\{2,4\},\{3,5\}\}\) and \(\{\{1,2,3\},\{1,4\},\{2,4,5\},\{3,5\}\}\) (see Figure 6). In fact, these solutions are the same, only the nodes are renamed. **\(\Psi(6)=4\):** We have a separating family \(\mathcal{SF}\) consisting of four sets: \(\{1,3,6\}\), \(\{2,4,6\}\), \(\{1,2,5\}\), \(\{3,4,5\}\). As \(\Psi(6)\geq\Psi(4)=4\), we can conclude that \(\Psi(6)=4\). For later use, we show that this is the only solution up to a permutation of nodes. Let \(\mathcal{SF}\) be a separating family containing four sets. First, we observe that there is no set \(F\in\mathcal{SF}\) with one or two elements. By way of contradiction, we can assume that \(F\) is such a set. Then, \(U=\{1,\ldots,6\}\setminus F\) contains at least four elements. To separate them, we need at least four elements in \(\mathcal{SF}\), as \(\Psi(4)=4\). None of these sets is \(F\), because \(F\) does not separate any pair of elements from \(U\). Thus, together, we would have at least five sets in \(\mathcal{SF}\), which is a contradiction. If \(F\) contains four or more elements, a similar argument applies. To separate the elements of \(F\), we need at least \(\Psi(4)=4\) sets, where none of them is \(F\). Thus, we can conclude that \(\mathcal{SF}\) contains only sets of cardinality 3. The next observation is that if \(\{a,b,c\}\in\mathcal{SF}\), then \(a\) must appear in at least one other set \(F^{\prime}\in\mathcal{SF}\) to separate it from \(b,c\). As four sets with three elements each have twelve elements altogether (with repetitions), each element must appear in exactly two sets from \(\mathcal{SF}\). Figure 6: An optimal separating family for five nodes consisting of four sets \(F_{1},\ldots,F_{4}\). Now, let us construct an optimal solution (up to renaming the nodes). Without loss of generality, assume that \(\{1,2,3\}\in\mathcal{SF}\). Thus, \(\mathcal{SF}\) consists of the sets having the following form (the asterisk \(*\) stands for an unknown element):  
\[\{1,2,3\},\{1,*,*\},\{2,*,*\},\{3,*,*\}\,.\]  
Element 4 belongs to two sets; because of symmetry (permuting \(\{1,2,3\}\)), we may assume that \(\mathcal{SF}\) consists of the following sets:  
\[\{1,2,3\},\{1,4,*\},\{2,4,*\},\{3,*,*\}\,.\]  
We need to put the remaining elements 5 and 6 in place of the asterisks. One of them falls into \(\{1,4,*\}\), say, element 5; consequently, it cannot appear in \(\{2,4,*\}\), as then we could not separate 4 and 5. This means that 5 is placed in \(\{3,*,*\}\), and 6 must then be placed in the remaining two places, providing the following solution (see Figure 7):  
\[\{1,2,3\},\{1,4,5\},\{2,4,6\},\{3,5,6\}\,.\]  
**\(\Psi(7)=5\):**: First, we note that \(\Psi(7)\leq\Psi(6)+1=5\) by Lemma 2. We also know that \(\Psi(7)\geq\Psi(6)\). Assuming towards contradiction that \(\Psi(7)=4\), let \(\mathcal{SF}\) be a separating family with four sets; we first consider the case in which no set in \(\mathcal{SF}\) contains more than two elements. Each element of \(\{1,\ldots,7\}\) must belong to some set in \(\mathcal{SF}\), meaning that at least three out of four sets in \(\mathcal{SF}\) must be disjoint (say, \(\{1,2\}\), \(\{3,4\}\), \(\{5,6\}\) are in \(\mathcal{SF}\)).