Riffle: An Efficient Communication System With Strong Anonymity
Open accessThe DOI matches its Crossref record; 53 of the 56 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures










Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Khodak et al. [270] and Jiang et al. [250] explore the connection between FL and MAML, and show how the MAML setting is a relevant framework to model the personalization objectives for FL.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [270]
Experimental — accuracy not yet measuredThe check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Several challenging FL topics including personalization and privacy have begun to be studied in this multi-task/LTL framework [270, 250, 299].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [270]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
Untraceable electronic mail, return addresses, and digital pseudonyms
Chaum, D. L. (1981) · Communications of the ACM · doi:10.1145/358549.358563 · Cited by 4,289 · cited 1×
“However, such systems are susceptible to traffic analysis attacks [36, 43] by powerful adversaries such as an authoritarian government or a state controlled ISP, and have recently been attacked by even weaker adversaries monitoring only the users’ traffic [14, 32, 39, 51].”
Tor: The Second-Generation Onion Router
Dingledine, R., Mathewson, N., & Syverson, P. (2004) · doi:10.21236/ada465464 · Cited by 4,104 · cited 1×
“The right to remain anonymous is a fundamental right in a democratic society and is crucial for freedom of speech [49].”
Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
Keying Hash Functions for Message Authentication
Bellare, M., Canetti, R., & Krawczyk, H. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_1 · Cited by 1,580 · cited 1×
“A client only uploads a ciphertext of layered authenticated encryption of size b + mλ, where b is the size of the message, m is the number of servers, and λ is the size of the message authentication codes (MACs) [8] used with the authenticated encryption [9].”
MethodThe dining cryptographers problem: Unconditional sender and recipient untraceability
Chaum, D. (1988) · Journal of Cryptology · doi:10.1007/bf00206326 · Cited by 1,408 · cited 1×
“In this section, we describe related work, focusing on the trade-offs made by existing anonymity systems.”
BackgroundWallet Databases with Observers
Chaum, D., & Pedersen, T. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_7 · Cited by 1,292 · cited 2×
“We used ElGamal encryption using Curve25519 [11] and Neff’s shuffle [37] with Chaum-Pederson proofs [17] for the verifiable shuffle and decryption.”
MethodProbabilistic encryption & how to play mental poker keeping secret all partial information
Goldwasser, S., & Micali, S. (1982) · Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 · doi:10.1145/800070.802212 · Cited by 883 · cited 1×
“To show zero-knowledge, let us assume that the encryption scheme is semantically secure [31], as assumed by [9].”
BackgroundAuthenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm
Bellare, M., & Namprempre, C. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-44448-3_41 · Cited by 879
Curve25519: New Diffie-Hellman speed records
Bernstein, D. J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11745853_14 · Cited by 859 · cited 1×
“We used ElGamal encryption using Curve25519 [11] and Neff’s shuffle [37] with Chaum-Pederson proofs [17] for the verifiable shuffle and decryption.”
The Bittorrent P2P File-Sharing System: Measurements and Analysis
Pouwelse, J., Garbacki, P., Epema, D., & Sips, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/11558989_19 · Cited by 760 · cited 1×
“From the pool, each client chose one file to request and one file to share, and each file was divided into 256KB blocks, similar to BitTorrent’s typical block size [42].”
MethodNew Directions in Cryptography
Diffie, W., & Hellman, M. E. (2022) · Democratizing Cryptography · doi:10.1145/3549993.3550007 · Cited by 668 · cited 1×
“During the setup phase, the clients share three sets of pairwise secrets with the servers: (1) {kij} using a verifiable shuffle (used in the hybrid shuffle), and (2) {mij} and (3) {sij} using simpler methods like Diffie-Hellman [25] (used in the PIR).”
MethodTarzan: a peer-to-peer anonymizing network layer
Freedman, M. J., & Morris, R. (2002) · Proceedings of the 9th ACM conference on Computer and communications security · doi:10.1145/586110.586137 · Cited by 663
Mixminion: design of a type III anonymous remailer protocol
Danezis, G., Dingledine, R., & Mathewson, N. (2004) · Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405) · doi:10.1109/secpri.2003.1199323 · Cited by 658
Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm
Bellare, M., & Namprempre, C. (2008) · Journal of Cryptology · doi:10.1007/s00145-008-9026-x · Cited by 652 · cited 3×
“To show verifiability, let us assume that the authenticated encryption used by Riffle is secure against forgery, following the proposal of [9].”
Low-Cost Traffic Analysis of Tor
Murdoch, S. J., & Danezis, G. (2005) · 2005 IEEE Symposium on Security and Privacy (S&P'05) · doi:10.1109/sp.2005.12 · Cited by 517 · cited 1×
“…popularity as a practical privacy enhancing technology among users seeking *Corresponding Author: Albert Kwon: MIT, E-mail: kwonal@mit.edu David Lazar: MIT, E-mail: lazard@mit.edu Srinivas Devadas: MIT, E-mail: devadas@mit.edu Bryan Ford: EPFL, E-mail: bryan.ford@epfl.ch higher levels of privacy.”
BackgroundA verifiable secret shuffle and its application to e-voting
Neff, C. A. (2001) · Proceedings of the 8th ACM conference on Computer and Communications Security · doi:10.1145/501983.502000 · Cited by 513 · cited 1×
“Tor [26] is a popular anonymity system that focuses on scalability and low latency by routing users’ messages through decentralized volunteer relays without delays or cover traffic.”
BackgroundWebsite fingerprinting in onion routing based anonymization networks
Panchenko, A., Niessen, L., Zinnen, A., & Engel, T. (2011) · Proceedings of the 10th annual ACM workshop on Privacy in the electronic society · doi:10.1145/2046556.2046570 · Cited by 501 · cited 1×
“However, such systems are susceptible to traffic analysis attacks [36, 43] by powerful adversaries such as an authoritarian government or a state controlled ISP, and have recently been attacked by even weaker adversaries monitoring only the users’ traffic [14, 32, 39, 51].”
BackgroundHerrmann, D., Wendolsky, R., & Federrath, H. (2009) · Proceedings of the 2009 ACM workshop on Cloud computing security · doi:10.1145/1655008.1655013 · Cited by 424 · cited 1×
“However, such systems are susceptible to traffic analysis attacks [36, 43] by powerful adversaries such as an authoritarian government or a state controlled ISP, and have recently been attacked by even weaker adversaries monitoring only the users’ traffic [14, 32, 39, 51].”
Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems
Raymond, J.-F. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44702-4_2 · Cited by 422 · cited 2×
“Anonymizing networks based on relays such as Tor [26] have been gaining popularity as a practical privacy enhancing technology among users seeking *Corresponding Author: Albert Kwon: MIT, E-mail: kwonal@mit.edu David Lazar: MIT, E-mail: lazard@mit.edu Srinivas Devadas: MIT, E-mail: devadas@mit.edu Bryan Ford: EPFL, E-…”
BackgroundTouching from a distance: website fingerprinting attacks and defenses
Cai, X., Zhang, X. C., Joshi, B., & Johnson, R. (2012) · Proceedings of the 2012 ACM conference on Computer and communications security · doi:10.1145/2382196.2382260 · Cited by 394 · cited 1×
“However, such systems are susceptible to traffic analysis attacks [36, 43] by powerful adversaries such as an authoritarian government or a state controlled ISP, and have recently been attacked by even weaker adversaries monitoring only the users’ traffic [14, 32, 39, 51].”
The Poly1305-AES Message-Authentication Code
Bernstein, D. J. (2005) · Lecture Notes in Computer Science · doi:10.1007/11502760_3 · Cited by 362 · cited 1×
“For authenticated encryption, we use Go’s Secretbox implementation [4, 5], which internally uses Salsa20 [12] for encryption and Poly1305 [10] for authentication.”
Introducing MorphMix: peer-to-peer based anonymous Internet usage with collusion detection
Rennhard, M., & Plattner, B. (2002) · Proceedings of the 2002 ACM workshop on Privacy in the Electronic Society · doi:10.1145/644527.644537 · Cited by 306
Improved website fingerprinting on Tor
Wang, T., & Goldberg, I. (2013) · Proceedings of the 12th ACM workshop on Workshop on privacy in the electronic society · doi:10.1145/2517840.2517851 · Cited by 295 · cited 1×
“However, such systems are susceptible to traffic analysis attacks [36, 43] by powerful adversaries such as an authoritarian government or a state controlled ISP, and have recently been attacked by even weaker adversaries monitoring only the users’ traffic [14, 32, 39, 51].”
BackgroundAnonymous Web transactions with Crowds
Reiter, M. K., & Rubin, A. D. (1999) · Communications of the ACM · doi:10.1145/293411.293778 · Cited by 286
Computationally private information retrieval (extended abstract)
Chor, B., & Gilboa, N. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258609 · Cited by 249 · cited 1×
“Aqua [34] aims to provide low-latency and highbandwidth anonymity with traffic analysis resistance by using Tor-like infrastructure with mixes.”
BackgroundProof systems for general statements about discrete logarithms
Camenisch, J. L., & Stadler, M. A. (1997) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-a-006651937 · Cited by 220 · cited 1×
“We can use zero-knowledge proof-of-knowledge [15] for 1, and Chaum-Pedersen proof [17] for 2.”
Herbivore: A Scalable and Efficient Protocol for Anonymous Communication
Goel, S., Robson, M., Polte, M., & Sirer, E. G. (2003) · eCommons (Cornell University) · Cited by 210
Distributed Point Functions and Their Applications
Gilboa, N., & Ishai, Y. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-55220-5_35 · Cited by 205 · cited 1×
“Aqua [34] aims to provide low-latency and highbandwidth anonymity with traffic analysis resistance by using Tor-like infrastructure with mixes.”
BackgroundAn Efficient Scheme for Proving a Shuffle
Furukawa, J., & Sako, K. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_22 · Cited by 199 · cited 1×
“Tor [26] is a popular anonymity system that focuses on scalability and low latency by routing users’ messages through decentralized volunteer relays without delays or cover traffic.”
BackgroundEfficient Zero-Knowledge Argument for Correctness of a Shuffle
Bayer, S., & Groth, J. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_17 · Cited by 193 · cited 1×
“Tor [26] is a popular anonymity system that focuses on scalability and low latency by routing users’ messages through decentralized volunteer relays without delays or cover traffic.”
BackgroundCircuit fingerprinting attacks: passive deanonymization of tor hidden services
Kwon, A., AlSabah, M., Lazar, D., Daciér, M., & Devadas, S. (2015) · USENIX Security Symposium · Cited by 192
Self-citationDissent: accountable anonymous group messaging
Corrigan-Gibbs, H., & Ford, B. (2010) · Proceedings of the 17th ACM conference on Computer and communications security · doi:10.1145/1866307.1866346 · Cited by 190 · cited 1×
“In this section, we describe related work, focusing on the trade-offs made by existing anonymity systems.”
BackgroundSelf-citationOn the Computational Practicality of Private Information Retrieval
Sion, R., & Cărbunar, B. (2006) · Cited by 171
Practical Traffic Analysis: Extending and Resisting Statistical Disclosure
Mathewson, N., & Dingledine, R. (2005) · Lecture Notes in Computer Science · doi:10.1007/11423409_2 · Cited by 166 · cited 1×
“A powerful adversary monitoring clients and network over longer periods of time can correlate the presence of some messages with the online status of the clients [35].”
BackgroundDissent in numbers: making strong anonymity scale
Wolinsky, D. I., Corrigan-Gibbs, H., Ford, B., & Johnson, A. (2012) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5555/2387880.2387898 · Cited by 162
Self-citationWaidner, M., & Pfitzmann, B. (2007) · Springer eBooks · doi:10.1007/3-540-46885-4_69 · Cited by 139
Breaking an efficient anonymous channel
Pfitzmann, B. (1995) · Lecture notes in computer science · doi:10.1007/bfb0053448 · Cited by 120 · cited 1×
“The second is verifiable mixnets, based on mix networks [18].”
BackgroundHow to Break the Direct RSA-Implementation of Mixes
Pfitzmann, B., & Pfitzmann, A. (2007) · Springer eBooks · doi:10.1007/3-540-46885-4_37 · Cited by 115 · cited 1×
“The second is verifiable mixnets, based on mix networks [18].”
Riposte: An Anonymous Messaging System Handling Millions of Users
Corrigan-Gibbs, H., Boneh, D., & Mazières, D. (2015) · Cited by 106
Efficient anonymity-preserving data collection
Brickell, J., & Shmatikov, V. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150415 · Cited by 93 · cited 1×
“Tor [26] is a popular anonymity system that focuses on scalability and low latency by routing users’ messages through decentralized volunteer relays without delays or cover traffic.”
BackgroundAl Teich, M. S. F. (1999) · The Information Society · doi:10.1080/019722499128538 · Cited by 70 · cited 1×
“The right to remain anonymous is a fundamental right in a democratic society and is crucial for freedom of speech [49].”
BackgroundProactively Accountable Anonymous Messaging in Verdict
Corrigan-Gibbs, H., Wolinsky, D. I., & Ford, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.4819 · Cited by 68 · cited 1×
“In this section, we describe related work, focusing on the trade-offs made by existing anonymity systems.”
BackgroundSelf-citationUntraceable Electronic Mail, Return Addresses and Digital Pseudonyms
Chaum, D. (2003) · Advances in information security · doi:10.1007/978-1-4615-0239-5_14 · Cited by 65
Five Practical Attacks for “Optimistic Mixing for Exit-Polls”
Wikström, D. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24654-1_12 · Cited by 55
Sassaman, L., Cohen, B., & Mathewson, N. (2005) · ACM Workshop on Privacy in the Electronic Society (WPES) · doi:10.1145/1102199.1102201 · Cited by 54
A verifiable secret shuffle and its application to e-voting
Neff, C. A. (2001) · Proceedings of the ACM Conference on Computer and Communications Security · doi:10.1145/501997.502000 · Cited by 53
Towards efficient traffic-analysis resistant anonymity networks
Blond, S. L., Choffnes, D., Zhou, W., Druschel, P., Ballani, H., & Francis, P. (2013) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/2486001.2486002 · Cited by 46 · cited 1×
“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.”
Sirer, E. G., Goel, S., Robson, M., & Engin, D. (2004) · ACM SIGOPS European Workshop · doi:10.1145/1133572.1133611 · Cited by 37 · cited 2×
“Previous works [30, 48] have explored these problems in detail, and their solutions are applicable to Riffle as well.”
Hang With Your Buddies to Resist Intersection Attacks
Wolinsky, D. I., Syta, E., & Ford, B. (2013) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 33
Self-citationTowards efficient traffic-analysis resistant anonymity networks
Blond, S. L., Choffnes, D., Zhou, W., Druschel, P., Ballani, H., & Francis, P. (2013) · ACM SIGCOMM Computer Communication Review · doi:10.1145/2534169.2486002 · Cited by 28
Breaking and Mending Resilient Mix-Nets
Nguyen, L. D., & Safavi–Naini, R. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-40956-4_5 · Cited by 23 · cited 1×
“The second is verifiable mixnets, based on mix networks [18].”
BackgroundBlake, I. F. (2024) · Cambridge University Press eBooks · doi:10.1017/9781009283403.010 · Cited by 14
Research works printed but not linked: 2
- [11]11. D. J. Bernstein. New stream cipher designs. chapter The Salsa20 Family of Stream Ciphers, pages 84-97. Springer- Verlag, Berlin, Heidelberg, 2008.
- [19]19. B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Pri- vate information retrieval. J. ACM, 45(6):965-981, Nov. 1998.
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Decentralization in Bitcoin and Ethereum Networks
Gencer, A. E., Basu, S., Eyal, I., van Renesse, R., & Sirer, E. G. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-58387-6_24 · Cited by 374
Distributed Differential Privacy via Shuffling
Cheu, A., Smith, A., Ullman, J., Zeber, D., & Zhilyaev, M. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-17653-2_13 · Cited by 268
“, [22, 5] and citations therein).”
PIR with Compressed Queries and Amortized Query Processing
Angel, S., Chen, H., Laine, K., & Setty, S. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00062 · Cited by 251
SPIRAL: Fast, High-Rate Single-Server PIR via FHE Composition
Menon, S. J., & Wu, D. J. (2022) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46214.2022.9833700 · Cited by 175
Metadata
- Authors
- Kwon, A., Lazar, D., Devadas, S., & Ford, B.
- Affiliations
- Massachusetts Institute of Technology (US)
- École Polytechnique Fédérale de Lausanne (CH)
- Venue
- Proceedings on Privacy Enhancing Technologies
- Published
- 2015-12-30
- Volume
- 2016
- Issue
- 2
- Pages
- 115-134
- ISSN
- 2299-0984 (ISSN-L)
- OpenAlex
- W2211872228
- Cited by
- 84
- References
- 56
- Citations by year
- 2026: 6 · 2025: 6 · 2024: 10 · 2023: 5 · 2022: 13 · 2021: 9 · 2020: 11 · 2019: 6 · 2018: 9 · 2017: 5 · 2016: 3 · 2015: 1
- FWCI
- 5.89
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Proceedings on Privacy Enhancing Technologies (publishedVersion, cc-by-nc-nd)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-nd)
- Infoscience (Ecole Polytechnique Fédérale de Lausanne) (submittedVersion, cc-by-nc-nd)
- Funders
- National Science Foundation (1413920)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Internet Traffic Analysis and Secure E-voting
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Authentication Protocols Security
- Keywords
- anonymous communication, private information retrieval, traffic analysis attacks, onion routing, spectral efficiency, computational efficiency, file sharing, microblogging, riffles
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.