Mixnets are widely believed to hide communication metadata of individuals. We show that there are various pitfalls when designing mixnet topologies and routing strategies, in particular when choosing mixnets with low delays. We introduce a tool that empirically evaluates such leakage in mixnets and show that this tool precisely estimates this leakage for recipient anonymity, up to an error introduced by sampling. First, we introduce a novel generic attack strategy that we even prove to be optimal for breaking recipient anonymity. In contrast to prior work, our attack strategy incorporates the severity of each observation's leakage, via its so-called privacy loss. Second, our tool provides a lower bound on an attacker's advantage against recipient anonymity by sampling a large set of observations; if a significant number of observations with high privacy loss is observed, the tool outputs a lower bound on the leakage by providing a lower bound on the mass of the tail of the distribution of privacy losses. From the literature, we study the topology and routing strategies of the Karaoke and Atom protocols, provide bounds on their leakage, and recommend design choices based on the analysis.

While many anonymous communication (AC) protocols have been proposed to provide anonymity over the internet, scaling to a large number of users while remaining provably secure is challenging. We tackle this challenge by proposing a new scaling technique to improve the scalability/anonymity of AC protocols that distributes the computational load over many nodes without completely disconnecting the paths different messages take through the network. We demonstrate that our scaling technique is useful and practical through a core sample anonymous broadcast protocol, Streams, that offers provable security guarantees and scales for a million messages. The scaling technique ensures that each node in the system does the computation-heavy public key operation only for a tiny fraction of the total messages routed through the Streams network while maximizing the mixing/shuffling in every round. Our experimental results show that Streams can scale well even if the system has a load of one million messages at any point in time, with a latency of 16 seconds while offering provable “one-in-a-billion” unlinkability, and can be leveraged for applications such as anonymous microblogging and network-level anonymity for blockchains. We also illustrate by examples that our scaling technique can be useful to other AC protocols to improve their scalability and privacy, and can be interesting to protocol developers.

Oblivious RAM (ORAM) allows a client to out-source storage to a remote server while hiding the data access pattern from the server. Many ORAM designs have been proposed to reduce the computational overhead and bandwidth blowup for the client. A recent work, Onion Ring ORAM (CCS'19), is able to achieve$O(1)$bandwidth blowup in the online phase using fully homomorphic encryption (FHE) techniques, at the cost of a computationally expensive client-side offline phase. Furthermore, such a scheme can be categorized as a stateful construction, meaning that the client has to locally maintain a dynamic state representing the order of remote database elements. We present Panacea: a novel design of ORAM based on FHE techniques, which is non-interactive and stateless, achieves$O(1)$bandwidth blowup, and does not require an expensive offline phase for the client to perform; in that sense, our design is the first of its kind among other ORAM designs. To provide the client with such performance benefits, our design delegates all expensive computation to the resourceful server. We additionally show how to boost the server performance significantly using probabilistic batch codes at the cost of only 1.5x in additional bandwidth blowup and 3x expansion in server storage, but less amortized bandwidth. Our experimental results show that our design, with the batching technique, is practical in terms of server computation overhead as well. Specifically, for a database size of 219, it takes only 1.16 seconds of amortized computation time for a server to respond to a query. As a result of the statelessness and low computational overhead on the client, and reasonable computational overhead on the server, our design is very suitable to be deployed as a cloud-based privacy-preserving storage outsourcing solution with a portable client running on a lightweight device.

This work formally analyzes the anonymity guarantees of continuous stop-and-go mixnets and attempts to answer the titular question. Existing mixnet based anonymous communication protocols that aim to provide provable anonymity guarantees rely on round-based communication models, which requires synchronization among all the nodes and clients that is difficult to achieve in practice. Continuous stop-and-go mixnets (e.g., Loopix and Nym) provide a nice alternative by adding a random delay for each message on every hop independent of all other hops and all other messages. The core anonymization technique of continuous mixnets combined with the fact that the messages are sent by the clients to the mixnet at different times makes it a difficult problem to formally prove security for such mixnet protocols; existing end-to-end analyses for such designs provide only experimental evaluations for anonymity and were lacking a comprehensive formal treatment. We are the first to close that gap and provide a formal analysis. We provide two indistinguishability based definitions (of sender anonymity), namely pairwise unlinkability and user unlinkability, tuned specifically for continuous stop-and-go mixnets. We derive the adversarial advantage as a function of the protocol parameters for the two definitions. We show that there is a fundamental lower bound on the adversarial advantage $\delta$ for pairwise unlinkability; however, strong user unlinkability (negligible adversarial advantage) can be achieved if the users message rate ($\lambda_u$) is proportional to message processing rate ($\lambda$) on the nodes.

We analyze the anonymity provided by continuous mixnets (e.g., Loopix) when messages with different latency requirements are sent through the same network. The anonymity provided by existing mixnets that offer bounded latency guarantees has only been studied considering that all the traffic in the network follows the same latency distribution. In this work we evaluate whether it is beneficial to aggregate different types of traffic in the same network or to keep them separate, when the latency distributions are exponential and the traffic arrivals are a poisson process --- as is the case in Loopix and related designs. We present a novel evaluation method to analyze the leakage to the adversary when multiple different types of traffic are sent through the same network of continuous mixes. We apply the method to empirically evaluate the end-to-end anonymity (in terms of entropy) for each type of traffic in the presence of a global passive adversary that may additionally compromise a constant fraction of mixes or may have knowledge about the type of traffic of network output messages. Finally we show via empirical evaluation using our analytical framework that it is beneficial for anonymity to blend different types of traffic in the same mixnet.

Oblivious RAM (ORAM) allows a client to outsource database storage to a remote server while hiding the data access pattern. Existing designs use non-linear data structures (e.g., trees or hierarchical structures) and follow a online-offline paradigm. Clients submit their queries in the online phase and then the queries are ''flushed'' in the offline (eviction) phase. Such designs are interactive, requiring more than one round of client-server communication, be it during the online, offline, or both phases. Moreover, the client has to maintain an internal state which depends on the database state.

Machine learning as a service scenario typically requires the client to trust the server and provide sensitive data in plaintext. However, with the recent improvements in fully homomorphic encryption (FHE) schemes, many such applications can be designed in a privacy-preserving way. In this work, we focus on such a problem, private decision tree evaluation (PDTE) --- where a server has a decision tree classification model, and a client wants to use the model to classify her private data without revealing the data or the classification result to the server. We present an efficient non-interactive design of PDTE, that we call SortingHat, based on FHE techniques. As part of our design, we solve multiple cryptographic problems related to FHE: (1) we propose a fast homomorphic comparison function where one input can be in plaintext format; (2) we design an efficient binary decision tree evaluation technique in the FHE setting, which we call homomorphic traversal, and apply it together with our homomorphic comparison to evaluate private decision tree classifiers, obtaining running times orders of magnitude faster than the state of the art; (3) we improve both the communication cost and the time complexity of transciphering, by applying our homomorphic comparison to the FiLIP stream cipher. Through a prototype implementation, we demonstrate that our improved transciphering solution runs around 400 times faster than previous works. We finally present a choice in terms of PDTE design: we present a version of SortingHat without transciphering that achieves significant improvement in terms of computation cost compared to prior works, and another version t-SortingHat with transciphering that has a communication cost about 20 thousand times smaller but comparable running time.

There is a growing demand for network-level anonymity for delegates at global organizations such as the UN and Red Cross. Numerous anonymous communication (AC) systems have been proposed over the last few decades to provide anonymity over the internet; however, they introduce high latency overhead, provide weaker anonymity guarantees, or are difficult to deploy at the organizational networks. Recently, the PriFi system introduced a client/relay/server model that suitably utilizes the organizational network topology and proposes a low-latency, strong-anonymity AC protocol. Using an efficient lattice-based (almost) keyhomomorphic pseudorandom function and Netwon’s power sums, we present a novel AC protocol OrgAn in this client/relay/server model that provides strong anonymity against a global adversary controlling the majority of the network. OrgAn’s cryptographic design allows it to overcome several major problems with any realistic PriFi instantiation: (a) unlike PriFi, OrgAn avoids frequent, interactive, slot-agreement protocol among the servers; (b) a PriFi relay has to receive frequent communication from the servers, which can not only become a latency bottleneck but also reveal the access pattern to the servers and increases the chance of server collusion/coercion, while OrgAn servers are absent from any real-time process. We demonstrate how to make this public-key cryptographic solution scale equally well as the symmetric-cryptographic PriFi with practical pre-computation and storage requirements. Through a prototype implementation, we show that OrgAn provides similar throughput and end-to-end latency guarantees as PriFi, while still discounting the setup challenges in PriFi.

Abstract For anonymous communication networks (ACNs), Das et al. recently confirmed a long-suspected trilemma result that ACNs cannot achieve strong anonymity, low latency overhead and low bandwidth overhead at the same time. Our paper emanates from the careful observation that their analysis does not include a relevant class of ACNs with what we call user coordination where users proactively work together towards improving their anonymity. We show that such protocols can achieve better anonymity than predicted by the above trilemma result. As the main contribution, we present a stronger impossibility result that includes all ACNs we are aware of. Along with our formal analysis, we provide intuitive interpretations and lessons learned. Finally, we demonstrate qualitatively stricter requirements for the Anytrust assumption (all but one protocol party is compromised) prevalent across ACNs.

This work investigates the fundamental constraints of anonymous communication (AC) protocols. We analyze the relationship between bandwidth overhead, latency overhead, and sender anonymity or recipient anonymity against the global passive (network-level) adversary. We confirm the trilemma that an AC protocol can only achieve two out of the following three properties: strong anonymity (i.e., anonymity up to a negligible chance), low bandwidth overhead, and low latency overhead. We further study anonymity against a stronger global passive adversary that can additionally passively compromise some of the AC protocol nodes. For a given number of compromised nodes, we derive necessary constraints between bandwidth and latency overhead whose violation make it impossible for an AC protocol to achieve strong anonymity. We analyze prominent AC protocols from the literature and depict to which extent those satisfy our necessary constraints. Our fundamental necessary constraints offer a guideline not only for improving existing AC systems but also for designing novel AC protocols with non-traditional bandwidth and latency overhead choices.