Introduction
In privacy-preserving messaging systems and blockchains like Zcash, recipients face a significant "discovery" challenge. Since messages lack public metadata identifying the recipient, users must traditionally download and attempt to decrypt every message on the network to find those intended for them. This process is computationally expensive and prohibitive for mobile devices. Oblivious Message Retrieval (OMR) was introduced to delegate this task to an untrusted server. Using Homomorphic Encryption (HE), the server scans a message board and returns a compact "digest" of relevant messages without learning the recipient's identity or the contents of the messages.
The Latency Bottleneck in Prior OMR
Existing OMR protocols, such as SophOMR, primarily utilize the BFV encryption scheme. While BFV is efficient for processing large batches of data, it suffers from high "startup latency." Even for a single message, the homomorphic operations can take over 70 seconds. This batch-heavy approach prevents real-time notifications and limits the effectiveness of parallel processing across modern multi-core CPUs, as the server must wait for a full batch to accumulate before processing begins.
InstantOMR: A Hybrid Streaming Architecture
InstantOMR addresses these limitations by shifting from a batch-oriented design to a streaming-capable, hybrid cryptographic architecture. The system utilizes TFHE (Torus Fully Homomorphic Encryption) for the detection phase and RLWE (Ring Learning With Errors) for the encoding phase.
As illustrated in the figure above, the retrieval process (Step 3) is divided into three distinct sub-steps:
- Step 3a: Homomorphic Decryption: The detector uses TFHE to decrypt the "clue" attached to each message. TFHE's functional bootstrapping allows for fast evaluation of individual ciphertexts.
- Step 3b: Homomorphic Checking: The system checks if the decrypted clue matches the recipient's identity.
- Step 3c: Homomorphic Encoding: To efficiently return the results, the TFHE ciphertexts are converted into RLWE ciphertexts. This allows the server to use SIMD-like operations to pack multiple message payloads into a single digest.
Because each message is processed independently, InstantOMR enables a "streaming" workflow where the server processes messages as they arrive on the board, rather than waiting for a user request.
Performance and Parallelizability
InstantOMR achieves near-optimal parallelizability. Unlike BFV-based schemes where batching constraints limit scaling, InstantOMR can distribute message processing across any number of CPU cores with minimal overhead.
Key results include:
- Latency Reduction: InstantOMR reduces the latency for retrieving a single message from ~76 seconds (SophOMR) to just 88 milliseconds—a nearly 900x improvement.
- Real-Time Retrieval: For a user coming online after a period of absence, the waiting time for message retrieval is reduced to less than 0.1 seconds in a streaming configuration.
- Scaling: On an 180-core server, InstantOMR processes a board of $2^{16}$ messages approximately 3x faster than previous state-of-the-art methods.
Conclusion and Future Work
InstantOMR represents a paradigm shift in OMR by prioritizing user-perceived latency over amortized throughput. While it requires more total computational power per message than BFV-based schemes, its ability to provide instant feedback makes it far more practical for real-world applications. Future research will focus on reducing the size of the returned digest and exploring hardware acceleration to further improve single-core throughput.
Summary updated