Cryptographic Alignment of Distributed Datasets

78 concepts69 papers3 proposals

Modern data analysis frequently requires combining datasets held by different organizations. For example, a bank might want to cross-reference its loan defaults with a power grid's consumption logs to assess credit risk, or healthcare institutions might need to combine medical imaging with genomic records to train diagnostic models.

However, a fundamental dilemma arises: how can two parties identify shared records without exposing their entire, highly sensitive customer or patient lists to one another?

Simply sharing raw identifiers is a clear privacy violation. Even sharing naive cryptographic hashes (such as SHA-256 values of email addresses or phone numbers) is insecure; because the space of possible identifiers is often predictable, an adversary can easily perform a brute-force dictionary attack to reverse the hashes and discover the identities of individuals who are not in the intersection.

Private Set Intersection (PSI) solves this problem. It allows two or more parties to compute the exact overlap of their datasets such that neither party learns anything about the elements unique to the other side.


The Mechanics of Private Set Intersection

To understand why PSI works, it helps to look at the core cryptographic intuition that prevents brute-force dictionary attacks. The goal is to transform the identifiers into abstract tokens using a process where matching inputs yield matching tokens, but the transformation itself cannot be guessed or reversed by the counterparty.

A classic way to achieve this is through commutative encryption. An encryption scheme is commutative if the order in which keys are applied does not affect the final ciphertext:

$$E_A(E_B(x)) = E_B(E_A(x))$$

In a basic commutative PSI protocol, Alice encrypts her dataset with her private key $A$ and sends the ciphertexts to Bob. Bob cannot decrypt these values, nor can he guess the underlying data because he lacks key $A$. Bob then encrypts his own dataset with his private key $B$, and also encrypts Alice's already-encrypted dataset with his key $B$.

When Bob sends Alice's doubly-encrypted dataset back to her, Alice applies her key $A$ to Bob's singly-encrypted dataset. Because the encryption is commutative, both datasets are now encrypted under both keys ($A$ and $B$). Alice can now directly compare the two sets of doubly-encrypted tokens. If a token matches, the underlying element $x$ is in the intersection. If it does not match, Alice learns nothing about Bob's unique element because it remains shielded by key $B$.

Modern protocols have evolved beyond commutative encryption to achieve better performance. As formalized by Liang et al., contemporary PSI implementations generally follow a Map-and-Compare framework. This decomposes the interaction into two distinct phases:

  1. Bidirectional Mapping: The parties interactively generate intermediate pseudorandom tokens using cryptographic primitives like Oblivious Transfer (OT) extensions or homomorphic encryption.
  2. Unidirectional Comparison: One party sends a compressed representation of their tokens to the other, who identifies the common elements without exposing non-intersecting data.

Optimizing for Scale

Early PSI protocols suffered from quadratic computational and communication costs ($O(N \times M)$), making them impractical for industrial-scale applications. To make these systems viable for millions of records, researchers introduced specialized data structures that reduce complexity to linear time ($O(N + M)$).

A primary bottleneck is the comparison phase: checking every token from Alice against every token from Bob. To bypass this, protocols leverage advanced hashing techniques. As demonstrated by Freedman et al., Cuckoo Hashing can be used to map items into a highly organized array of buckets. By ensuring that each item can only reside in a small, deterministic set of locations, the counterparty only needs to compare incoming tokens against a few specific buckets rather than the entire database.

Alice's Element (x) ---> Hash Functions ---> Deterministic Buckets [1, 4, or 7]
                                                    |
                                                    v
                                      Only compare against these buckets!

Further efficiency gains come from decoupling the cryptographic operations from the dataset size. De Cristofaro et al. and Kim et al. proposed linear-complexity protocols that drastically reduce bandwidth consumption. Instead of transmitting heavy cryptographic ciphertexts for every single comparison, modern variants utilize Oblivious Key-Value Stores (OKVS). As shown by Jiang et al., an OKVS allows a server to encode dataset properties into a compact, lightweight structure. The client can then query this structure obliviously, ensuring high throughput even when processing massive, vertically partitioned datasets across distributed nodes (Liu et al.).


Varying the Output: Cardinality and Labeled Extensions

In many real-world scenarios, revealing the exact identity of the overlapping elements is still too permissive. For instance, when testing genetic compatibility or running digital contact tracing, parties may only want to know how much they overlap, rather than who overlaps.

This variation is known as Private Set Intersection Cardinality (PSI-CA). Instead of returning the shared elements, it outputs a single integer representing the size of the intersection.

  • Blundo et al. paired PSI-CA with MinHash approximation techniques to efficiently estimate sample set similarity (such as the Jaccard Index) without revealing the underlying data points.
  • Kikuchi et al. introduced recursive Bayesian estimation over multiple small Bloom filters to calculate intersection sizes even when datasets lack clean, unique identifiers.
  • Tsudik et al. expanded this paradigm to Size-Hiding PSI, which prevents a malicious party from even learning the total size of the counterparty's database, eliminating a common vector for data harvesting.

Conversely, some applications require moving beyond simple intersection to secure data retrieval. Labeled PSI allows a protocol to securely transfer an associated payload (a "label") only when a match is cryptographically confirmed. De Cristofaro et al. and Bienstock et al. demonstrated that auxiliary records can be bound to the set identifiers, ensuring that sensitive data transfer happens conditionally and obliviously upon a successful match.

Taking this a step further, Blass et al. designed Non-Equi PSI protocols for collaborative data cleaning. Instead of matching identical records, their construction specifically isolates records that share a common identifier but possess differing attributes, allowing organizations to find mislabeled data without exposing their correctly aligned records.


The Gateway to Collaborative Machine Learning

Beyond standalone queries, private entity alignment serves as an indispensable pre-processing step for Vertical Federated Learning (VFL). While horizontal federated learning deals with scenarios where different parties hold different rows (users) of the same features, VFL handles scenarios where different parties hold different columns (features) of the same users.

As outlined in the foundational framework by Yang et al., a model cannot be trained across vertical data islands unless the sample spaces are perfectly aligned beforehand. If a bank and an e-commerce platform want to jointly train a credit scoring model, they must first ensure they are matching the correct bank account with the correct shopping profile.

Vertical Partitioning:
[ Bank Dataset: User ID | Account Balance ]  <-- PSI Aligns IDs -->  [ Retail Dataset: User ID | Purchase History ]
                                       \                                 /
                                        v                               v
                                  [ Combined Secure Feature Space for Model Training ]

Ye et al. emphasize that performing this alignment without leaking the identities of non-overlapping users remains a core technical challenge in real-world deployments. If entity resolution is ignored or handled insecurely, the entire privacy pipeline of the federated model collapses. Consequently, robust PSI protocols are routinely deployed as the foundational layer for secure cross-silo applications, ranging from social recommendation systems (Chen et al.) to cross-network user embeddings (Ren et al.).


Real-World Applications

PSI has transitioned from a theoretical cryptographic novelty into a widely deployed tool across diverse domains:

  • Epidemiology and Contact Tracing: During public health crises, decentralized contact tracing systems like Epione (Trieu et al.) and BeeTrace (Liu et al.) used PSI-CA to let a user's device check its location history against a server's list of infection vectors. The user only learns if they were exposed, while the server learns nothing about the user's movements.
  • Healthcare and Genomics: Dong et al. implemented a two-stage pipeline combining PSI with garbled circuits to perform patient risk stratification across separate hospital networks. Similarly, Baldi et al. demonstrated that fully-sequenced human genomes can be tested for paternity or genetic compatibility "in-silico" without exposing raw DNA sequences.
  • Investigative Journalism: In large-scale international investigations, journalists must cross-reference sensitive document leaks without endangering sources. EdalatNejad et al. developed a multi-set PSI protocol that allows reporters to discover if peers hold matching entities across decentralized databases without revealing their active search queries.
  • Data Curation and Conservation: Hui Li demonstrated how encrypted tokens allow major NIH repositories to link multimodal clinical and imaging data safely. Even in wildlife conservation, as shown in the Flukebook platform (Blount et al.), pairwise cryptographic collaboration models allow researchers to discover matches across separate cetacean photo catalogs without prematurely exposing proprietary raw data.
  • Cybersecurity: In threat intelligence, Luca Melis demonstrated that collaborative blacklisting networks can use PSI to identify common malicious IP addresses attacking multiple networks simultaneously, allowing participants to predict and block threats without leaking their internal system logs to competitors.

Key Foundational Work

Confidentiality Preserving Audits of Electronic Medical Record Access (2007) — contributed 1 concept elements to this direction.
Privacy-preserving k-means clustering over vertically partitioned data (2003) — contributed 1 concept elements to this direction.
Knowledge discovery in a circle of trust (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_private_set_intersection_d728f61b,
  title = {private set intersection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/private-set-intersection/rdr_d728f61bd0c74e75a2243e11faa5e167},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_private_set_intersection_d728f61b_v1,
  title = {private set intersection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/private-set-intersection/rdr_d728f61bd0c74e75a2243e11faa5e167/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake