Orca: Blocklisting in Sender-Anonymous Messaging


Nirvan Tyagi and Julia Len, Cornell University; Ian Miers, University of Maryland; Thomas Ristenpart, Cornell Tech


Sender-anonymous end-to-end encrypted messaging allows sending messages to a recipient without revealing the sender's identity to the messaging platform. Signal recently introduced a sender anonymity feature that includes an abuse mitigation mechanism meant to allow the platform to block malicious senders on behalf of a recipient.

We explore the tension between sender anonymity and abuse mitigation. We start by showing limitations of Signal's deployed mechanism, observing that it results in relatively weak anonymity properties and showing a new griefing attack that allows a malicious sender to drain a victim's battery. We therefore design a new protocol, called Orca, that allows recipients to register a privacy-preserving blocklist with the platform. Without learning the sender's identity, the platform can check that the sender is not on the blocklist and that the sender can be identified by the recipient. We construct Orca using a new type of group signature scheme, for which we give formal security notions. Our prototype implementation showcases Orca's practicality.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {277116,
author = {Nirvan Tyagi and Julia Len and Ian Miers and Thomas Ristenpart},
title = {Orca: Blocklisting in {Sender-Anonymous} Messaging},
booktitle = {31st USENIX Security Symposium (USENIX Security 22)},
year = {2022},
isbn = {978-1-939133-31-1},
address = {Boston, MA},
pages = {2299--2316},
url = {https://www.usenix.org/conference/usenixsecurity22/presentation/tyagi},
publisher = {USENIX Association},
month = aug,

Presentation Video