Oblivious Message Retrieval
Last updated
Last updated
Anonymous messaging systems, such as private messaging services and privacy-preserving payment platforms, face the challenge of enabling recipients to retrieve messages without revealing metadata or allowing the messages to be linked back to them. The core issue is ensuring that the process of message retrieval does not expose identifying information or communication patterns.
A simple, yet inefficient, solution is for recipients to download all messages and scan them individually for those addressed to them. While this method protects privacy, it leads to significant communication and computation overhead, especially as the system scales. This approach becomes impractical with a large user base, resulting in network congestion and heavy processing demands on users’ devices.
To address these challenges, Oblivious Message Retrieval (OMR), proposed by Ziyu and Eran, is a cryptographic protocol designed to prevent privacy leakage during message retrieval.
In private blockchains like Zcash, transaction contents are hidden from everyone except the parties involved, using encryption and zero-knowledge proofs. However, Zcash’s current lightwallet architecture faces several issues, including:
Performance bottlenecks for wallet users.
Metadata privacy leaks when using services like lightwalletd.
Inefficient data retrieval, as downloading all transactions is impractical due to the blockchain's growing size, which leads to high bandwidth and computation costs.
Currently, Zcash light wallets must perform trial decryption for each shielded transaction, which is computationally expensive and requires additional data from lightwalletd, exposing metadata in the process.
OMR, combined with Fully Homomorphic Encryption (FHE), can enhance metadata privacy in private blockchains by enabling efficient and private message retrieval.
In a Zcash implementation utilizing OMR, the process may work as follows:
A user generates a Zcash address that includes a new clue key, PVW.pk.
The sender creates a shielded transaction along with a clue ciphertext, which is an encryption of a vector of 0s using the recipient's clue key PVW.pk. This adds about 1KB of data per shielded transaction.
To detect and receive relevant transactions, the recipient generates a detection key and registers it with a Zcash full node that supports OMR. The full node uses the detection key to scan all shielded transactions and their attached clue ciphertexts.
The node performs homomorphic operations on all transactions, using the detection key to try to decrypt the clue ciphertexts attached to the shielded transactions. The decryption key is a BFV encryption of the clue private key PVW.sk.
If a transaction is relevant, the homomorphic decryption outputs a Pertinency Vector (PV), which encrypts a vector of 0s. If the transaction is not relevant, the PV will encrypt random bits.
The user can then use the bit vector PV to retrieve the pertinent transaction's message digest.
In this OMR protocol, two homomorphic encryption schemes are used:
PVW encryption: This is used by the sender to encrypt the clue for the recipient.
BFV encryption: Used to homomorphically decrypt clues and generate pertinency ciphertexts.
This process of switching between encryption schemes is known as transciphering, enabling efficient and secure message retrieval without exposing sensitive metadata.
4o
