# Binary-Tree-Fed Mixnet: An Efficient Symmetric Encryption Solution
## 1 Introduction  
Anonymity is a service required in several applications like e-voting, journalism, surveys, etc. Additionally, it is a desirable feature in order to mitigate the threats of communications surveillance. For these reasons, many anonymous communication systems have been proposed [1, 2]. These can be classified by their strategies [3]. One of them is to build a broadcast channel where all users participate. These schemes are known as DC-nets (Dinning Cryptograpishers Network) [4] and have some variants, such as Dissent (Dining Cryptographers Shuffled Send Network) [5] or BAR (Broadcast Anonymous Routing) [6]. These protocols offer a high level of privacy, but they lack flexibility, require all participants' cooperation, and allow only one user to communicate in one protocol round, which implies low throughput. Another technique is hiding the transmission path by multiple hops. For example, Tor (The Onion Router) [7], Herd [8], Hornet [9], TresMep (Tracking-resistant Communication Mechanism with Dynamic Paths) [10], Misty Clouds [11], dPHI (dependable Path-Hldden lightweight anonymity protocol) [12], and Nym [13] belong to this category. These onion routing systems are suitable for low-latency communications in environments where messages arrive at different times in an almost constant flow. Nevertheless, they are vulnerable to traffic analysis [14, 15] and attacks from adversary nodes [16, 17]. The third approach is the use of mixnets. They are sequences of nodes that work with batches of messages. Each node makes a cryptographic operation and shuffles the batch,thus breaking the relationship between incoming and outgoing messages [18]. Mixnets have evolved and diversified widely in recent years. They started with [19], where users have to encrypt their messages with the public keys of the nodes. Then, each one decrypts the batch with its private key. These were followed by the so-called \"encryption mixnets\" [20]. Taking advantage of the properties of the ElGamal cryptosystem, this new category provides greater privacy and less delay for users and nodes. An effort to improve efficiency is the combination of asymmetric and symmetric encryption. This gave rise to hybrid mixnets [21; 22; 23]. Instead of encrypting the entire message with public keys, what is encrypted with these is a symmetric one. Then, the message encrypted with the latter is appended. This solution reduces the high computational effort of asymmetric encryption to the few bits of a symmetric key. However, this does not bypass exponential calculations and must add symmetric decryption to the process. A better idea is cMIX (fixed cascade mixnet), proposed in [24], where operations in users and nodes are reduced to a set of modular multiplications. Although the latency in the production phase is small, each message must traverse the mixnet twice. Moreover, it requires a precomputation phase where a set of asymmetric cryptographic operations must be carried out. Another solution is the use of alternative encryption methods like lattice-based ones [25], which can be six times faster than traditional mixnets [26]. However, these methods are relatively new and require deeper research [27; 28]. The first pure symmetric mixnet was SEBM (Symmetric-Key-Encryption-Based Mixnet) [29], improved with ESEBM (Enhanced SEBM) [30]. In these schemes, nodes generate keys and an identifier linked to it in an internal table. These values are propagated, shuffled, and blinded from the last node in a predefined sequence to the first one, which delivers them to users. Then, users send their encrypted messages to the mixnet, which is composed in another different sequence. There is no need for asymmetric operations in any step, which provides this scheme the highest speed. However, each message entails a vector of identifiers that must be found in a table at each step. Moreover, depending on the place each node occupies in the mixnet, several vulnerabilities arise. Some of them could be exploited by just one adversary.