2nd Anonymity Day workshop | Cybersecurity Center

Anonymity Days is a workshop series for disseminating recent advances in anonymity research. It will occur twice a year at Brown University, Tufts University, or Columbia University, rotating between the three venues. Our target audience is theory and security researchers/graduate students interested in sharing and learning the newest anonymity results, but everyone is welcome! If you plan to register, register below (free).

Location: Tisch Library, Room 304
Date and Time: Nov 15, 9:45am to 5pm

Register Now (Free)

Agenda:

9:45-10:00 | Opening remarks: Megumi Ando & Susan Landau (Tufts University)
10-11:15 | "XRD: Scalable Messaging System with Cryptographic Privacy" by Albert Kwon (Badge Inc.)
11:15-12:30 | Talk: Kashvi Gupta (Columbia University)
12:30-2:00 | Lunch: with a discussion led by Nick Mathewson on Tor v. What Can be Proved
2:00-3:15 | "Oblivious Message Retrieval" by Eran Tromer (Boston University)
3:15-4:30 | "Robust and Scalable Metadata-private Anonymous Broadcast" by Sacha Servan-Schreiber (MIT)

Abstracts:

"XRD: Scalable Messaging System with Cryptographic Privacy" by Albert Kwon (Badge Inc.)

In this talk, Kwon will present XRD (Crossroads), a metadata private messaging system that provides cryptographic privacy, while scaling easily to support more users by adding more servers. XRD protects all communication metadata, in particular who is talking with whom, using multiple mix networks in parallel. To achieve our privacy goals without incurring large performance penalties, we introduce a novel technique to efficiently and privately verify the correctness of mix network operations called aggregate hybrid shuffle (AHS). AHS provides guarantees similar to traditional verifiable shuffle in our setting, but requires significantly less exponentiation operations than prior verifiable shuffles, which in turn reduces the overall latency of a verifiable mix network. With 100 servers, we found that XRD could support 2 million users with 228s of latency.

"Oblivious Message Retrieval" by Eran Tromer (Boston University)

Anonymous message delivery systems, such as private messaging services and privacy-preserving blockchains, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale.

We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding. This generalizes to the setting of group messaging or mailing lists: senders can generate messages that would be efficiently detected by multiple recipients of their choice.

Our approach is based on homomorphic encryption and sparse random linear codes, and achieves practical efficiency using bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations.

(Covers joint works Zeyu Liu, Katerina Sotiraki and Yunhao Wang.)

"Robust and Scalable Metadata-private Anonymous Broadcast" by Sacha Servan-Schreiber (MIT)

In this talk, Servan-Schreiber will present Trellis: 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.

Servan-Schreiber aims to 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.

Organizers:

Megumi Ando (Tufts University)
Anna Lysyanskaya (Brown University)
Tal Malkin (Columbia University)
Eli Upfal (Brown University)

This workshop has been supported by NSF grants CCF-2312241, CCF-2312242, and CCF-2312243 and the Tufts Cybersecurity Center for the Public Good.