# Binary-Tree-Fed Mixnet: An Efficient Symmetric Encryption Solution
## 4 Security Analysis
### Analysis  
The objective of adversaries is to link the decrypted message with its author. If the first node is an adversary, it will only need the key because it knows the sender. If the last node is an adversary, it will only need the authorship because the message is decrypted. Intermediate nodes will need the two kinds of information. Definition 1: \"Binary-tree cut\" is defined as a set of nodes of which at least one participates in any connected path between root and leaves. Proposition 1: The nodes capable of learning user keys must necessarily constitute a cut. Proof: The information needed to deduce the key is initially the set of fragments. All the leaf nodes could reconstruct the key, and it is also true that the set defined by them is a cut. If instead of the initial fragments any aggregation of them is available, it can also be reconstructed as long as all the fragments have participated. For a fragment not to have participated, it must happen that, on the path that joins it to the root, there is no node of the cut, which is precisely the definition of cut. Figure 4 shows two examples of binary-tree cuts. Although being a cut is a necessary condition, it is not sufficient. Notice that the cut in Figure 4 has no node of the third level\((i,j,k,l)\); therefore, the elements of the cut are unaware of the permutation carried  
out at said level and cannot associate the keys to the users. However, the cut in Figure 4b is capable. **Proposition 2**. : _For a cut to reveal the keys and associate them with their users, it must have at least one node at each level between the level of the leaves and the lowest level (closest to the root) of the cut._  
Proof. : To construct the keys, in addition to the fragments or aggregations of these, the permutations carried out on them must be known. Only the nodes at each level know their permutation. That is, the collaboration of at least one of the nodes at each level is needed between the extreme nodes of the cut. If the top of the cut is a level that does not correspond to the leaf nodes, then a batch of keys can be obtained, but they cannot be associated with users. The first permutation is only known to the leaf nodes. Therefore, it is necessary to incorporate the information of all the permutations from these to the cut. **Theorem 1**. : _The minimum number of adversaries to learn keys in a binary tree of \(k\) levels is \(k\)._  
Proof. : Given Proposition 1, the minimum number of levels of a cut capable of revealing the keys would be the one constituted by the leaf nodes, whose number is \(2^{k-1}\). Furthermore, it is the only cut possible with this single level given Proposition 2. The fragment information that exists in two leaf nodes is obtained aggregated in their parent nodes. Therefore, if we now consider a cut that includes the next level, each pair of leaf nodes can be replaced by its parent node by reducing the cut by one. It is not possible to conduct it with all of them because at least one leaf node must remain to report the permutation of its level. In this way, different cuts of size \(2^{k-2}+1\) can be established, that is, the nodes of the next level plus a leaf node. This number would be the minimum because with one less node there would always be a lack of information. Now consider a cut \(A\) that reaches level \(r\) formed by a sequence of nodes from a leaf node to \(r\) (minimum number of nodes to know all the permutations) and the rest of the nodes of level \(r\) (those that make up the minimum number to build the keys). That is, \(|A|=2^{r-1}+k-r\) (for example, nodes \(a,i,m\), and \(n\) in Figure 4 for the case \(k=2\) and \(r=2\)). Suppose there is a cut \(B\) with a smaller number of nodes (\(|B|<|A|\)). This cut \(B\) must necessarily exclude nodes from cut \(A\) as it is smaller in number. If the excluded node is one of level \(r\), then it must be replaced with any combination of its descendants, a number never less than two.