Paper 2021/1380

Orca: Blocklisting in Sender-Anonymous Messaging

Nirvan Tyagi, Julia Len, Ian Miers, and Thomas Ristenpart


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Usenix Security 2022
end-to-end encrypted messaginggroup signatureskeyed-verification anonymous credentialsanonymous blacklisting
Contact author(s)
nirvan tyagi @ gmail com
2021-10-15: received
Short URL
Creative Commons Attribution


      author = {Nirvan Tyagi and Julia Len and Ian Miers and Thomas Ristenpart},
      title = {Orca: Blocklisting in Sender-Anonymous Messaging},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1380},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.