Matching records without revealing them

Aligning records on a shared key is a routine data operation, whether joining tables inside a database, merging files, or combining data sets held by different organizations. The difficulty is that a conventional join exposes the full records of at least one side. For example, when Alice and Bob each hold lists of contacts identified by email address and want a count of mutual contacts, traditional matching requires one party to hand over everything. Privacy-enhancing technologies (PETs) avoid that by letting the parties compute an agreed result while revealing nothing beyond it.

Private set intersection (PSI) has long covered the basic case. The classic trick is a commutative encryption scheme where double encryption yields the same ciphertext regardless of key order:

encryptkeybob(encryptkeyalice([email protected])) = encryptkeyalice(encryptkeybob([email protected]))

Two parties can then encrypt their lists, exchange and re-encrypt the results, and compare shuffled values to count matches without learning which specific records overlap. In a worked example with two lists of eight addresses each, the parties learn there are 12 unique attendees among the combined 16, but not which four addresses were shared.

PSI alone only supports simple computations on the join result. Many analyses require something richer: a sum, a test statistic, or a trained model that depends on columns from both parties. Those cases call for more powerful PETs like multiparty computation (MPC) or homomorphic encryption (HE), which compute over the combined data while keeping everything except the final answer hidden.

Consider three scenarios:

  1. Alice knows donation amounts and Bob knows each donor’s giving category. The parties want the total donated per category.
  2. Alice holds the outcome of a randomized controlled trial; Bob knows which participants were in the treatment versus control group. The parties want the test statistics.
  3. Alice knows historical lifetime donations; Bob has predictive features such as years active and volunteer event count. The parties want to train a regression model.

Money by category

Taken together, these yield category totals, treatment-versus-control counts, and a regression model — but only if the data from both parties can be brought into alignment first. And that alignment step, inside a generic MPC, turns out to be disproportionately expensive.

Private-ID and PS3I

The alignment problem can be pulled out of the MPC and solved with two new protocols that extend the PSI double-encryption idea. Private-ID and PS3I let two parties feed encrypted, already-joined data into an MPC or another PET, subject to two privacy guarantees: neither party learns anything about the other’s data except the computation’s output, and neither party learns which of its own records matched — only the total count. Operationally, only the join identifier is needed up front; features can be attached later, and one side may hold a static database while the other streams batches.

Private-ID produces an outer join. The output is a set of anonymized IDs on which both parties can later attach their own records locally. Private-ID formulation The key property of this ID spine is that neither party can tell whether a given record matched, but if two records did match they share the same ID.

Private-ID has three stages:

  1. Encrypt and exchange records. Parties C and P each hold two secret keys. Each encrypts its records as points on an elliptic curve using one key, shuffles, and sends them. The receiver makes two copies of each received encrypted record, encrypting one copy with one of its own keys and the other with both keys — leaving one set double-encrypted and one triple-encrypted.
  2. Calculate set difference. Party P re-shuffles and sends its double-encrypted records to C, who computes a symmetric set difference. The shuffling prevents P from learning which records matched, at the cost of breaking the link between encrypted and original records; the triple-encrypted copies restore that link later.
  3. Generate the ID mapping. The parties exchange the triple-encrypted records, undo the shuffles, and append those results to the records derived from the set difference to assemble the full ID spine.

PS3I delivers an inner join where the matching records’ values survive as additive shares rather than cleartext. It mixes elliptic-curve encryption for identifiers with Paillier encryption for the values being shared. Each record thus has both an identifier and one or more values. There are again three stages:

  1. Encrypt and exchange. C and P generate elliptic-curve secret keys, C generates a Paillier keypair, and the parties exchange Paillier public keys. Each party encrypts its records with one elliptic-curve key, shuffles, and sends them. On receipt, each encrypts the identifiers again with its own key, leaving them double-encrypted and ready for matching.
  2. Calculate the intersection. P re-encrypts identifiers with its key, then for each record homomorphically subtracts a random number from the value using C’s Paillier public key. Those random numbers become additive shares for C’s values. P sends everything to C, who matches on the double-encrypted identifiers. For every match, C homomorphically subtracts its own random number under P’s public key, producing symmetric shares for P’s values.
  3. Output the shares. C decrypts the values received from P to obtain its share of P’s values, and sends matched indices along with its encrypted values back to P. P decrypts those to obtain its shares of its own values and uses the matched indices to recover the random numbers that form the other half of C’s shares.

PS3I algorithm

Both designs avoid the all-or-nothing disclosure of classic PSI and the heavyweight circuit construction that generic private matching requires. Because each stage is embarrassingly parallel, matching runs scale far beyond what interactive circuit approaches manage: internal benchmarks show data sets with up to 100 million records can be matched within an hour. Once the private join is complete, the same aligned, encrypted structures can support any number of downstream MPC or HE computations without re-running the matching step.

Implementation and what's next

The protocols described above are implemented in Rust and released as open source at https://github.com/facebookresearch/Private-ID. Rust was selected for its memory safety guarantees and straightforward multithreading support. The implementations rely on the Curve 22519 elliptic curve from the Dalek library and the Paillier encryption scheme from the rust-paillier crate.

Performance testing covered large-scale inputs: Private-ID generates identifiers for 100 million records in 60 minutes, while PS3I produces additive shares for 5 million records in the same timeframe.

The broader goal is to reduce the amount of raw data that needs to be collected in the first place. Releasing this implementation is an early step toward building machine learning pipelines that operate on encrypted data end-to-end. Considerable work remains before this can be applied to production systems, but development in this direction is ongoing.