Sabre: Sender-Anonymous Messaging with Fast Audits

We present Sabre, a family of sender-anonymous messaging protocols with instances supporting both Twitter-like anonymous bulletin boards and Secure Drop-like mailboxes. Both variants provide strong anonymity while potentially scaling to anonymity sets in the tens of millions and beyond. Sabre protocols inherit their basic structure from Riposte and Express while replacing those schemes’ linear-cost audit protocols with new logarithmic-cost ones. Sabre also incorporates a host of innovations that improve concrete performance by an order of magnitude or more under “ideal” circumstances, while providing asymptotic speedups in the face of resource exhaustion-style DoS attacks.