# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Two Malicious Receiver Nodes  
Separating families do not address the case where two malicious receivers in a multicast group share their keys and can forge more tags when impersonating the sender. Therefore, we consider the following stronger notion:  
**Definition 6**. : _We say that a family \(\mathcal{SF}\) of subsets of \(\mathcal{R}\) is a 2-separating family for \(\mathcal{R}\) if, for every \(i,j_{1},j_{2}\in R\), \(i\
eq j_{1},j_{2}\), there is a subset \(F\in\mathcal{SF}\) such that \(i\in F\) and \(j_{1},j_{2}\
ot\in F\). We say that \(F\) separates \(i\) from \(j_{1}\) and \(j_{2}\)._  
In the case depicted in Figure 9, the tag created with the key corresponding to set \(F_{1}\) can be verified by node 1 but cannot be forged by the malicious nodes 2 and 3. Consider the set \(\mathcal{R}=\{1,\ldots,r\}\). Obviously, the family of \(r\) singletons \(\{1\},\ldots,\{r\}\) is a 2-separating family for \(\mathcal{R}\). Using this family for designing the tags corresponds to creating a dedicated tag for each receiver. Creating a 2-separating family for \(r\) elements and less than \(r\) sets is possible:  
**Lemma 5**. : _For an \(r\)-element set, there is a \(2\)-separating family of cardinality \(2m(m-1)\), where \(m=\lceil\log(r)\rceil\)._  
Proof. : To each element from the set \(\{1,\ldots,r\}\), we can assign a unique identifier of \(\lceil\log r\rceil\) bits. Let us define the sets of the separating family as follows: \(F_{k_{1},a_{1},k_{2},a_{2}}\) contains \(i\leq r\) if and only if \(i\) contains bit \(a_{1}\) on position \(k_{1}\) and bit \(a_{2}\) on position \(k_{2}\). Note that the number of different pairs \((k_{1},k_{2})\) is \(m(m-1)/2\), while for each pair \((k_{1},k_{2})\) we have four options for \(a_{1},a_{2}\). It follows that the defined family has cardinality \(2m(m-1)\). Let \(i,j_{1},j_{2}<r\). To separate \(i\) from \(j_{1}\) and \(j_{2}\), we want to find \(k_{1}\) such that \(i\) and \(j_{1}\) differ on position \(k_{1}\). Similarly, we want to find \(k_{2}\) such that \(i\) and \(j_{2}\) differ on position \(k_{2}\). If \(a_{1},a_{2}\) are the bits corresponding to \(i\) on these positions, then \(F_{k_{1},a_{1},k_{2},a_{2}}\) separated \(i\) from \(j_{1},j_{2}\). The family presented in Lemma 5 enables the number of tags to be reduced while keeping the system resilient against two malicious receivers. However, the method is not very useful from our point of view. For example, for \(r=32\), it requires 40 sets in the 2-separating family, which is more than the 32 provided by the singletons as a 2-separating family. The turning point is \(r=60\), where \(r=2\cdot\lceil\log(r)\rceil\cdot(\lceil\log(r)\rceil-1)\). However, we are interested in values of \(r\) that are much smaller. \begin{table}
\begin{tabular}{l c c c c c c c c c c c c c c} \hline  & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** & **11** & **12** & **13** & **14** & **15** \\ \hline \(F_{1}\) & x & & x & & & x & x & & & & x & & & & \\ \hline \(F_{2}\) & & x & & x & & x & & x & & & & x & & & \\ \hline \(F_{3}\) & x & x & & & x & & & x & & x & & & x & & \\ \hline \(F_{4}\) & & & x & x & x & & & & & x & & & & x & \\ \hline \(F_{5}\) & & & & & & & x & x & x & & x & & & & x \\ \hline \(F_{6}\) & & & & & & & & & & & & x & x & x & x \\ \hline \end{tabular}
\end{table} 
Table 6: \(\mathcal{SF}\) for fifteen elements, with each element belonging to two sets. Figure 9: Set \(F_{1}\in\mathcal{SF}\) separates 1 from \(2,3\), while \(F_{2}\) does not separate 2 from 1 and 3. Below, we show that the hopes to reduce the number of sets in a 2-separating family below \(r\) are futile for \(r\leq 9\) (see Theorem 1). Consequently, for multicast groups of up to nine nodes, the only way to protect against two colluding receivers is to create a separate tag for each receiver. For larger values, say, \(r=10,\ldots,20\)), this is an interesting open problem with direct practical impact.