Multi-Party Private Join

Anja Lehmann (Paper author · Hasso-Plattner-Institute, University of Potsdam), Christian Mouchet (Paper author · Hasso-Plattner-Institute, University of Potsdam), Andrey Sidorenko (Paper author · Hasso-Plattner-Institute, University of Potsdam)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Alpaca

Overview

In an era defined by vast datasets and the imperative for data privacy, the challenge of collaboratively analyzing information from multiple independent sources without compromising sensitive details remains a critical hurdle. The talk "Multi-Party Private Join," presented by Andrey Sidorenko, Anja Lehmann, and Christian Mouchet from the Hasso Plattner Institute and University of Potsdam, addresses this complex problem. The speakers introduce a novel cryptographic protocol designed to enable an inner join operation across several distinct databases, where each database is controlled by a different entity, and a receiver wishes to obtain the joined result without learning any extraneous information.

Watch on YouTube · Slides

Visual summary for Multi-Party Private Join by Anja Lehmann, Christian Mouchet, Andrey Sidorenko
Visual summary for Multi-Party Private Join by Anja Lehmann, Christian Mouchet, Andrey Sidorenko

Key moments

  1. 0:00 Introduction: Multi-Party Join Problem and Privacy Goals
  2. 2:40 Limitations of existing solutions like PSI and PJC
  3. 4:47 Our solution: Introducing a helper party for efficiency
  4. 6:16 Helper's role: Pseudonymizing UIDs and secret sharing data
  5. 8:40 Receiver's final steps and security properties
  6. 9:50 The non-collusion assumption between receiver and helper

Multi-Party Private Join

Speakers: Anja Lehmann (Paper author, Hasso-Plattner-Institute, University of Potsdam); Christian Mouchet (Paper author, Hasso-Plattner-Institute, University of Potsdam); Andrey Sidorenko (Paper author, Hasso-Plattner-Institute, University of Potsdam)

Conference: PETS

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

Overview

In an era defined by vast datasets and the imperative for data privacy, the challenge of collaboratively analyzing information from multiple independent sources without compromising sensitive details remains a critical hurdle. The talk "Multi-Party Private Join," presented by Andrey Sidorenko, Anja Lehmann, and Christian Mouchet from the Hasso Plattner Institute and University of Potsdam, addresses this complex problem. The speakers introduce a novel cryptographic protocol designed to enable an inner join operation across several distinct databases, where each database is controlled by a different entity, and a receiver wishes to obtain the joined result without learning any extraneous information.

The core motivation behind this work stems from the practical limitations of existing solutions. While simple, a central server approach creates a single point of failure and privacy vulnerabilities, especially with personal data like medical records. More advanced cryptographic techniques, such as generic Multi-Party Computation (MPC) or Fully Homomorphic Encryption (FHE), offer strong privacy guarantees but often suffer from prohibitive performance overheads, making them unsuitable for resource-constrained environments or high-throughput applications. This research proposes a more efficient and scalable alternative by introducing a designated helper party to offload computational complexity, thereby making secure multi-party data joining practical for real-world scenarios like collaborative medical research or inter-organizational data analysis.

The protocol formalizes two critical privacy properties: join anonymity for the receiver, ensuring they only learn the final, joined dataset stripped of identifiers and non-matching entries; and source privacy for the data providers, guaranteeing they learn nothing about the operation beyond providing their initial encrypted inputs. By carefully balancing security, performance, and scalability, this work offers a significant step forward in enabling privacy-preserving data collaboration across multiple distrusting parties, mitigating the risks associated with centralized data aggregation while overcoming the performance bottlenecks of generic cryptographic primitives.

Background

▶ Watch: Introduction: Multi-Party Join Problem and Privacy Goals (0:00)

The foundational problem addressed by this talk is the multi-party join, a database operation where several distinct data sources, each possessing a database (conceptually, a table with a unique identifier and an associated value), aim to find and combine rows that share common identifiers across all participating databases. For instance, in a medical context, different hospitals might hold patient records (e.g., patient name as UID, age or blood group as value) and wish to identify patients present in all their databases to correlate their attributes. If all databases and the receiver were on the same server, this would be a straightforward inner join. However, the scenario becomes significantly more complex and privacy-sensitive when these data sources are operated by different, potentially distrusting entities, and the receiver cannot be fully trusted with raw, unmasked data.

Traditional approaches to this problem present substantial drawbacks. The most straightforward method, uploading all data to a central server, allows for easy computation of the join. This solution, while simple and sometimes used in practice (e.g., for German patient data), is fundamentally not privacy-preserving. It creates a massive single point of failure, as the central server gains access to all raw, sensitive data, making it a prime target for attacks and a significant compliance risk for personal data.

At the other end of the spectrum lie advanced cryptographic techniques like generic Multi-Party Computation (MPC) or Fully Homomorphic Encryption (FHE). These methods theoretically allow arbitrary computations on encrypted data, offering robust privacy guarantees. However, their practical application for multi-party join operations is severely hampered by performance issues. MPC protocols often involve numerous interactive rounds and high computational loads, while FHE schemes typically incur significant overheads in terms of processing time and data size. The speakers emphasize that entities like hospitals often lack the computational resources or the ability to partake in complex, multi-round interactive protocols, rendering generic solutions impractical.

More specialized approaches also fall short. Private Set Intersection (PSI) protocols allow two or more parties to discover common elements in their datasets without revealing any non-common elements. While PSI scales well for multi-parties and is efficient, it is insufficient for the multi-party private join use case for two main reasons. First, PSI typically reveals the intersection to the participating sources, which contradicts the requirement for source privacy where sources should learn nothing. Second, PSI only identifies shared identifiers; it does not provide a mechanism to combine or compute on the associated values, which is a core requirement of a join operation.

A more recent and relevant category of work is Private Join and Compute (PJC). These protocols aim to perform a join and then apply a function (e.g., aggregation, average, count, inner product) on the associated values of the joined elements. While PJC protocols appear promising, the speakers highlight their limitations: many cannot scale beyond two or three parties, making them unsuitable for truly multi-party scenarios. Crucially, in many PJC constructions, the "compute" functionality cannot be removed or simplified to achieve a plain join without compromising the underlying security properties. This means that a protocol designed for complex computations might not securely reduce to a simple, efficient join.

Recognizing these gaps, the authors propose a novel architecture that integrates a helper party to overcome both performance and security challenges. This helper party is designed to take on the "brunt of the computation and complexity," allowing the data sources to merely encrypt their data and then drop out of the protocol. A critical new security requirement introduced for this architecture is helper obliviousness, ensuring that the helper, despite its central role in computation, learns no new information about the data beyond what is inherently revealed by its protocol execution. This innovative approach aims to deliver a practical, scalable, and privacy-preserving multi-party private join solution.

Key Findings

▶ Watch: Our solution: Introducing a helper party for efficiency (4:47)

The central contribution of this research is the development of a novel protocol for Multi-Party Private Join that effectively addresses the critical performance and security limitations inherent in prior approaches. The authors' key findings and contributions can be summarized as follows:

Firstly, the talk formalizes the essential privacy properties required for such a protocol. For the receiver, the property of join anonymity is introduced, ensuring that the receiver learns only the final, combined table of shared identifiers and their associated values. Specifically, the receiver must not learn which specific unique identifiers (UIDs) were part of the join, nor any information about data that was not included in the final, common intersection. For the data sources, the protocol guarantees source privacy, meaning that the participating entities learn nothing from the protocol's execution beyond providing their initial inputs.

Secondly, the protocol introduces and leverages a designated helper party as a core architectural component. This helper party is instrumental in achieving efficiency, particularly for the data sources. The sources are only required to encrypt their data and send it to the helper, after which they can go offline, significantly reducing their computational and communication burden. This design choice makes the protocol highly practical for entities with limited computational power or network bandwidth, such as hospitals.

Thirdly, a crucial security property for this new architecture, helper obliviousness, is defined and achieved. Despite performing significant computational work, the helper learns no new information during the protocol execution. It operates solely on encrypted data, ensuring that it cannot deduce original identifiers or associated values, thereby preventing it from becoming another single point of failure or a privacy risk.

Fourthly, the protocol successfully scales for multi-party scenarios, moving beyond the two- or three-party limitations often found in existing Private Join and Compute (PJC) protocols. It provides a direct, plain join functionality without needing to incorporate complex, computationally intensive "compute" operations that cannot be easily stripped away without compromising security.

Finally, the authors formally prove the security of their protocol. The security guarantees are established under the non-collusion assumption between the receiver and the helper. This means that if the receiver and helper parties do not collude, the protocol provides strong privacy guarantees for both sources and the receiver. The protocol also acknowledges a "small and acceptable leakage," where the receiver might infer that a match occurred in a subset of databases (e.g., two out of three) but cannot determine the specific identifiers or associated values, nor which specific databases were involved in the partial match. This carefully managed leakage is deemed acceptable in exchange for the protocol's significant performance and scalability benefits.

Technical Deep Dive

▶ Watch: Helper's role: Pseudonymizing UIDs and secret sharing data (6:16)

The proposed Multi-Party Private Join protocol is structured in a multi-stage process involving the data sources, a helper party, and the receiver. The protocol is designed to maximize efficiency for the data sources while ensuring strong privacy guarantees under the non-collusion assumption between the helper and the receiver.

1. Initial Data Preparation and Encryption by Data Sources:

Each data source possesses a database, conceptualized as a table with two columns: a Unique Identifier (UID) (e.g., a person's name) and an associated value (e.g., age, blood group).

As the first step, all participating data sources encrypt their entire database. This encryption is performed towards the receiver, meaning they use the receiver's public key. The choice of encryption scheme is critical, as subsequent homomorphic operations will be performed on these ciphertexts. The speaker mentions partially homomorphic encryption (PHE) schemes like ElGamal as suitable candidates due to their efficiency for specific operations.

Once encrypted, these ciphertexts are sent to the helper party. A key advantage here is that the data sources are no longer required to participate in the protocol; they can go offline, significantly reducing their computational and communication burden. This design choice directly addresses the performance requirements for entities like hospitals. Furthermore, at this stage, the helper obliviousness property is intuitively met, as the helper only receives encrypted data and cannot learn any plaintext information.

2. Helper Party Operations (The "Brunt of Computation"):

The helper party is central to the protocol's security and efficiency. It performs two major operations on the encrypted data received from the sources:

  • Pseudonymization of UIDs: The primary goal here is to hide the actual UIDs from the receiver while still allowing for the identification of common UIDs. For each encrypted UID, the helper homomorphically applies a pseudorandom function (PRF). This PRF is specifically implemented as an Oblivious Pseudorandom Function (OPRF). An OPRF allows a client (in this case, the helper, operating on encrypted data) to compute the output of a PRF on its input, where the PRF key is held by a server (conceptually, the receiver's key is involved in the homomorphic context, or a separate OPRF server could be involved in a more complex setup), without revealing the input to the server or the server's key to the client. The result is that each original UID (e.g., "Bob") is mapped to a pseudonym (e.g., "X"), and "Dave" to "Z." Crucially, this mapping is not linkable back to the original identifiers, thereby ensuring the privacy of UIDs. The use of partially homomorphic encryption schemes like ElGamal is particularly efficient for this step, as they allow for operations like additions or multiplications on ciphertexts, which can be leveraged to implement PRFs.
  • Secret Sharing of Associated Data: While the UIDs are pseudonymized, the associated values (e.g., age, blood group) also need protection. This is achieved by transforming the associated data into a form that requires multiple "keys" to decrypt. The same OPRF functionality used for UID pseudonymization is leveraged here. For each associated value, the helper generates a set of distinct shares or "keys," also derived homomorphically based on the original database tables and the input UIDs. Conceptually, if there are N data sources, the associated data for a particular UID would require N different keys to be recovered. A new column is added to the encrypted table, containing these derived keys. If a UID is present in all N databases, the receiver will eventually obtain all N keys for its associated value. If a UID is only present in a subset of databases (e.g., "Dave" in two out of three), the receiver will only obtain a subset of the necessary keys, thus preventing the recovery of the associated value.
  • Shuffling: After the pseudonymization and secret sharing steps, the helper performs a random shuffle of all the rows in the modified, encrypted table. This step is crucial for preventing leakage about the original data sources' positions or relationships between records based on their order. Without shuffling, the receiver might infer which pseudonymized UIDs originated from which source, compromising source privacy.

3. Receiver Decryption and Join Operation:

Upon receiving the shuffled, homomorphically processed table from the helper, the receiver uses its secret key to decrypt the entire table. The decrypted table will now contain pseudonymized UIDs, the encrypted associated values (which are now effectively secret-shared), and the corresponding derived keys.

The receiver's task is then to perform the actual join. It scans the decrypted table to identify pseudonymized UIDs (e.g., "X") that appear N times (e.g., three times, corresponding to three data sources). For each such fully-matched UID, the receiver collects the N different keys associated with that UID. With all N keys in hand, the receiver can then successfully reconstruct and recover the original associated values. This process yields the final output table, which contains only the UIDs that were shared across all databases, along with their combined associated values.

Handling Non-Full Joins and Leakage:

For any UID that was not part of the full inner join (i.e., not present in all N databases, like "Dave" appearing in only two), the receiver will not be able to collect all N required keys. Consequently, the receiver cannot recover the hidden associated data for these partial matches. Similarly, since the UIDs were pseudonymized, the receiver cannot link "X" or "Z" back to "Bob" or "Dave."

The protocol does acknowledge a "small and acceptable leakage." The receiver might observe that a particular pseudonymized UID appeared in, for example, two out of three databases. While the receiver cannot learn the actual UID, the associated value, or which specific original databases contributed to this partial match, the existence of such a partial match is a form of leakage. The authors consider this minimal leakage acceptable given the significant performance and privacy benefits, and the security proof holds under this specific condition.

Security Assumption:

The protocol's security relies fundamentally on the non-collusion assumption between the receiver and the helper. If the helper were to collude with the receiver (e.g., if the helper obtained the receiver's secret key), they could jointly recover all information, completely undermining the privacy guarantees. This highlights the importance of carefully selecting and trusting the helper party, or distributing the helper's role among multiple, non-colluding entities in more advanced setups.

Demo / Proof of Concept

▶ Watch: Receiver's final steps and security properties (8:40)

The talk "Multi-Party Private Join" primarily focuses on the theoretical construction, formalization of privacy properties, and security proofs of the proposed cryptographic protocol. While the speaker provides a detailed overview of how the protocol works step-by-step, including the roles of data sources, the helper, and the receiver, no explicit live demonstration or a specific proof-of-concept tool was presented during the conference session. The speaker noted that further details could be discussed at a poster session, suggesting that the presentation was geared towards outlining the research paper's core contributions rather than showcasing a working implementation. Therefore, the detailed protocol description itself serves as the foundational basis for future implementations.

Defensive Implications

▶ Watch: The non-collusion assumption between receiver and helper (9:50)

The Multi-Party Private Join protocol offers significant defensive implications, primarily by empowering organizations to engage in secure, privacy-preserving data collaboration. This is especially critical for industries handling sensitive personal or proprietary information.

  1. Enabling Secure Data Collaboration: The most direct implication is the ability for multiple, independent entities (e.g., hospitals, financial institutions, research consortia) to perform collective data analysis without compromising the privacy of their individual datasets. This allows for valuable insights to be derived from combined data, such as identifying common disease patterns across patient populations or detecting sophisticated fraud schemes across different banks, without any single entity or a central server gaining access to raw, unmasked sensitive data.
  1. Mitigating Single Points of Failure and Data Breaches: By eliminating the need for a trusted central server that aggregates all raw data, the protocol significantly reduces the risk of large-scale data breaches. Instead of a single honey pot of sensitive information, the data remains distributed and encrypted, even during the join operation. This decentralization of trust is a fundamental defensive posture against insider threats and external attacks targeting centralized data repositories.
  1. Enhancing Compliance with Data Privacy Regulations: Regulations like GDPR, HIPAA, CCPA, and others mandate strict controls over personal data. This protocol directly supports compliance by minimizing data exposure. Data sources only reveal encrypted inputs, and the receiver only learns the strictly necessary joined output, devoid of original identifiers or non-matching entries. This "privacy by design" approach helps organizations meet legal and ethical obligations for data protection.
  1. Practicality for Resource-Constrained Environments: The protocol's design, which allows data sources to encrypt their data and then go offline, makes it highly practical for organizations that may not have the computational infrastructure or expertise to participate in complex, interactive Multi-Party Computation (MPC) protocols. This broadens the applicability of privacy-enhancing technologies to a wider range of potential users, fostering greater adoption of secure data practices.
  1. Careful Selection and Auditing of the Helper Party: While the helper is designed to be oblivious, the protocol's security critically depends on the non-collusion assumption between the helper and the receiver. Defensively, this means that the helper party must be a genuinely independent and trusted third party. Organizations deploying this protocol must implement rigorous vetting, auditing, and contractual agreements for the helper to ensure it adheres to its non-colluding role. In scenarios where a single trusted helper is problematic, advanced deployments might consider distributing the helper's role among multiple, non-colluding entities to further enhance robustness.
  1. Addressing Data Utility vs. Privacy Trade-offs: The protocol explicitly acknowledges a "small and acceptable leakage" where the receiver might infer partial matches. Defenders need to evaluate if this level of leakage is acceptable for their specific use case and threat model. For many applications, the utility gained from the joined data far outweighs this minimal, unidentifiable leakage, making it a powerful tool in a defender's arsenal for secure data utilization.

In essence, the Multi-Party Private Join protocol provides a robust cryptographic primitive that allows organizations to defensively manage and leverage their sensitive data in collaborative environments, moving beyond the traditional compromises between data utility and data privacy.

Key Takeaways

  • The Multi-Party Private Join protocol enables secure inner join operations across multiple independent databases without revealing sensitive, unjoined, or identifying information.
  • It introduces a helper party to offload computational complexity from data sources, making the protocol efficient and practical for entities with limited resources.
  • The protocol formally defines and achieves join anonymity for the receiver (only learns the final, stripped join) and source privacy for data providers (learn nothing beyond input).
  • It leverages partially homomorphic encryption (e.g., ElGamal) and Oblivious Pseudorandom Functions (OPRFs) for efficient pseudonymization of UIDs and secret sharing of associated values.
  • Security relies on the non-collusion assumption between the receiver and the helper, with a noted "small and acceptable leakage" regarding partial matches.
  • This work offers a scalable and practical alternative to generic MPC/FHE or limited PJC protocols for multi-party data collaboration in privacy-sensitive domains.

About the Speaker(s)

The talk "Multi-Party Private Join" was presented by Andrey Sidorenko, who is a paper author affiliated with the Hasso-Plattner-Institute at the University of Potsdam. The research is a joint work with his colleagues, Anja Lehmann and Christian Mouchet, who are also paper authors from the same institution. Their collective work focuses on advancing cryptographic protocols to enable privacy-preserving data operations, addressing the practical challenges of secure multi-party computation.

Reviews

Dr. Zero (Offensive Security Researcher) — SOLID

They built a multi-party private join protocol using ElGamal and OPRFs to dodge the massive overhead of generic MPC. It's mathematically sound, but relies entirely on a 'helper party' that just pinky-promises not to collude with the receiver. Good academic crypto, but I need to see the code, not just the poster session.

Heather Calloway (CISO) — STRONG ACCEPT

This research solves a massive headache for the business: how to execute cross-organizational data sharing without violating privacy regulations or building a centralized honey pot. It's an elegant architectural compromise that enterprise risk teams need to understand as privacy-enhancing technologies move from academia to procurement.

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

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026