Group Oblivious Message Retrieval

Group Oblivious Message Retrieval

Speakers: Zeyu Liu; Eran Tromer; Yunhao Wang

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=iq7ujQo1sTE

Overview

This talk, "Group Oblivious Message Retrieval," presented by Zeyu Liu and co-authored with Eran Tromer and Yunhao Wang, introduces a novel cryptographic primitive designed to enhance recipient privacy in group messaging and blockchain applications. The core problem addressed is how a recipient can efficiently retrieve messages pertinent to them from a public bulletin board without revealing their identity or which messages they are interested in, especially when messages are intended for multiple recipients.

The research extends the concept of Oblivious Message Retrieval (OMR) to group settings, proposing two distinct models: Ad-hoc Group OMR (AGR) for flexible, dynamically formed groups, and Fixed Group OMR (FGR) for pre-established groups like mailing lists. The significance of this work lies in its ability to provide strong recipient privacy and unlinkability guarantees while maintaining high efficiency, overcoming the severe performance degradation that would result from naively applying existing OMR schemes to group scenarios. This is crucial for resource-constrained clients in applications ranging from secure group chats to privacy-preserving blockchains.

The paper presents innovative technical solutions, including the use of homomorphic encryption for efficient processing of encrypted recipient identifiers and the development of a new lattice-based key-private multi-recipient encryption (MRE) scheme. The proposed constructions achieve substantial performance gains—up to hundreds of times faster than naive approaches for large groups—and incorporate robust defenses against Denial of Service (DoS) attacks. These advancements mark a significant step forward in building privacy-preserving communication systems that are both secure and practically viable for real-world group interactions.

Background

▶ Watch: Introduction to anonymous message retrieval and recipient privacy (0:00)

The motivation for Group Oblivious Message Retrieval (GOMR) stems from the need for recipient privacy in modern messaging and blockchain systems. In these systems, a sender places a payload (e.g., a text message, a coin transfer) onto a public bulletin board—which could be a central database in apps like Signal or WhatsApp, or a public ledger in blockchains like Zcash or Monero. The challenge is for recipients to find messages addressed to them, known as pertinent messages, without revealing their identity or which messages they are interested in.

A trivial solution involves each recipient downloading the entire bulletin board and filtering messages locally. However, this is prohibitively expensive for resource-limited clients. To address this, the concept of Oblivious Message Retrieval (OMR) was introduced in LT22. In an OMR system, the recipient outsources the filtering task to an untrusted third party called a detector. The recipient generates a secret key and derivation of public keys: a clue key and a detection key. The sender uses the clue key to generate a clue which, along with the payload, forms a message appended to the board. The detector, holding the board and the recipient's detection key, processes the messages to form a digest. This digest, significantly smaller than the full board, is sent back to the recipient, who uses their secret key to extract the plaintext pertinent payloads.

OMR schemes typically aim for three key properties:

1. Privacy: The detector learns nothing about which messages are pertinent to the recipient.
2. Unlinkability: The detector cannot link retrieval requests to specific recipients or keys.
3. Efficiency: The digest size should be much smaller than the bulletin board, ideally proportional only to the number of pertinent messages.

The OMR construction in LT22 primarily relies on a PVW public key encryption scheme, a lattice-based public key encryption scheme variant of original Regev scheme. In this scheme, the clue is a PVW ciphertext encrypting '1'. The detector, equipped with an encrypted PVW secret key, performs homomorphic decryption on the clue. Pertinent messages yield encryptions of '1', while impertinent ones yield encryptions of '0'. These binary indicators are then compressed via homomorphic encoding into a small digest.

The natural follow-up question, and the starting point for this research, is: what happens when a sender wants to send a message to multiple recipients? A naive extension of OMR to a group of G recipients would involve the sender generating G individual clues (PVW ciphertexts) for each recipient and attaching them to the payload. This approach, however, forces the detector to process each of the G clues separately for every message on the board. Consequently, the detector's runtime becomes G times slower, rendering it impractical for groups of even moderate size (dozens or hundreds of recipients). This significant efficiency bottleneck underscores the need for a more sophisticated and optimized approach to Group Oblivious Message Retrieval.

Key Findings

▶ Watch: Naive group OMR solution and its efficiency drawbacks (3:00)

The core contribution of this work is the design and implementation of efficient Group Oblivious Message Retrieval (GOMR) schemes that effectively address the challenges of recipient privacy in multi-recipient communication. The key findings and contributions can be summarized as follows:

1. Overcoming G-times Overhead: The primary breakthrough is the complete elimination of the G-times overhead inherent in a naive extension of OMR to G recipients. Instead of processing G individual clues per message, the proposed GOMR constructions allow the detector to perform a constant number of homomorphic operations, drastically reducing processing time.

1. Two Group Models: The research defines and constructs GOMR for two distinct and widely applicable group communication models:

• Ad-hoc Group OMR (AGR): Designed for flexible scenarios where senders can dynamically choose a group of recipients, such as in secure group messaging or privacy-preserving blockchains.
• Fixed Group OMR (FGR): Tailored for pre-established groups like mailing lists or fixed group chats, where recipients pre-form a group and generate a shared group key. This model, due to its tighter constraints, allows for even greater efficiency.

1. Innovative AGR Construction using Encrypted Compressed IDs: For the AGR model, the authors developed a sophisticated technique involving linear interpolation over encrypted compressed IDs. Initially, attempts to use polynomial interpolation on plaintext IDs compromised unlinkability, while homomorphic evaluation of high-degree polynomials on encrypted IDs was prohibitively expensive. The final AGR construction cleverly uses a pseudo-random matrix Zs to compress recipient IDs, then interpolates a linear function (represented by a Matrix M) such that M multiplied by the compressed ID yields the appropriate PVW ciphertext. The detector homomorphically computes this matrix-vector product, requiring only two levels of homomorphic multiplication, which is highly efficient.

1. Novel Lattice-Based Key-Private Multi-Recipient Encryption (MRE) for FGR: For the FGR model, the authors devise the first lattice-based key-private MRE scheme. This new cryptographic primitive allows a sender to encrypt a message for multiple recipients using a single group key, ensuring that the ciphertext does not reveal which public keys were used for its generation (key privacy). By replacing the PVW encryption and OMR steps with this specialized MRE construction, the FGR scheme achieves significantly smaller clue sizes and even faster detector runtime compared to AGR.

1. Robust DoS Protection: The paper rigorously addresses the threat of Denial of Service (DoS) attacks, where a malicious sender crafts clues to make an excessive number of recipients (or non-group members) detect messages as pertinent, potentially causing retrieval failures or overwhelming clients. The proposed AGR and FGR constructions are proven to be resilient against such attacks, preventing a sender from spamming more than G plus a small constant number of recipients in AGR, and preventing spamming of recipients not belonging to the same group in FGR. These security guarantees rely on new "sortable conjectures."

1. Significant Performance Improvements: Empirical evaluations demonstrate that the GOMR constructions achieve substantial practical benefits. The AGR scheme is shown to be nearly G times faster than the naive OMR extension. The FGR scheme exhibits even greater efficiency, with its runtime growing much slower, almost remaining constant even for hundreds of recipients, and featuring a clue size that is almost independent of the group size G. These results extend to very large group sizes, up to thousands of people.

These findings collectively represent a major advancement in practical, privacy-preserving group communication, offering efficient and secure solutions for a wide range of applications that require recipient privacy at scale.

Technical Deep Dive

▶ Watch: Detailed explanation of the LT22 OMR construction (3:45)

The technical heart of Group Oblivious Message Retrieval lies in its innovative approach to processing multiple recipient keys and messages efficiently using homomorphic encryption. Let's first review the underlying OMR (Oblivious Message Retrieval) construction from LT22 and then delve into the evolution of the GOMR designs.

LT22 OMR Construction Overview

In the LT22 OMR scheme, the recipient generates a PVW public key as their clue key and a corresponding secret key. The sender uses this public key to encrypt a constant value, typically '1', which forms the clue. This clue is then attached to the payload. The recipient also provides the detector with a detection key, which contains an encryption of their PVW secret key.

The detector performs the following steps:

1. It streams the bulletin board, encountering various messages and their clues.
2. For each clue (a PVW ciphertext), it performs homomorphic decryption using the encrypted PVW secret key from the detection key.
3. If the clue was generated for the recipient, this homomorphic decryption yields an encryption of '1'. If not, it yields an encryption of '0'.
4. These encrypted binary indicators are then compressed into a small digest using homomorphic encoding.
5. The detector sends this digest to the recipient, who can then locally decrypt it to recover the pertinent payloads.

This process ensures privacy (detector sees only ciphertexts) and unlinkability (detector doesn't know who is decrypting).

Ad-hoc Group OMR (AGR) Construction Evolution

The challenge for AGR is to extend this to G recipients without the G-times overhead. The talk details a progression of ideas:

1. Naive Extension (Inefficient Baseline)

A naive approach for G recipients would be for the sender to generate G separate PVW ciphertexts, one for each recipient using their individual clue keys. The detector would then have to homomorphically decrypt and encode G ciphertexts for every message, making the process G times slower than single-recipient OMR. This is the baseline the paper aims to beat.

2. First Idea: Polynomial Interpolation with Plaintext IDs

To avoid G separate ciphertexts, the first idea was to combine them. Each recipient is assigned an ID in addition to their PVW public key. The sender collects G (ID, PVW ciphertext) pairs and interpolates a polynomial function F such that F(ID_i) equals the PVW ciphertext for recipient i. The coefficients of this polynomial, rather than G individual ciphertexts, become the clue.

The detector, also knowing the recipient's ID, would compute F(ID) in plaintext to obtain the corresponding PVW ciphertext. It would then proceed with the standard homomorphic decryption and encoding steps.

• Benefit: The detector only performs one homomorphic decryption and encoding per message, removing the G-times overhead.
• Problem: The recipient's ID is known to the detector, which immediately breaks unlinkability. The detector knows exactly who is making the retrieval request.

3. Second Idea: Encrypted IDs with Homomorphic Polynomial Evaluation

To restore unlinkability, the recipient's ID is encrypted using a Fully Homomorphic Encryption (FHE) scheme. The detector now homomorphically evaluates F(Enc(ID)).

• Benefit: Unlinkability is restored.
• Problem: This approach introduces two significant performance issues:
• High Multiplicative Depth: The polynomial F has a degree of G-1. Direct homomorphic evaluation of such a high-degree polynomial is very costly in leveled FHE schemes, where runtime increases with multiplicative depth. For G in the dozens or hundreds, this is too slow.
• Large ID Space: To ensure unique IDs for many recipients, the ID space needs to be large (e.g., 128-bit finite field). Current FHE schemes struggle to efficiently perform operations over such large prime fields.

4. Third Idea: Linear Function with Compressed Encrypted IDs (The Chosen AGR Approach)

To overcome the limitations of polynomial interpolation, the authors propose using a linear function instead.

• ID Representation: Instead of a single large finite field element, IDs are represented as vectors of elements from a small prime field Z_q (e.g., Z_q^L for some small prime q and vector length L). The constraint is q^L must be large enough to provide a sufficient ID space.
• Linear Interpolation: The sender solves for a Matrix M such that M * ID_i equals the corresponding PVW ciphertext for recipient i. This matrix M then forms the clue.
• Detector Operation: The detector, receiving an encrypted ID (Enc(ID)), homomorphically computes M * Enc(ID). This is a single level of multiplication, making it much more efficient than high-degree polynomial evaluation.
• Problem: Linear Independence: For this linear system to be solvable and unique, the IDs must be linearly independent. While this can be achieved if groups are honestly formed and IDs are uniformly random, this assumption doesn't hold in adversarial settings (e.g., a malicious group member). To guarantee linear independence with high probability in arbitrary groups, L would need to be very large (e.g., thousands for G in the tens/hundreds), making the matrix M (and thus the clue size) excessively large.

• Solution: Compressed IDs. To mitigate the large clue size problem while maintaining linear independence, the sender introduces a pseudo-random matrix Zs.
• The sender first samples a pseudo-random matrix Zs of size L x G' (where G' is slightly larger than G, but much smaller than L).
• It then computes a compressed ID ID'_i = ID_i * Zs.
• The sender then solves for a new matrix M such that M * ID'_i equals the corresponding PVW ciphertext.
• The clue now consists of this new matrix M and the seed used to generate Zs.
• The detector first regenerates Zs (in plaintext, very fast). Then, it homomorphically computes Enc(ID) Zs M to obtain the PVW ciphertext. This requires two levels of homomorphic multiplication, which is still highly efficient.
• Summary of AGR: The final AGR construction uses M and Zs's seed as the clue. This clue size is comparable to the naive G * PVW ciphertext size. The detector's work is reduced from G homomorphic PVW decryptions and G encodings to just two efficient matrix multiplications under FHE, resulting in a nearly G-fold speedup. Unlinkability is preserved by encrypting the IDs.

Fixed Group OMR (FGR) Construction

The FGR model assumes that recipients pre-form a group and generate a single group clue key. This more constrained model allows for even greater efficiency.

• The FGR construction leverages a new primitive: a multi-recipient encryption (MRE) scheme. This scheme allows a sender to encrypt a message for multiple recipients simultaneously, using a single group key.
• Crucially, the authors develop the first lattice-based key-private MRE scheme. Key privacy means that the MRE ciphertext itself does not reveal which specific public keys were used in its generation, adding another layer of unlinkability.
• In FGR, the sender obtains the group clue key and generates a group clue (an MRE ciphertext). The detector then processes this single MRE ciphertext.
• Benefits: The MRE scheme is inherently designed for groups, leading to significantly smaller clue sizes (roughly G + PVW_ciphertext_size instead of G * PVW_ciphertext_size for naive or AGR) and even faster detector runtimes. The talk notes that the FGR runtime grows even slower than AGR, approaching near-constant time for large groups.

Both AGR and FGR demonstrate sophisticated cryptographic engineering to achieve high efficiency and strong privacy guarantees in complex group communication scenarios.

Demo / Proof of Concept

▶ Watch: Unlinkability issue with Idea 1 and FHE performance challenges (5:50)

While the talk did not feature a live, interactive demo, the effectiveness and practical viability of the proposed Group Oblivious Message Retrieval (GOMR) schemes were rigorously demonstrated through comprehensive benchmarks and performance evaluations. These results serve as the primary proof of concept, highlighting the significant improvements over naive approaches. The authors provide a link to their code repository, allowing for independent verification and further research.

The key benchmark findings presented were:

1. Detector Runtime Efficiency:

• AGR Performance: Compared to directly using OMR for G recipients (the naive solution), the AGR construction achieved a runtime that was approximately G times faster. This means for a group of 100 recipients, the detector's processing time was reduced by a factor of nearly 100.
• FGR Performance: The FGR construction demonstrated even greater efficiency. Its runtime grew significantly slower than AGR, with the talk highlighting that the time taken for 300 recipients was almost the same as sending to a single recipient. This indicates near-constant time performance for the detector, making it highly scalable for very large fixed groups.

1. Clue Size:

• AGR Clue Size: The clue size for AGR was shown to be essentially the same as the naive solution (G times the size of a single PVW ciphertext). While efficient in runtime, AGR's clue size still scales linearly with the group size G.
• FGR Clue Size: In contrast, the FGR construction achieved a much smaller clue size. It was reported to be almost independent of the group size G, growing negligibly even for thousands of people. This is a critical advantage for applications where bandwidth or storage of clues is a concern.

1. Sender Time:

• The sender's computation time for the GOMR constructions was noted to be worse than the naive solution. This is primarily due to the requirement for the sender to perform Gaussian elimination to solve for the Matrix M in the AGR scheme.
• However, the speakers emphasized that this is a relatively insignificant point to the paper's main contribution (detector and recipient efficiency) and can be greatly improved with standard optimizations. For instance, implementing Gaussian elimination using faster algorithms from well-developed libraries (like Strassen's algorithm for matrix multiplication) would significantly reduce this overhead. The current implementation used the simplest form of Gaussian elimination, leaving ample room for optimization.

These benchmark results convincingly demonstrate that the GOMR constructions, particularly FGR, offer a practically viable and highly efficient solution for private group messaging, overcoming the severe performance limitations of prior approaches. The availability of the code further supports the reproducibility and real-world applicability of this research.

Defensive Implications

▶ Watch: Second proposed idea: Linear function with vector IDs (7:50)

The introduction of Group Oblivious Message Retrieval (GOMR) has significant implications for how privacy-preserving group communication systems can defend against various attacks, particularly Denial of Service (DoS) attacks.

First, in a standard OMR scenario, a malicious sender could craft a clue such that a message is detected as pertinent by many recipients, or even all of them, even if it's not truly intended for them. This can inflate the recipient's computational costs and potentially cause the retrieval process to fail if the estimated maximum number of pertinent messages is exceeded. A recent work (mentioned in the talk) indeed confirmed that some existing OMR constructions are vulnerable to such attacks.

In the group setting, this DoS threat is amplified. A malicious sender could naturally spam up to G recipients (the intended group size) by generating a valid clue for them. The GOMR constructions, however, introduce specific defenses against more widespread abuse:

1. AGR (Ad-hoc Group OMR) DoS Protection:

In the AGR model, the construction is designed to prevent an attacker from spamming more than G plus a small constant number of recipients. Concretely, this constant is very small, typically around five. This means that while a malicious sender can target the intended group, they cannot arbitrarily force a majority or all recipients outside that group to process the message as pertinent. This limits the scale of a DoS attack to a manageable scope, preventing system-wide disruption. This property is proven based on specific sortable conjectures detailed in the paper.

1. FGR (Fixed Group OMR) DoS Protection:

The FGR model offers an even stronger defense. It ensures that two recipients cannot be spammed together if they are not part of the same pre-formed group. Recalling that a group contains at most G recipients, this provides a powerful isolation mechanism. If a sender tries to target a recipient who is not in the designated fixed group for a message, that recipient will not detect the message as pertinent. This property is also proven based on separate sortable conjectures.

These DoS protections are crucial for the robustness of privacy-preserving group communication. Without them, the efficiency gains of GOMR could be undermined by adversaries overwhelming the system or individual clients. By building in these defenses, GOMR ensures that recipients can confidently retrieve their messages with strong privacy guarantees, even when faced with malicious senders. The ability to limit the impact of spamming to either a small constant beyond the intended group (AGR) or strictly within the intended group (FGR) is a significant defensive advantage, making these GOMR constructions suitable for real-world deployment in sensitive applications.

Key Takeaways

• Efficient Recipient Privacy for Groups: GOMR provides a solution for recipients to privately retrieve messages from a public bulletin board without revealing their identity or message interests, specifically addressing the challenge of messages sent to multiple recipients.
• Two Models for Group Flexibility: The research introduces two distinct GOMR models: Ad-hoc Group OMR (AGR) for flexible, dynamically formed groups, and Fixed Group OMR (FGR) for pre-established groups, each optimized for different application contexts.
• AGR's Homomorphic Efficiency: The AGR construction achieves significant speedups (up to G times faster than naive OMR) by using homomorphic operations on compressed encrypted IDs and linear interpolation, drastically reducing the detector's workload from G operations to a constant few.
• FGR's Advanced Cryptography and Superior Performance: The FGR model leverages a novel lattice-based key-private Multi-Recipient Encryption (MRE) scheme, resulting in even greater efficiency with detector runtime almost constant regardless of group size and significantly smaller clue sizes.
• Robust DoS Protection: Both GOMR constructions include built-in defenses against Denial of Service (DoS) attacks, preventing malicious senders from spamming an excessive number of recipients beyond the intended group, thereby ensuring system stability and client usability.
• Practical Viability: Benchmarks demonstrate the practical feasibility and substantial performance gains of GOMR, making it a viable technology for enhancing recipient privacy in real-world applications like secure group messaging and privacy-preserving blockchains.

About the Speaker(s)

The talk "Group Oblivious Message Retrieval" was presented by Zeyu Liu and is a joint work with Eran Tromer and Yunhao Wang. Based on the context of a technical paper presentation at a prestigious conference like IEEE S&P, Zeyu Liu, Eran Tromer, and Yunhao Wang are researchers and authors who have contributed to the field of cryptography and privacy-preserving technologies, specifically in the area of oblivious message retrieval and homomorphic encryption.