Paper 2022/1548

Trellis: Robust and Scalable Metadata-private Anonymous Broadcast

Simon Langowski, Massachusetts Institute of Technology
Sacha Servan-Schreiber, Massachusetts Institute of Technology
Srinivas Devadas, Massachusetts Institute of Technology

Trellis is a mix-net based anonymous broadcast system with cryptographic security guarantees. Trellis can be used to anonymously publish documents or communicate with other users, all while assuming full network surveillance. In Trellis, users send messages through a set of servers in successive rounds. The servers mix and post the messages to a public bulletin board, hiding which users sent which messages. Trellis hides all network metadata, remains robust to changing network conditions, guarantees availability to honest users, and scales with the number of mix servers. Trellis provides three to five orders of magnitude faster performance and better network robustness compared to Atom, the state-of-the-art anonymous broadcast system with a comparable threat model. In achieving these guarantees, Trellis contributes: (1) a simpler theoretical mixing analysis for a routing mix network constructed with a fraction of malicious servers, (2) anonymous routing tokens for verifiable random paths, and (3) lightweight blame protocols built on top of onion routing to identify and eliminate malicious parties. We implement and evaluate Trellis in a networked deployment. With 128 servers, Trellis achieves a throughput of 320 bits per second. Trellis’s throughput is only 100 to 1000× slower compared to Tor (which has 6,000 servers and 2 million daily users) and is potentially deployable at a smaller “enterprise” scale. Our implementation is open-source.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Network and Distributed System Security (NDSS) Symposium 2023
Contact author(s)
slangows @ mit edu
3s @ mit edu
devadas @ mit edu
2023-03-21: revised
2022-11-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Simon Langowski and Sacha Servan-Schreiber and Srinivas Devadas},
      title = {Trellis: Robust and Scalable Metadata-private Anonymous Broadcast},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1548},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.