USENIX Security 26 - Oblivious Signaling @UsenixOrg
USENIX Security 26 - Oblivious Signaling  @UsenixOrg
Uploaded October 2026 | Updated November 2026, 3 days ago
USENIX Security '26 - Oblivious Signaling

Mirza Kamrul Bashar Shuhan, George Mason University; Foteini Baldimtsi, George Mason University & Mysten Labs; Giuseppe Ateniese, George Mason University

An anonymous messaging service has to solve a basic routing problem: a server must deliver an encrypted message to its recipient without learning who the recipient is. Broadcasting all ciphertexts hides the destination but forces every recipient to constantly scan for new messages. Oblivious Message Retrieval (OMR; CRYPTO~'22) tackles this by using fully homomorphic encryption (FHE) to let an untrusted server perform message retrieval on a recipient's behalf without learning which messages are pertinent.
We introduce Oblivious Signaling, which shifts this cost from retrieval to sending. The server maintains a fixed-size encrypted inbox for each recipient. When a sender submits a message, the server applies the same homomorphic update to every inbox: the intended inbox absorbs the message, and the rest remain unchanged at the plaintext level. The update is uniform, can be parallelized across inboxes, and ties the delivery cost strictly to the size of the anonymity set rather than global traffic. Recipients retrieve by fetching and decrypting their inbox, so checking for new messages is independent of the global traffic.
We formalize receiver privacy against an untrusted server, even when it colludes with other users, give a concrete construction based on fully homomorphic encryption, and analyze the resulting ``digital postage'' trade-off: delivery is expensive, but checking is cheap. Our prototype identifies practical regimes in which this cost-model shift is preferable to scan-based retrieval, even with highly optimized OMR implementations. This cost model is well-suited to settings where recipients check frequently, and messages arrive sporadically, and it naturally discourages high-volume spam.

View the full USENIX Security '26 program at usenix.org/conference/usenixsecurity26/technical-sessions
USENIX Security 26 - Oblivious SignalingSREcon26 Europe/Middle East/Africa - Three Lies We Tell Ourselves about Disaster Recovery and...USENIX Security 26 - Health Hazard, Handle with Care: Investigating the Privacy Risks of Androids…WOOT 26 - DisARMed: Attacking ARM TrustZone from Userspace with Memory AliasingSREcon26 Europe/Middle East/Africa - The Future of OperationsWOOT 26 - SoK: Multi-Layer Indirect Call Analysis in the Real WorldUSENIX Security 26 - An Integer Overflow Endgame: Compiler and Architecture Support for Default-On…VehicleSec 26 - E-Trojans: Ransomware, Tracking, DoS, and Data Leaks on the Xiaomi E-Scooter...WOOT 26 - Keynote Address: Click Here to Hack Your Target: A Perspective on the Past...WOOT 26 - CATana: On the Dangers of SIM-Originating AT CommandsUSENIX Security 26 - Distributed Synthesis of Differentially Private Tabular DatasetsVehicleSec 26 - Perspective-Shift Attacks Against Optical Perception Sensors: A Novel Attack...
USENIX |

USENIX Security '26 - Oblivious Signaling

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER