Sabre: Sender-Anonymous Messaging with Fast Audits
Published in IEEE Symposium on Security and Privacy (SP), 2022
This paper presents 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.