Beyond the Output: Inference Attacks on Private Set Union and Multi-Key Private Matching
Authors: Andrea Raguso (ETH Zürich), Francesca Falzon (ETH Zürich), Tianxin Tang (University of Glasgow), Kenneth G. Paterson (ETH Zürich)
Volume: 2026
Issue: 4
Pages: 983–1005
DOI: https://doi.org/10.56553/popets-2026-0155
Artifact: Available, Functional, Reproduced
Abstract: Recent work (Falzon and Tang USENIX 2025) has shown that a protocol participant who behaves honestly but strategically chooses its inputs can break input privacy in the Private Join and Compute functionality. In this work, we expand our understanding of attacks in this setting by investigating a broader class of functionalities, namely: Private Set Union (PSU), PSU-Cardinality (PSU-CA), and Meta’s multi-key private matching (MKPM) functionality.
We begin with a simple yet novel attack on PSU that fully reconstructs the intersection using only two protocol invocations and forms the conceptual foundation for our more complex attacks. We also show that any attack on PSI-Cardinality, such as that of Guo et al. (USENIX 2023), lifts to an attack on PSU-CA that recovers the intersection with only three additional queries. For the MKPM protocol, we distinguish its intended matching functionality from the protocol-specific leakage, give an attack against the intended functionality, and then show that exploiting the additional leakage enables even stronger attacks, including partial reconstruction of the other party’s records from a single protocol invocation.
We conclude by discussing possible mitigations for deploying such systems. Our analysis demonstrates limitations of existing secure multi-party computation security definitions and highlights the real-world privacy risks associated with deploying these functionalities in practice.
Keywords: private set union, private set intersection, multi-key private matching, attacks, multi-party computation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
