# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Two Malicious Receiver Nodes
This contradicts our assumption that there is a \(2\)-separating family with less than \(r\) sets for \(r\leq 9\). **Corollary 5**. : _The only possible profiles of the nodes are \(\mathsf{I}\)-profile and \(\mathsf{m}\)-profile. Moreover, either \(1,2,3\) all have \(\mathsf{I}\)-profile or all have \(\mathsf{m}\)-profile._  
Proof. : The only thing to check here is that if one of the elements has the profile \(\mathsf{m}\)-profile, then all elements have this profile. Let \(1\) have profile \(\mathsf{m}\)-profile; then, there are \(F_{1},F_{2}\) in \(\mathcal{SF}\) such that \(\mathsf{Tr}_{U}(F_{1})=\{1,2\}\) and \(\mathsf{Tr}_{U}(F_{2})=\{1,3\}\). Because of \(F_{1}\), the profile of \(2\) cannot be \(\mathsf{I}\)-profile. Similarly, because of \(F_{2}\), the profile of \(3\) cannot be \(\mathsf{I}\)-profile. Figure 13: Example profiles of element \(1\); each element from \(\mathcal{SF}^{\prime}\) containing \(1\) is represented by an arch. **Case 2A. **_Elements \(1,2,3\) have \(m\)-profile._  
We consider elements \(5,6,7,8,9\) and investigate which sets from \(\mathcal{SF}^{\prime}\) they may belong to. Let the sets of \(\mathcal{SF}^{\prime}\) be called \(Z_{1}\),...\(Z_{6}\), as represented in Figure 14. Note that up to renaming the sets, Figure 14 represents the only possible situation. **Claim 16**. : _Let \(i\geq 5\); then, \(i\) belongs to three different sets from \(\mathcal{SF}^{\prime}\)._  
Proof. : Per Claim 4, \(i\) must belong to at least three sets from \(\mathcal{SF}\). We have to show that these sets must be in \(\mathcal{SF}^{\prime}\). Assume that out of these three sets, the first is either \(U\) or \(V^{\prime}\). Let \(Z_{a}\) be the second (out of three sets, only two might be \(U\) and \(V^{\prime}\)). We take \(j\leq 3\), \(j\in Z_{a}\), and an arbitrary element \(j^{\prime}\
eq i\) from the third set. Then, these three sets cannot separate \(i\) from \(j\) and \(j^{\prime}\). **Claim 17**. : _Let \(i\geq 5\); then, \(i\) belongs to \(Z_{1}\), \(Z_{2}\), \(Z_{3}\)._  
Proof. : To separate \(i\) from \(2\) and \(3\), we have to find a set \(F\in\mathcal{SF}\) such that \(i\in F\) but \(2,3\
ot\in F\). Thus, \(F\
eq U\), \(V^{\prime}\), as \(2,3\in U\), \(V^{\prime}\); moreover, for each \(Z_{k}\), \(k\
eq 1\), either \(2\in Z_{k}\) or \(3\in Z_{k}\) (see Figure 14). The only set left is \(Z_{1}\), meaning that \(i\in Z_{1}\). In a similar way, we show that \(i\in Z_{2},Z_{3}\). **Claim 18**. : _Let \(i\geq 5\); then, \(i\
ot\in Z_{4}\), \(Z_{5}\), \(Z_{6}\)._  
Proof. : Assume for example that \(i\in Z_{5}\); then, consider separating \(1\) from \(i\) and \(3\). For this purpose, we cannot use \(Z_{1}\), \(Z_{5}\), as \(i\in Z_{1}\), \(Z_{5}\), and cannot use \(Z_{4}\), \(U\), \(V^{\prime}\), as \(3\in Z_{4}\), \(U\), \(V^{\prime}\). The remaining cases are shown in the same way. We conclude that \(5,6,7,8,9\) belong to the same sets from \(\mathcal{SF}^{\prime}\). Therefore, to separate \(5,6,7,8,9\) from themselves, we have to use only \(U,V^{\prime}\). However, a separating family for five elements contains at least four sets (see Section 4.5.2), resulting in a contradiction. **Case 2B. **_Elements \(1,2,3\) have \(l\)-profile._  
In Figure 15, we recall the shape of an \(l\)-profile:  
Consider \(i\geq 5\); element \(i\) must be separated from \(2\) and \(3\). The only sets from \(\mathcal{SF}\) that contain neither \(2\) or \(3\) are \(F_{1}\) and \(F_{1}^{\prime}\). Thus, at least one of them must contain \(i\). In addition, observe that \(i\) cannot belong to both \(F_{1}\) and \(F_{1}^{\prime}\). Indeed, in this case it would be impossible to separate \(1\) from \(i\) and \(3\), as \(i\in F_{1}\), \(F_{1}^{\prime}\) while \(3\in U\), \(V^{\prime}\). Figure 14: Traces of sets in \(\mathcal{SF}^{\prime}\) when \(1,2,3\) have \(m\)–profile. Figure 15: Traces of sets in \(\mathcal{SF}^{\prime}\) when \(1,2,3\) have \(l\)–profile. This argument can be repeated for separating \(i\) from \(1,2\) and for separating \(i\) from \(1,3\). In this way, we prove the following claim.