Beyond the Output: Inference Attacks on Private Set Union and Multi-Key Private Matching

Andrea Raguso (Paper author · ETH Zurich), Francesca Falzon (Paper author · ETH Zurich), Tianxin Tang (Paper author · University of Glasgow), Kenneth G. Paterson (Paper author · ETH Zurich)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 3 · Moose

Overview

In the realm of privacy-preserving technologies, Multi-Party Computation (MPC) protocols are designed to allow multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. The standard security guarantees of MPC typically focus on ensuring that nothing beyond the intended output is leaked about the inputs during the computation. However, as this talk by Andrea Raguso and collaborators highlights, the output itself, especially when aggregated over multiple protocol invocations, can become a significant source of privacy leakage, leading to powerful inference attacks.

Watch on YouTube · Slides

Visual summary for Beyond the Output: Inference Attacks on Private Set Union and Multi-Key Private Matching by Andrea Raguso, Francesca Falzon, Tianxin Tang, Kenneth G. Paterson
Visual summary for Beyond the Output: Inference Attacks on Private Set Union and Multi-Key Private Matching by Andrea Raguso, Francesca Falzon, Tianxin Tang, Kenneth G. Paterson

Key moments

  1. 0:00 Problem: MPC outputs can leak info over multiple invocations
  2. 2:15 Paper's focus: Inference attacks on union functionalities
  3. 3:30 Adversary's goal: Infer P2's static input using chosen inputs
  4. 5:45 Crucial protocol leakage: Same hiding function for all values
  5. 6:40 How adversary reconstructs P2's input from observed leakage
  6. 8:15 Experimental results: Attacks are fast and scale linearly
  7. 9:30 Key advice for designers: Consider leakage and ideal output

Beyond the Output: Inference Attacks on Private Set Union and Multi-Key Private Matching

Speakers: Andrea Raguso (Paper author, ETH Zurich), Francesca Falzon (Paper author, ETH Zurich), Tianxin Tang (Paper author, University of Glasgow), Kenneth G. Paterson (Paper author, ETH Zurich)

Conference: PETS

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

Overview

In the realm of privacy-preserving technologies, Multi-Party Computation (MPC) protocols are designed to allow multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. The standard security guarantees of MPC typically focus on ensuring that nothing beyond the intended output is leaked about the inputs during the computation. However, as this talk by Andrea Raguso and collaborators highlights, the output itself, especially when aggregated over multiple protocol invocations, can become a significant source of privacy leakage, leading to powerful inference attacks.

This research delves into a critical, yet often overlooked, vulnerability: what happens when a malicious party strategically manipulates its inputs over repeated interactions to deduce sensitive information about another party's private data? The talk introduces novel intersection recovery attacks against Private Set Union (PSU) and Private Set Union Cardinality (PSUC) functionalities, extending the scope of such attacks beyond traditional intersection-based scenarios. Crucially, the researchers demonstrate highly efficient attacks against Meta's Multi-Key Private Matching (MKPM) protocol by exploiting specific design choices that introduce observable leakage patterns, even when the protocol is cryptographically sound under its stated assumptions.

The implications of this work are profound for the design and deployment of real-world privacy-preserving systems. The findings underscore that merely achieving cryptographic security for the computation itself is insufficient; designers must also meticulously analyze the privacy implications of the intended output and any protocol-specific leakage across repeated use. The attacks presented are not theoretical curiosities but are shown to be practical and efficient, running in mere tens to hundreds of milliseconds, thereby posing a tangible threat to systems relying on these functionalities in production or under development.

Background

▶ Watch: Problem: MPC outputs can leak info over multiple invocations (0:00)

The concept of Multi-Party Computation (MPC) emerged from the foundational work of Yao in the 1980s, enabling mutually distrusting parties to jointly compute a function on their private inputs without revealing those inputs to one another. A classic example involves two banks wanting to identify common blocked IP addresses without disclosing their full lists to each other. An MPC protocol would compute the intersection, providing the banks with the shared list while preserving the privacy of their individual inputs. The security guarantees of such protocols are typically strong, ensuring that the only information revealed is the "intended output."

However, the threat model explored in this work extends beyond traditional MPC security notions. The core problem arises when the output itself, even if cryptographically secure in isolation, can be leveraged by a malicious party to infer private information over multiple protocol invocations. The speaker illustrates this with an example: if Bank A (the malicious party) repeatedly participates in a Private Set Union protocol with Bank B (the honest party), and Bank A strategically omits certain IP addresses from its input, it can observe which omitted addresses still appear in the aggregated union output. If an omitted address appears in the output, Bank A can infer that the address must have been present in Bank B's private list, thereby learning information it was not supposed to.

This scenario is not artificial. Real-world applications often demand repeated invocations of MPC protocols over short periods with changing inputs. A prominent, if controversial, example is Apple's now-paused CSAM (Child Sexual Abuse Material) detection system. While cryptographically designed, concerns were raised that the system's functionality could be abused for surveillance, highlighting that even well-intentioned privacy-preserving systems can have unintended leakage channels. Prior academic work in this area has primarily focused on inference attacks against functionalities that compute over the intersection of two input sets. This research distinguishes itself by focusing on union and union-related functionalities, expanding the scope of potential vulnerabilities.

The threat model for these attacks is specific:

  • Two parties, P1 and P2, are involved in the MPC protocol.
  • P2 is assumed to be honest and holds a static input, Y, referred to as the recovery set. This represents the sensitive data P1 aims to learn.
  • P1 is the malicious adversary. P1 holds a target set, T, which contains known information (e.g., email addresses, phone numbers).
  • P1 is allowed to choose its inputs maliciously and over multiple protocol invocations.
  • P1's ultimate goal is to infer as much information as possible about P2's static input Y, given its own target set T and the observed outputs/leakage from the protocol. This setup allows P1 to probe the system iteratively, gradually piecing together information about Y.

Key Findings

▶ Watch: Adversary's goal: Infer P2's static input using chosen inputs (3:30)

The research presents several critical findings that advance the understanding of inference attacks against privacy-preserving computations:

  • Novel Intersection Recovery Attacks for Union Functionalities: The authors developed and demonstrated effective intersection recovery attacks specifically targeting Private Set Union (PSU) and Private Set Union Cardinality (PSUC) functionalities. This is a significant extension of prior work, which largely concentrated on intersection-based computations, highlighting new vulnerabilities in union-based protocols.
  • Applicability to Real-World Protocols: The attack against the PSUC functionality was shown to be adaptable and applicable to Meta's Multi-Key Private Matching (MKPM) protocol. This demonstrates that theoretical attacks can have direct relevance to complex, production-oriented systems designed by major technology companies.
  • Efficient Attacks Leveraging Protocol-Specific Leakage: Beyond attacks on the ideal functionality, the research uncovered four more efficient attacks against Meta's MKPM protocol. These attacks do not rely on weaknesses in the underlying cryptography but rather exploit protocol-specific leakage arising from design decisions. This type of leakage, where intermediate computations or data transformations reveal patterns, proved to be a powerful vector for inference.
  • Practical Efficiency: The attacks were experimentally evaluated and found to be remarkably efficient, with run times typically ranging from tens to hundreds of milliseconds. This level of performance indicates that these are not merely theoretical concerns but practical threats that could be executed rapidly and repeatedly by an adversary. The attack run times were shown to be largely independent of the amount of shared data between the parties but grew linearly with the size of the adversary's target set, aligning with theoretical predictions.
  • T Reconstruction of Y: The ultimate goal and key outcome of these attacks is a T reconstruction of Y. This means the adversary P1 manages to recover a partial copy of P2's private input Y, specifically containing at least all values that also occur in P1's target set T. This allows P1 to confirm the presence of known sensitive data points within P2's supposedly private dataset.

Technical Deep Dive

▶ Watch: Crucial protocol leakage: Same hiding function for all values (5:45)

The core of the research's most impactful findings revolves around attacks against Meta's Multi-Key Private Matching (MKPM) protocol. This protocol is a sophisticated MPC solution designed to link records across different datasets without revealing the underlying data. It serves as a preprocessing step in Meta's private computation solution, used for tasks like measuring ad performance, and has parallels with Apple's private computation solutions.

Multi-Key Private Matching (MKPM) Functionality

The intended purpose of MKPM is to enable two parties to identify matching records between their respective datasets.

  • Inputs: Each party provides a set of tuples, which are data points representing user information or other entities. For instance, a tuple might contain an email address, a phone number, and a user ID.
  • Matching Logic: The protocol matches these tuples based on shared values within the tuples. The exact matching logic can be complex, involving multiple keys or attributes within the tuples.
  • Output: If two tuples from different parties are matched, the functionality assigns them the same unique label. The parties ultimately learn the full set of these labels, along with a mapping of these labels back to their own records. Critically, they do not learn which of their specific records matched which specific record of the other party, only that a match occurred and its corresponding label. This label set and mapping constitute the intended functionality output.

Protocol-Specific Leakage

While the intended functionality aims for strong privacy, the researchers identified crucial protocol-specific leakage that significantly weakens the security in practice. This leakage stems from specific design choices in how the protocol processes and transforms data before the final label generation.

The leakage occurs in two main steps:

  1. Random Hiding Function:
  • As a first step, all values within the input tuples from both parties are transformed using a random hiding function. This function maps each plaintext value (e.g., an email address) to a unique, randomly chosen hidden value.
  • Crucial Leakage Point: The same random hiding function is applied to values from both parties. This means if the same plaintext value appears in P1's input and P2's input, it will be mapped to the exact same hidden value in both parties' transformed datasets. Furthermore, if a value appears multiple times within a single party's input, it will consistently map to the same hidden value across all its occurrences. This preserves the pattern of repeating values.
  1. Independent Shuffling:
  • After the hiding step, the sets of hidden tuples are shuffled independently for each party.
  • From P1's perspective, it observes two sets of tuples containing random, hidden values. Let's call P1's hidden input LT and P2's hidden input LY.
  • Crucial Leakage Point: While the order of tuples is randomized, the internal structure of the tuples (the relative positions of values within a tuple) is maintained. More importantly, the pattern of repeating hidden values (derived from the original plaintext values) is preserved within LT and LY.

The combination of these two leakage points is highly exploitable. P1, the adversary, can observe LT (its own hidden input) and LY (P2's hidden input). Because the same hiding function is used, if P1 knows a plaintext value v in its input T, it also knows its hidden representation h(v) within LT. If P1 then observes h(v) appearing in LY, it has a strong indication that v also exists in P2's input Y.

The Attack Approach: T Reconstruction of Y

The attack leverages this leakage to achieve a T reconstruction of Y, meaning P1 recovers a partial copy of Y that includes at least all values present in its target set T. The general approach is as follows:

  1. P1's Input and Observation: P1 runs the MKPM protocol, providing its target set T as its input. During or after the pre-processing steps, P1 observes the hidden, shuffled versions of both its input (LT) and P2's input (LY).
  1. Matching Plaintext to Hidden Tuples: The primary challenge for P1 is to establish a correspondence between its original plaintext tuples in T and their hidden, shuffled counterparts in LT. Since the tuples are shuffled, P1 doesn't know which hidden tuple in LT corresponds to which plaintext tuple in T.
  • If T contains only one record, this matching is trivial.
  • For T with multiple records, this becomes more involved. The paper's contribution here lies in developing techniques to solve this matching problem. While the exact algorithms are complex and refer to the poster for full details, the core idea likely involves using the preserved "patterns of repeating values." For example, if a specific plaintext value v1 appears in two tuples in T, and another value v2 appears in one tuple, the corresponding hidden values h(v1) and h(v2) will exhibit the same frequency and co-occurrence patterns within LT. By analyzing these structural properties (e.g., the number of unique values in a tuple, the frequency of specific hidden values across tuples), P1 can statistically or deterministically map its plaintext tuples to the hidden tuples in LT.
  1. Assigning Plaintext to Hidden Values: Once P1 has successfully matched its plaintext tuples in T to their hidden representations in LT, it effectively knows the plaintext equivalent for every hidden value present in LT. For example, if P1 matches (email_A, phone_X) to (h(email_A), h(phone_X)), it now knows that h(email_A) corresponds to email_A and h(phone_X) corresponds to phone_X.
  1. Inferring P2's Input (Y) from LY: With this knowledge, P1 can then examine LY, P2's hidden input. For every hidden value hv observed in LY:
  • If hv is one of the hidden values P1 has already mapped to a plaintext value (e.g., h(email_A)), P1 can immediately infer that the corresponding plaintext value (email_A) must be present in P2's input Y.
  • This process allows P1 to "substitute values" in LY with their plaintext equivalents, effectively reconstructing a significant portion of Y – specifically, all parts of Y that overlap with T or contain values that P1 can identify from its own input.

This detailed exploitation of the "same random hiding function" and "preservation of repeating value patterns" demonstrates a powerful attack vector that bypasses the cryptographic security of the protocol's later stages by extracting information from its initial data transformation steps.

Demo / Proof of Concept

▶ Watch: Experimental results: Attacks are fast and scale linearly (8:15)

The practical viability of these inference attacks was validated through an experimental evaluation, serving as a robust proof of concept. The experimental setup and results highlight the efficiency and scalability of the proposed methods.

Experimental Setup:

  • The researchers fixed the size of P2's static input set, Y, which is the recovery set the adversary aims to reconstruct.
  • They generated synthetic datasets to systematically vary two key parameters:
  1. The size of P1's target set, T.
  2. The amount of shared information (overlap) between P1's target set T and P2's recovery set Y.
  • The primary metric measured was the attack run time. Crucially, this measurement excluded the time taken for the computation of the MPC functionality itself and any network latencies. This means the reported run times reflect the overhead of the adversary's inference process, providing a clear indication of how quickly P1 can perform the necessary analysis to reconstruct Y.

Experimental Results:

The evaluation yielded compelling results demonstrating the practicality of the attacks:

  • High Efficiency: The attacks were found to be remarkably fast, with run times typically ranging between tens and hundreds of milliseconds. This sub-second performance means an adversary can execute these inference steps rapidly, even for moderately sized datasets, allowing for repeated probing if necessary.
  • Independence from Shared Data: The attack run times were observed to be largely independent of the amount of shared data between the two sets (T and Y). This is a significant finding, as it implies the attack's efficiency is not bottlenecked by the density of overlapping information, making it robust across various data distributions.
  • Linear Scaling with Target Set Size: As predicted by theoretical complexity analysis, the run time of the attack grew linearly with increasing target set sizes. This linear scaling indicates good performance characteristics for larger inputs, suggesting that the attack remains practical even when P1's target set T contains a substantial amount of known information.

These experimental findings underscore that the identified vulnerabilities are not merely theoretical but represent practical, efficient threats to systems employing Private Set Union or Multi-Key Private Matching functionalities. The ability to perform such an inference in milliseconds makes repeated probing a highly feasible strategy for a determined adversary.

Defensive Implications

▶ Watch: Key advice for designers: Consider leakage and ideal output (9:30)

The findings presented in this research have critical implications for developers, cryptographers, and organizations deploying privacy-preserving technologies. The talk concludes with two key takeaways for defensive strategies:

  1. Rethink Protocol Design and "Leaky" Functionalities:
  • The research draws a crucial distinction between an intended functionality (what the protocol is designed to achieve) and leaky functionalities (what the protocol actually reveals, including intermediate states or unintended side effects).
  • Defenders must not "shrug off" observed leakage patterns as benign or insignificant. The presence of protocol-specific leakage, even if cryptographically sound under certain assumptions, can be a direct result of design decisions. Attacks exploiting such leakage serve as a direct critique of these choices.
  • Actionable Advice: When designing or implementing MPC protocols, a rigorous leakage analysis should be performed, considering not just the final output but also all intermediate data transformations and observable patterns. Designers should actively ask: "What could an adversary infer from this specific leakage pattern over multiple invocations?" If a design choice introduces a specific pattern (like the consistent mapping of values in Meta's MKPM), its privacy implications must be fully understood and mitigated, rather than dismissed.
  1. Scrutinize Ideal Functionalities and Deployment Context:
  • Even in a hypothetical scenario where an MPC system has no leakage at all and only outputs the perfectly defined ideal functionality, defenders must still critically evaluate the privacy implications.
  • The intended output itself might reveal too much information about the inputs, especially when aggregated over time or analyzed in specific contexts. The example of Apple's CSAM detection system, where the functionality itself could be abused for surveillance despite its cryptographic security, serves as a stark warning.
  • Actionable Advice: Organizations must consider whether deploying a particular functionality is appropriate at all for a given sensitive context. Before deployment, a comprehensive privacy impact assessment should be conducted, analyzing how the intended output, even if perfectly generated, could be misused or lead to inference attacks. This involves understanding the broader ecosystem, potential adversary goals, and the sensitivity of the data involved. If the ideal output inherently carries too much risk, then the functionality may simply be unsuitable for that application, regardless of its cryptographic implementation.

The disclosure process undertaken by the researchers further emphasizes the importance of these implications. Upon contacting the authors of Meta's original paper, the leakage was acknowledged, though it was stated that the protocol is "not currently being used in production at Meta." This highlights the proactive nature of security research in identifying potential vulnerabilities before widespread deployment, urging caution and re-evaluation in the design and application of private computation solutions.

Key Takeaways

  • Inference attacks pose a significant and practical threat to Multi-Party Computation (MPC) protocols, especially when adversaries can strategically choose inputs and observe outputs over multiple invocations.
  • This research extends the scope of such attacks beyond traditional intersection-based functionalities to Private Set Union (PSU) and Private Set Union Cardinality (PSUC), revealing new vulnerabilities in these union-related operations.
  • Protocol-specific leakage, arising from subtle design choices, can be a powerful attack vector. The Multi-Key Private Matching (MKPM) protocol's use of a single random hiding function across parties and the preservation of value patterns enabled highly efficient inference attacks.
  • The attacks demonstrated are highly efficient and practical, with run times in the range of tens to hundreds of milliseconds, making them feasible for rapid execution against real-world systems.
  • **MPC protocol designers must rigorously analyze all observable outputs and intermediate leakage patterns**, not just the intended output, to understand what an adversary could infer, rather than dismissing minor leakage as inconsequential.
  • Even when an MPC protocol achieves perfect cryptographic security for its ideal functionality, the intended output itself might reveal too much sensitive information in certain contexts, making the functionality fundamentally inappropriate for deployment.

About the Speaker(s)

The research presented was a collaborative effort by a team of distinguished academics:

  • Andrea Raguso (Paper author, ETH Zurich)
  • Francesca Falzon (Paper author, ETH Zurich)
  • Tianxin Tang (Paper author, University of Glasgow)
  • Kenneth G. Paterson (Paper author, ETH Zurich)

These researchers are affiliated with leading institutions in Europe, contributing their expertise in cryptography, privacy, and secure multi-party computation to uncover and analyze critical vulnerabilities in modern privacy-preserving systems. Their work at ETH Zurich and the University of Glasgow represents a significant contribution to the ongoing dialogue about the practical security of MPC technologies.

Reviews

Dr. Zero (Offensive Security Researcher) — MUST SEE

This is exactly why I don't trust vendor MPC implementations. Raguso and the ETH Zurich crew take a sledgehammer to Meta's Multi-Key Private Matching protocol, proving that even cryptographically sound MPC is fatal if the protocol leaks intermediate patterns. It's a textbook demonstration of how a single bad engineering choice turns a complex privacy shield into a simple substitution cipher.

Heather Calloway (CISO) — MUST SEE

The industry is heavily investing in Multi-Party Computation (MPC) as a magic bullet to share data across organizations without triggering privacy regulations. This research proves that even mathematically sound MPC protocols can leak sensitive datasets through iterative inference attacks on their outputs. It is required reading for any CISO or General Counsel evaluating privacy-enhancing technologies for joint business initiatives.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026