Oblivious Message Retrieval

Anonymous message delivery systems, such as private messaging services and privacy-preserving payment systems, require a method for recipients to retrieve their messages without revealing metadata or allowing messages to be linked back to them. The challenge lies in ensuring that the process of retrieving messages does not expose any identifying information or communication patterns.

One naive solution is for recipients to download all posted messages and individually scan for those addressed to them. While this method maintains privacy, it is highly inefficient, resulting in excessive communication and computation costs, particularly as the system scales up. This approach would quickly become impractical with a large number of users and messages, leading to significant network congestion and high processing demands on each recipient's device.

Oblivious message retrieval (OMR), proposed by Ziyu and Eran in their paper, is a cryptographic protocol that can address such privacy leakages.

Using OMR in a Private Blockchain

A private blockchain like Zcash, keeps the contents of every transaction hidden from all but the counterparties to the transaction, using cryptographic protocols utilizing encryption and zero-knowledge proofs. However, the current Zcash lightwallet architecture faces several challenges: performance issues for wallet users, privacy leaks through metadata exposure when using lightwalletd, and inefficiencies in data retrieval. Downloading all transactions to maintain privacy is impractical due to large blockchain sizes, leading to high bandwidth and computational costs. Light wallets perform computationally intensive trial decryption for each shielded transaction and require additional data from lightwalletd to construct new transactions, further exposing metadata.

OMR can improve the metadata privacy of a private blockchain by combining it with fully homomorphic encryptions (FHE).

alt text

At a high level, this is how a Zcash implementation featuring OMR might operate.

A user generates a Zcash address that includes a new clue key PVW.pk.
The sender creates a shielded transaction, plus a clue ciphertext, which is an encryption to a vector of 0s with the recipient's clue key PVM.pk. Note in practice, the size is about 1KB of additional data per shielded output.
To detect and receive any pertaining transactions, the user generates a detection key and registers that with an OMR-supporting Zcash full node. The node uses that detection key to scan all the shielded transactions on the chain and their attached clue ciphertexts. The scanning involves taking all the transactions, including the clue ciphertexts, and fully-homomorphically, trying to use the detection key to decrypt the clue ciphertexts associated with the shielded transactions.
- Note the decryption key is a BFV encryption of the clue private key PVW.sk, and such a homomorphic decryption will output a result that is an encryption of a bit vector (a Pertinency Vector) PV, for which if this transaction is pertinent to this recipient, then PV will encrypt of 0s, and if the transaction is impertinent, then PV will encrypt of random bits.
- By linearly operating the bit vector PV with all the transaction payloads, the resulting message digest will be retrieved by the user.
- The user decrypts the digest to get the plain payload of all the pertaining transactions.

Both PVW and BFV are homomorphic encryption schemes used in the OMR protocol, where the sender encrypts the clue using PVW scheme and clues are decrypted homomorphically to generate pertinency ciphertexts using BFV scheme. This technique of switching encryption scheme is generally known as transciphering.