Cryptology ePrint Archive: Report 2021/1380

Orca: Blocklisting in Sender-Anonymous Messaging

Nirvan Tyagi and Julia Len and Ian Miers and Thomas Ristenpart

Abstract: 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.

Category / Keywords: cryptographic protocols / end-to-end encrypted messaging, group signatures, keyed-verification anonymous credentials, anonymous blacklisting

Original Publication (with major differences): Usenix Security 2022

Date: received 12 Oct 2021

Contact author: nirvan tyagi at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211015:082201 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]