# Binary-Tree-Fed Mixnet: An Efficient Symmetric Encryption Solution
## 3 Binary-Tree-Fed Mixnets
### Formal Description  
Let \(U=\{U_{i}|i=1,2...n\}\) be a set of \(n\) users. Let \(T=\{T_{j}|j=1,2...m\}\) be a set of nodes. The elements of these sets can establish communication links among them. The scheme follows three stages:  
1. _STAGE 1: FEEDING._ The value \(k\) is computed from \(k=\lfloor log_{2}(m+1)\rfloor\). That is, \(k\) is the highest number that accomplishes \(2^{k}-1\leq m\). Then, each user \(U_{i}\) generates \(2^{k}\) random numbers per node. A half builds the keys with each node: \(K_{ij}=K_{ij1}\oplus K_{ij2}...K_{ijn}\), where \(j=1,2...m\) corresponds to different nodes and \(\alpha=2^{k-1}\). The other half are fragments of the labels: \(L_{ij}=L_{ij1}\oplus L_{ij2}...L_{ijn}\). Next, for each node \(T_{j}\), a perfect binary tree of \(k\) levels is established by selecting other nodes randomly until the tree is completed. Nodes collaborate to ensure this randomness against adversaries [31]. The tree is a subset of \(T\) with \(2^{k}-1\) elements, where \(T_{j}\) is the root at the first level. Each node of the tree has two children nodes, occupying the next level. The exception is at the last level, which has \(\alpha=2^{k-1}\) nodes that have no children. To these leaf nodes, each user \(U_{i}\) sends the pair \((K_{ijl},L_{ijl})\), where \(l=1,2,...\alpha\) corresponds to each leaf node. All the nodes in the same level agree on a random permutation \(\pi_{h},h=1,2...k\). Nodes at the last level receive the pairs from users in a batch. Next, they create the same permutation \(\pi_{k}\) and send the result to their parent node. From the level \(k-1\) to the root, each node creates an XOR operation between the pairs received in the same position of the batches. Then, they create the permutation of their level and send the  
Figure 3: Setting stage: user keys (\(K_{ik}\)) are linked to the incoming batch positions (\(u\)) and a random permutation (\(\pi_{uv}\) is established).  
result to their parent node. The root node creates the XOR operation to obtain the pair \((K_{ij},L_{ij})\), which is stored in a table.
2. _STAGE 2: SETTING_. A random sequence of \(T_{1},T_{2},...,T_{m}\) defines the mixnet. Users send to the first node the vector \((L_{i1},L_{i2}\oplus K_{i1},L_{i3}\oplus K_{i1}\oplus K_{i2},...,L_{im}\oplus K _{i1}...K_{i(m-1)})\). Each node \(T_{j}\) of the mixnet looks for the first element \(L_{ij}\) of the vector in its table, where it must be next to the key \(K_{ij}\). Then, it removes the first element of the vector and applies XOR to the remaining elements with \(K_{ij}\). Next, the node establishes a permutation on the input batch and sends the result. From now on, the key \(K_{ij}\) will be applied with any value that comes in the same batch position.
3. _STAGE 3: MIXING_. Users compute \(K_{i}=K_{i1}\oplus K_{i2}\oplus...\oplus K_{im}\). Then, they can anonymously publish any message \(m_{i}\) by sending \(K_{i}\oplus m_{i}\) to the first node of the mixnet. The first node processes the batch of encrypted messages, which will remove its partial key \(K_{i1}\). The next nodes do the same until the last one, which shows a batch of decrypted messages.