SophOMR: Improved Oblivious Message Retrieval from SIMD-Aware Homomorphic Compression

Privacy-preserving blockchains and private messaging services that ensure receiver-privacy face a significant UX challenge: each client must scan every payload posted on the public bulletin board to avoid missing messages intended for them. Oblivious Message Retrieval (OMR) addresses this issue by securely outsourcing this expensive scanning process to a service provider using Homomorphic Encryption (HE). In this work, we propose a new OMR scheme that substantially improves upon the previous state-of-the-art, PerfOMR (USENIX Security'24). Our implementation demonstrates reductions of 3.4x in runtime, 2.2x in digest size, and 1.5x in key size, in a scenario with 65536 payloads (each 612 bytes), of which up to 50 are pertinent. At the core of these improvements is a new homomorphic compression mechanism, where ciphertexts of length proportional to the number of total payloads are compressed into a digest whose length is proportional to the upper bound on the number of pertinent payloads. Unlike previous approaches, our scheme fully exploits the native homomorphic SIMD structure of the underlying HE scheme, significantly enhancing efficiency. In the setting described above, our compression scheme achieves 7.5x speedup compared to PerfOMR. * Equal contribution. 1 https://www.propublica.org/article/how-facebook-undermi nes-privacy-protections-for-its-2-billion-whatsapp-users 2 https://www.forbes.com/sites/thomasbrewster/2022/02/23 /meet-the-secretive-surveillance-wizards-helping-the-fbi-a nd-ice-wiretap-facebook-and-google-users/ * N: # of payloads * n: BFV ring dimension * t: # of BFV slots per payload * k: # of pertinent payloads * p: BFV plaintext modulus * 2 -ν : false negative probability