# Binary-Tree-Fed Mixnet: An Efficient Symmetric Encryption Solution
## 3 Binary-Tree-Fed Mixnets
### Overview  
The presented scheme consists of three stages. The first one allows mix nodes to share secret keys with users but preserve privacy. The second stage configures a fixed permutation on each node of the mixnet. The last stage is the production mode, where users can continuously send messages.  
In the first stage, each node is placed at the root of a binary node tree. For each root, the remaining nodes form the branches of the tree. Each user links with each node of the last level (nodes without children), called leaf nodes. Through those links, users send fragments of a key and a label they want to share with the root node. Therefore, each leaf node has a key fragment but needs all the other nodes to unveil the key. All the leaf nodes agree on a permutation and shuffle their fragments with it. Each pair of leaf nodes delivers the batch to its parent node in the next level. Each parent node creates an XOR operation with the key fragments at the same position of the batch. In this level, all the nodes agree on a permutation, which is applied to the result. The process is repeated in each level. When it reaches the root node, all the fragments will build the complete key.  
Figure 2 shows a case of a mixnet of seven nodes in which a generic user \(U_{i}\) is feeding with a key \(K_{iG}\) and a label \(L_{iG}\) node \(G\). This couple is divided into four parts: \(K_{iG}=a_{i}\oplus b_{i}\oplus c_{i}\oplus d_{i}\) and \(L_{iG}=a_{i}^{\prime}\oplus b_{i}^{\prime}\oplus c_{i}^{\prime}\oplus d_{i}^{\prime}\). User \(U_{i}\) sends to node \(A\) the couple \((a_{i},a_{i}^{\prime})\), to node \(B\) the couple \((b_{i},b_{i}^{\prime})\), and similarly to nodes \(C\) and \(D\). Notice that, at this moment, only a collusion of \(A,B,C\) and \(D\) is able to unveil the key \(K_{iG}\). These four nodes agree on the permutation \(\pi_{1}\). The four nodes create this permutation for the batch of all users including \(U_{i}\) and deliver the result to the parent node. In the case of nodes \(A\) and \(B\), the parent node is \(E\), which receives the two batches and creates an XOR operation. As the permutation is the same, the first two fragments of the user key will be at the same position in its batch and \(E\) will compute \((a_{i}\oplus b_{i},a_{i}^{\prime}\oplus b_{i}^{\prime})\). Nodes \(E\) and \(F\) agree on a permutation: \(\pi_{2}\). Both of them shuffle their results following it. Then, the result reaches node \(G\), which will be able to build the complete couple \((a_{i}\oplus b_{i}\oplus c_{i}\oplus d_{i},a_{i}^{\prime}\oplus b_{i}^{\prime }\oplus c_{i}^{\prime}\oplus d_{i}^{\prime})\), that is, \((K_{iG},L_{iG})\).  
In the second stage, each user sends a vector with the encrypted labels. In the example of Figure 2, it is \((L_{iA},L_{iB}\oplus K_{iA},L_{iC}\oplus K_{iA}\oplus K_{iB},...,L_{iG}\oplus K _{iA}...K_{iF})\), assuming that the mixnet sequence is \(A,B,C,...,G\). Each node chooses a permutation and sets it. Each node receives a batch of vectors whose first element is a label stored in the previous stage. This process can be observed in Figure 3. Then, each node finds the label in its table and links the corresponding key to the input position of the batch. Next, it removes its label from the vector and applies this key to the remaining values, which is sent to the next node. In the example, \(B\) receives \((L_{iB},L_{iC}\oplus K_{iB},L_{iD}\oplus K_{iB}\oplus K_{iC},...,L_{iG}\oplus K _{iB}...K_{iF})\). Then, at each position \(i\) of the batch, it looks for \(L_{iB}\) in its table and finds \(K_{iB}\) in the same row. Now, \(B\) knows which key \(K_{iB}\) to apply to which incoming batch position in the next stage. This node then removes key \(K_{iB}\) from each element of the label vector