cwPSU: Efficient Unbalanced Private Set Union via Constant-weight Codes

cwPSU: Efficient Unbalanced Private Set Union via Constant-weight Codes

Speakers: Qingwen Li

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=M2-779zVByU

Overview

This talk presents cwPSU, a novel protocol for unbalanced Private Set Union (PSU) that achieves dramatic efficiency improvements over prior work by leveraging constant-weight encoding. Private Set Union allows two parties to compute the union of their private datasets without revealing anything beyond the final result. While most existing PSU protocols are designed for balanced scenarios where both sets are roughly the same size, real-world applications frequently involve highly unbalanced settings -- one party's dataset may be orders of magnitude larger than the other's.

cwPSU addresses this by making communication cost independent of the large set size, requiring only a single round of online communication. The protocol introduces two key primitives: Batch Ciphertext Shuffle (BCS), which prevents information leakage about set membership positions, and EEQ, an optimized equality operator that reduces ciphertext-to-ciphertext multiplications by approximately two-thirds. The result is a protocol achieving up to 13.3x lower computation cost and 32.4x less communication compared to prior state-of-the-art approaches.

Background

▶ Watch: Introduction to Private Set Union and fraud prevention applications (0:00)

Private Set Union is a fundamental cryptographic primitive for privacy-preserving data collaboration. In a PSU protocol, two parties each hold a private set, and they wish to compute the union without revealing which elements belong to which party. This has direct applications in fraud prevention, where multiple organizations need to share suspicious identifiers and risk blacklists across payment networks or online marketplaces without exposing their individual datasets.

The unbalanced setting -- where one party holds a small set and the other holds a significantly larger set -- is particularly common in practice. For example, a small fintech company might want to check its customer list against a large bank's fraud database. Prior work by TCL introduced the permuted matrix private equality test and proposed the first unbalanced PSU protocol based on leveled FHE, achieving communication cost linear in the small set and logarithmic in the large set. The TC optimization incorporated an Oblivious Key-Value Store (OKVS) data structure for further improvements. However, both protocols still maintained communication complexity dependent on the large set size and required multiple rounds of OPRF invocations.

The work builds on established techniques from Private Set Intersection (PSI) protocols, particularly cuckoo hashing for the small set and standard hashing for the large set, adapted for the union computation setting.

Key Findings

▶ Watch: Key contributions: BCS primitive and EEQ operator (4:00)

Communication independence from large set size: The most significant finding is that cwPSU's online communication cost remains constant regardless of how large the receiver's set grows. The protocol only exchanges the selection vector from the receiver and ciphertexts corresponding to the set difference X minus Y from the sender. This is a fundamental improvement over prior protocols where communication scaled with the large set.

EEQ operator efficiency: The optimized equality operator reduces non-scalar multiplications by roughly two-thirds compared to the basic constant-weight equality operator. This is achieved by reformulating the equality test as a polynomial and applying the Paterson-Stockmeyer algorithm for efficient polynomial evaluation using carefully chosen combinations of low-degree and high-degree powers.

Practical performance gains: In benchmarks, cwPSU achieves up to 13.3x lower computation cost and 32.4x less communication overhead compared to baseline protocols. In low-bandwidth settings, cwPSU achieves up to an order of magnitude speedup as set sizes increase. Even in high-bandwidth scenarios, it maintains consistently lower or comparable running times.

Optimal encoding parameters: For 128-bit items, the optimal Hamming weight for constant-weight encoding is 19; for 32-bit items, it is 7. These values balance computation and communication costs for practical deployment.

Technical Deep Dive

▶ Watch: Online protocol: selection vector blinding and filtering (8:00)

The protocol operates in two phases: a setup/preprocessing phase and an online phase.

Preprocessing: Both parties independently prepare their data. The sender (holding small set X) inserts items into a one-dimensional cuckoo hash table TX, where each bin contains exactly one item. The receiver (holding large set Y) inserts items into a two-dimensional hash table TY using standard hashing, where each bin can contain up to B items. Both parties then apply constant-weight encoding to their hashed items, converting each element into a binary string with a fixed Hamming weight.

Batching for homomorphic computation: To enable efficient parallel FHE operations, bits at the same position across multiple codewords are packed into single ciphertexts. Under the homomorphic encryption parameter N, up to N messages can be batched into a single ciphertext. The receiver treats each column of its two-dimensional hash table as an independent one-dimensional table and applies the same packing strategy.

Online phase: The sender encrypts its packed constant-weight codewords under its public key and sends them to the receiver. For each bin, the receiver compares the sender's encoded item against its candidate items using the arithmetic constant-weight equality operator, evaluated homomorphically. The output is an encrypted bit vector E where E[i] = 1 if the sender's item appears in the receiver's bin i, and 0 otherwise. The receiver computes the inverted selection bit (1 - E) to identify items that should be included in the union.

Blinding and filtering: To hide the selection vector from the sender, the receiver blends it by adding random values, then sends the blended vector (encrypted under the sender's public key) along with unencrypted randomness and its own public key. The sender decrypts, removes randomness homomorphically, obtains selection bits encrypted under the receiver's key, and multiplies them with corresponding items to filter out duplicates.

Batch Ciphertext Shuffle (BCS): The basic protocol leaks structural information about which positions in the output correspond to which hash bins. BCS addresses this by allowing the sender to shuffle the encrypted message vector with a private permutation, breaking the link between ciphertext positions and hash bins. This is built using leveled FHE combined with permute-and-share techniques, ensuring the plaintext is hidden from the sender and the permutation is hidden from the receiver.

EEQ optimization: The equality test between two constant-weight codewords begins with computing the inner product K. The basic approach evaluates a polynomial checking whether K equals the Hamming weight H, requiring H ciphertext multiplications. The EEQ reformulation rewrites this as a polynomial F(K) that outputs zero for all K values except H, factored into quadratic terms that halve the multiplication count. The Paterson-Stockmeyer algorithm further reduces the cost by selecting optimal parameters L and H for polynomial evaluation.

Demo / Proof of Concept

▶ Watch: Batch Ciphertext Shuffle to prevent information leakage (10:00)

No live demo was performed. The speaker presented comparative benchmarks against prior protocols (TCL and TC optimizations), demonstrating cwPSU's advantages across multiple dimensions. Communication overhead comparisons showed cwPSU consistently requiring significantly less bandwidth. Runtime breakdowns were presented as a function of the sender's small set size under both low and high bandwidth settings. The EEQ operator evaluation showed a near twofold runtime reduction across settings while only modestly increasing ciphertext size due to additional scalar multiplications, with unchanged multiplicative depth.

Defensive Implications

▶ Watch: Benchmarks: 13.3x computation and 32.4x communication improvements (14:00)

cwPSU's practical significance for defenders lies in enabling cross-organizational fraud detection at scale. Organizations can share risk blacklists and suspicious identifiers without revealing their individual datasets, and the communication efficiency makes this feasible even for organizations with vastly different dataset sizes -- a common real-world constraint.

The protocol's single-round online communication requirement is particularly important for deployment scenarios involving high-latency networks or regulatory environments where minimizing data exchange rounds reduces compliance surface. The fact that communication cost is independent of the large set size means a small organization can query against a large institution's dataset without the large institution's cost scaling with its own dataset size.

From an enterprise security architecture perspective, cwPSU could be integrated into threat intelligence sharing platforms where participating organizations contribute indicators of compromise of varying volumes. The BCS primitive's guarantee against structural information leakage addresses a real concern in competitive environments where even metadata about set membership positions could reveal business intelligence.

The semi-honest security model, while standard for this type of protocol, means deployment requires trust assumptions between participating parties that should be formalized in contractual and governance frameworks.

Key Takeaways

• cwPSU achieves up to 13.3x lower computation and 32.4x less communication than prior unbalanced PSU protocols by leveraging constant-weight encoding
• Online communication cost is independent of the large set size, a fundamental improvement for real-world unbalanced scenarios
• The EEQ operator reduces ciphertext multiplications by roughly two-thirds using polynomial reformulation and the Paterson-Stockmeyer algorithm
• Batch Ciphertext Shuffle (BCS) prevents structural information leakage without significant performance penalty
• The protocol requires only a single round of online communication, minimizing latency and compliance surface
• Optimal Hamming weights are 19 for 128-bit items and 7 for 32-bit items, balancing computation and communication costs

About the Speaker(s)

Qingwen Li presented the work on behalf of the first author (Chinwan), who was unable to attend due to personal reasons. The research team works in the area of applied cryptography with a focus on privacy-preserving set operations and homomorphic encryption. Attendees were directed to contact the first author via email for technical questions about the protocol.