Haofei Liang, Shanghai Jiao Tong University; Zeyu Liu, Yale University; Eran Tromer, Boston University; Xiang Xie, Primus Labs; Yu Yu, Shanghai Jiao Tong University
Oblivious message retrieval (OMR) addresses the expensive message retrieval process in anonymous messaging systems and private blockchains. It enables resource-limited recipients to outsource detection and retrieval of their messages, while preserving privacy.
This work introduces InstantOMR, a novel OMR scheme that combines TFHE functional bootstrapping with standard RLWE operations in a hybrid design. InstantOMR is specifically optimized for low latency and high parallelizability. Our implementation, using the Primus-fhe library (and estimates based on TFHE-rs), demonstrates that InstantOMR offers the following key advantages:
- Low latency: InstantOMR achieves \sim 600× lower latency than SophOMR, the state-of-the-art single-server OMR. This translates directly into reduced recipient waiting time (by the same factor) in the streaming setting, where the detector processes incoming messages on-the-fly and returns a digest immediately upon the recipient becoming online.
- Optimal parallelizability: InstantOMR scales near-optimally with available CPU cores (by processing messages independently), so for high core counts it is faster than SophOMR (whose parallelism is constrained by reliance on BFV).
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.
