# Authenticated Multicast in Tiny Networks via an Extremely Low-Bandwidth Medium
## 3 Establishing Group Keys
### Summing Strategies
#### 3.1.2 Optimizing the Summing Strategy  
We can ask how far it is possible to optimize the selection of the family \(\{S_{1},\ldots,S_{m}\}\), given that each group key must be established by at most \(k\) multicast messages. Unfortunately, it turns out that finding the optimal choice reduces to a long-studied combinatorial problem. For this problem, solutions have been found only for a few small input values. Below, we go into details. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Number of Receiver Nodes** & \(k\) & **\# Group Keys per Receiver** & **\# Keys Stored by the Sender** \\ \hline
8 & 2 & 7 & 22 \\
8 & 4 & 1 & 4 \\
16 & 2 & 127 & 494 \\
16 & 4 & 7 & 44 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Example number of group keys per node with the method from Section 3.1.1. Let \(\mathcal{P}\) be a family of subsets of \(\mathcal{N}\) such that for each \(\mathcal{R}\in\mathcal{P}\) a key \(K_{\mathcal{R}}\) is preloaded to the sender \(S\) corresponding to the group \(\mathcal{R}\). For simplicity, we shall disregard the distinction between group keys and the one-to-one link keys, and allow \(\mathcal{P}\) to contain the keys \(K_{i}\) corresponding to the singletons \(\{i\}\subset\mathcal{N}\). For concreteness, let us assume that \(S\) can send only four messages to transport the group key to the group members (that is, in the pseudocode at the beginning of this section, \(w\leq 4\) for every multicast group). In the following, we shall find a connection between our optimization problem and an old problem from combinatorics. We start in the following way. First, consider a set \(\mathcal{R}\) of at least \(5\) nodes of \(\mathcal{N}\). To transmit the group key to \(\mathcal{R}\), we must use at least one set \(P\in\mathcal{P}\) of cardinality at least \(2\). Let us narrow our attention to receiver sets of cardinality exactly \(5\). Let \(\mathcal{N}_{5}=\mathcal{N}_{5}(n)\) denote the family of subsets of \(\mathcal{N}\) of cardinality \(5\). Let \(\mathcal{P}^{\prime}\) be a subfamily of \(\mathcal{P}\) restricted to subsets of \(\mathcal{N}\) of cardinality at most \(5\). Note that only the sets from \(\mathcal{P}^{\prime}\) can contribute to establishing a group key for a receiver set \(\mathcal{R}\in\mathcal{N}_{5}\). Let \(\mathcal{P}^{\prime\prime}\) be obtained by reducing each \(A\in\mathcal{P}^{\prime}\) of cardinality greater than \(2\) to its randomly chosen \(2\)-element subset. Then, for each \(D\in\mathcal{N}_{5}\) there is a family of at most \(4\) elements of \(\mathcal{P}^{\prime\prime}\) with union to \(D\). According to our assumptions, there exist sets \(P_{1},\ldots,P_{u}\in\mathcal{P}\), \(u\leq 4\), such that \(D=\bigcup_{i=1}^{u}P_{i}\). At least one \(P_{i}\) has cardinality at least \(2\). There is a \(2\)-element subset \(B\) of \(P_{i}\) that belongs to \(\mathcal{P}^{\prime\prime}\). Finally, \(D=B\cup\{j_{1}\}\cup\{j_{2}\}\cup\{j_{3}\}\), where \(\{j_{1},j_{2},j_{3}\}=D\setminus B\). Let \(\gamma_{5}=\gamma_{5}(n)\) be the minimal cardinality of a family \(\mathcal{F}\) of \(2\)-element subsets of \(\mathcal{N}\) such that for every \(G\in\mathcal{N}_{5}\) there exists \(A\in\mathcal{F}\) such that \(A\subset G\). The family \(\mathcal{P}\) contains at least \(\gamma_{5}\) elements. Obviously, \(|\mathcal{P}|\geq|\mathcal{P}^{\prime}|\geq|\mathcal{P}^{\prime\prime}|\) (note that it may happen that \(|\mathcal{P}^{\prime}|>|\mathcal{P}^{\prime\prime}|\), as for two elements of \(\mathcal{P}^{\prime}\) we may choose the same \(2\)-element set \(A\)). Per Lemma 1, \(\mathcal{P}^{\prime\prime}\) satisfies the conditions from Definition 1; thus, \(|\mathcal{P}^{\prime\prime}|\geq\gamma_{5}\). Now, let us recall the following classic concept from combinatorics [13]:  
A family of \(k\)-element subsets of \(\{1,2,\ldots,v\}\), called _blocks_, is a \((v,k,t)\)-covering design if each \(t\)-element subset of \(\{1,2,\ldots,v\}\) is contained in one of the blocks.