# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 4 Sender Authentication
### Two Malicious Receiver Nodes
Thus, we are left with \(W_{5},W_{7}\) only. However, they are incident, and \(\mathcal{F}_{j}\) would contain only two sets, contradicting Claim 11. * In the same way, we argue that \(W_{5}\
ot\in\mathcal{F}_{j}\). The only option left that satisfies both claims is \(\mathcal{F}_{j}=\{W_{6},W_{2},W_{7}\}\); thus, we conclude that every \(j\geq 5\) belongs to the same sets \(W_{6},W_{2},W_{7}\). However, this is wrong, as now these elements cannot be separated from each other. **Case 2. **_There is a trace with three or more elements._  
Let \(U\in SF\) have a trace of cardinality at least \(3\). Without loss of generality, we may assume that \(1,2,3\in U\). Our argument below disregards whether \(4\in U\); however, to focus the attention, the reader may think about \(\mathsf{Tr}(U)=\{1,2,3\}\). Let \(\mathcal{SF}^{\prime}=\mathcal{SF}\setminus\{U,V^{\prime}\}\). **Claim 12**. : _Let \(i\leq 3\). There are at least two sets \(F\in SF^{\prime}\) such that \(i\in F\)._  
**Proof. ** Assume that there is only one such set \(F\). Consider \(j\in F\setminus\{i\}\) and \(j^{\prime}\in\{1,2,3\}\setminus\{i\}\). Then, \(i\) cannot be separated from \(j,j^{\prime}\). **Definition 8**. : _Let the \(U\)-trace of an element \(F\in\mathcal{SF}^{\prime}\) be defined as \(\mathsf{Tr}_{U}(F)=F\cap U\)._  
**Claim 13**. : _If there are exactly two traces of sets \(F\in SF^{\prime}\) such that \(i\in F\), then their \(U\)-traces are \(\{i\}\)._  
**Proof. ** Assume that \(i\in F_{1},F_{2}\), where \(F_{1},F_{2}\in\mathcal{SF}\) and \(\mathsf{Tr}_{U}(F_{1})\
eq\{i\}\). Let \(j\in\mathsf{Tr}_{U}(F_{1})\), where \(j\in\{1,2,3,\}\setminus\{i\}\). Then, \(i\) cannot be separated from \(j\) and \(j^{\prime}\), where \(j^{\prime}\) is an arbitrary element of \(F_{2}\setminus\{i\}\). **Claim 14**. : _If there are exactly three traces of sets \(F\in SF^{\prime}\) such that \(i\in F\), but for one of them the trace is \(\{1,2,3\}\), then the two remaining ones have \(U\)-trace \(\{i\}\)._  
Proof. : We use the same argument as for Claim 13. The reason is that if \(\mathsf{Tr}_{U}(F)=\{1,2,3\}\), then \(F\) cannot be used to separate \(i\) from other elements \(1,2,3\). From Claims 13 and 14, the following situations may occur for an element \(i\leq 3\) (we disregard the sets with \(U\)-trace \(\{1,2,3\}\)) (see Figure 13 below):  
* \(\mathsf{I}\)-profile: \(i\) belongs to exactly two sets \(F_{1},F_{2}\in\mathcal{SF}^{\prime}\). Then, \(\mathsf{Tr}_{U}(F_{1})=\mathsf{Tr}_{U}(F_{2})=\{i\}\). * \(\mathsf{h}\)-profile: \(i\) belongs to exactly three sets \(F_{1},F_{2},F_{3}\in\mathcal{SF}^{\prime}\), where \(|\mathsf{Tr}_{U}(F_{1})=|\mathsf{Tr}_{U}(F_{2})|=1\) and \(|\mathsf{Tr}_{U}(F_{3})|=2\). * \(\mathsf{m}\)-profile: \(i\) belongs to exactly three sets \(F_{1},F_{2},F_{3}\in\mathcal{SF}^{\prime}\), where \(|\mathsf{Tr}_{U}(F_{1})=1\) and \(|\mathsf{Tr}_{U}(F_{2})|=|\mathsf{Tr}_{U}(F_{3})|=2\). * more-profile: any of the above, but a trace may correspond to more sets. We assign weights each set \(F\in\mathcal{SF}^{\prime}\) (again, we disregard the sets with \(U\)-trace \(\{1,2,3\}\)):  
* If \(|\mathsf{Tr}_{U}(F)|=1\), then \(\mathsf{weight}(F)=1\);
* If \(|\mathsf{Tr}_{U}(F)|=2\), then \(\mathsf{weight}(F)=\frac{1}{2}\). If \(i\leq 3\), then \(\mathsf{weight}(i)=\sum_{i\in F,F\in\mathcal{SF}^{\prime}}\mathsf{weight}(F)\). By definition,  
**Claim 15**. : \(\sum_{i=1,2,3}\mathsf{weight}(i)\leq|\mathcal{SF}^{\prime}|\). Let us consider the weights for each profile:  
* \(\mathsf{weight}(i)=2\), if \(i\) has \(\mathsf{I}\)-profile;
* \(\mathsf{weight}(i)=2.5\), if \(i\) has \(\mathsf{h}\)-profile;
* \(\mathsf{weight}(i)=2\), if \(i\) has \(\mathsf{m}\)-profile;
* \(\mathsf{weight}(i)>2\), if \(i\) has \(\mathsf{m}\)-profile. Thus, we see that if \(\mathsf{weight}(i)>2\) for any \(i\leq 3\), then there are more than six sets in \(\mathcal{SF}^{\prime}\). As \(\mathcal{SF}=\mathcal{SF}^{\prime}\cup\{U,V^{\prime}\}\), there are at least nine sets in \(\mathcal{SF}\).