Abstract: Existing anonymity systems sacrifice anonymity for efficient communication or vice-versa. Onion-routing achieves low latency, high bandwidth, and scalable anonymous communication, but is susceptible to traffic analysis attacks. Designs based on DC-Nets, on the other hand, protect the users against traffic analysis attacks, but sacrifice bandwidth. Verifiable mixnets maintain strong anonymity with low bandwidth overhead, but suffer from high computation overhead instead. In this paper, we present Riffle, a bandwidth and computation efficient communication system with strong anonymity. Riffle consists of a small set of anonymity servers and a large number of users, and guarantees anonymity among all honest clients as long as there exists at least one honest server. Riffle uses a new hybrid verifiable shuffle technique and private information retrieval for bandwidth-and computation-efficient anonymous communication. Our evaluation of Riffle in file sharing and microblogging applications shows that Riffle can achieve a bandwidth of over 100KB/s per user in an anonymity set of 200 users in the case of file sharing, and handle over 100,000 users with less than 10 second latency in the case of microblogging. Keywords: anonymous communication; verifiable shuffle; private information retrieval DOI 10.1515/popets-2016-0008 Received 2015 revised 2015-12-02; accepted 2015-12-02. The right to remain anonymous is a fundamental right in a democratic society and is crucial for freedom of speech [49] . Anonymizing networks based on relays such as Tor [26] There are two major branches of work that offer traffic analysis resistance even in the presence of a powerful adversary. The first is Dining-Cryptographer Networks (DC-Nets) [16] , which offer information theoretically secure anonymous communication for users as long as one other participant is honest. Dissent [53] improved upon DC-Nets by moving to the anytrust model, where the network is organized as servers and clients, and guarantees anonymity as long as there exists one honest server. The second is verifiable mixnets, based on mix networks [18] . In this design, the mixes use a verifiable shuffle [7, 13, 28, 37 ] to permute the ciphertexts, and produce a third-party verifiable proof of the correctness of the shuffle without revealing the actual permutation. Similar to DC-Net based systems, verifiable mixnets guarantee anonymity as long as one mix in the network is honest. Both designs, however, suffer from serious drawbacks. DC-Nets and DC-Net based systems, by design, implement a broadcast channel. That is, they were primarily designed for the case where one client messages everyone in the network. Thus, when multiple users wish to communicate simultaneously, every user must transfer a message of size proportional to the number of clients who wish to communicate. As a result, DC-Net based designs suffer from a large bandwidth overhead, and only scale to a few thousand clients [23, 53] . Verifiable mixnets, on the other hand, allow the clients to send messages of size proportional only to their own messages, and thus can be bandwidth efficient. However, the high computation overhead of verifiable shuffles has prevented verifiable mixnets from supporting high bandwidth communication. In this paper, we present Riffle, a system for bandwidth-and computation-efficient anonymous communication. Riffle addresses the problems of DC-Nets and verifiable mixnets, while offering the same level of anonymity. At a high level, Riffle is organized as servers and clients, similar to previous works [21, 23, 53] . RifUnauthenticated Download Date | 4/9/19 4:58 AM Riffle 116 fle focuses on minimizing the bandwidth consumption of the clients, who may be connecting from bandwidthconstrained environments such as their mobile phones, and reducing the computation overhead on the servers so they can support more clients. Specifically, the clients in Riffle consume upstream bandwidth proportional only to the size of their messages rather than the number of clients, and the server computation only involves fast symmetric key cryptography in the common case. This allows the users to exchange messages efficiently, making it suitable for applications like file sharing that no existing strong anonymity system can support well. Moreover, Riffle provides strong anonymity for all clients as long as one of the servers is honest. Riffle achieves bandwidth and computation efficiency by employing two privacy primitives: a new hybrid verifiable shuffle for upstream communication, and private information retrieval (PIR) [20] for downstream communication. Our novel hybrid verifiable shuffle scheme avoids using an expensive verifiable shuffle in the critical path, and employs authenticated encryption to improve both bandwidth and computation overhead of the shuffle without losing verifiability. We also propose a novel application of private information retrieval in the anytrust setting. Previous strong anonymity systems made a trade-off between computation and bandwidth by either broadcasting all messages to all users (low computation, high bandwidth) [21, 23, 53] , or using computationally expensive PIR (high computation, low bandwidth) [47] . In the anytrust model, we show that PIR can minimize the download bandwidth with minimal computation overhead. We also develop a Riffle prototype and two applications. The first is an anonymous file sharing application, where each message is large and is potentially of interest to only a small number of users. Sharing large files is a scenario that has not been considered carefully by previous strong anonymity systems [7, 21, 53] ; we propose a new file sharing protocol that leverages and illustrates Riffle's bandwidth-efficiency. The second application is for anonymous microblogging, similar to applications studied in previous works [21, 53] . In this setting, each user posts small messages to the server, and each message is of interest to many users. Our prototype demonstrates effectiveness for both applications. In file sharing, the prototype achieves high bandwidth (over 100KB/s) for more than 200 clients. In microblogging, the prototype can support more than 10,000 clients with latency less than a second, or handle more than 100,000 clients with latency of less than 10 seconds. We show that our results are orders of magnitude better in terms of both scalability and bandwidth compared to previous systems offering traffic analysis resistance [7, 48, 53] in comparable scenarios. This paper makes the following contributions: 1. A hybrid verifiable shuffle that uses symmetric encryption, and avoids expensive public key verifiable shuffling [7, 13, 28, 37]
Riffle REF introduces a new verifiable shuffle technique to achieve sender anonymity.
Riffle : an efficient communication system with strong anonymity
PoPETs
PoPETs
Computer Science