Secure and scalable private set intersection for large datasets

A method comprising performing, by a first party computing system:

• receiving a private database table join query, the private database table join query identifying one or more first database tables and one or more attributes;
• retrieving the one or more first database tables from a first party database;
• determining a plurality of first party join keys based on the one or more first database tables and the one or more attributes;
• tokenizing the plurality of first party join keys, thereby generating a tokenized first party join key set, wherein the tokenized first party join key set comprises a plurality of first party tokens;
• generating a plurality of tokenized first party subsets by assigning each first party token of the plurality of first party tokens to a tokenized first party subset of the plurality of tokenized first party subsets using an assignment function;
• for each tokenized first party subset of the plurality of tokenized first party subsets:
• performing a private set intersection protocol with a second party computing system using the tokenized first party subset and a tokenized second party subset corresponding to the second party computing system, thereby performing a plurality of private set intersection protocols and generating a plurality of intersected token subsets;
• combining the plurality of intersected token subsets, thereby generating an intersected token set;
• detokenizing the intersected token set, thereby generating an intersected join key set;
• filtering the one or more first database tables using the intersected join key set, thereby generating one or more filtered first database tables;
• receiving, from the second party computing system, one or more filtered second database tables;
• and
• combining the one or more filtered first database tables and the one or more filtered second database tables, thereby generating a joined database table.

A first party computing system comprising:

• a first processor;
• and
• a first non-transitory computer readable medium coupled to the first processor, the first non-transitory computer readable medium comprising code, executable by the first processor for implementing a method comprising:
• tokenizing a first party set of data records, thereby generating a tokenized first party set, wherein the tokenized first party set comprises a plurality of first party tokens;
• generating a plurality of tokenized first party subsets by assigning each first party token of the plurality of first party tokens to a tokenized first party subset of the plurality of tokenized first party subsets using an assignment function;
• for each tokenized first party subset of the plurality of tokenized first party subsets:
• performing a private set intersection protocol with a second party computing system using the tokenized first party subset and a tokenized second party subset corresponding to the second party computing system, thereby performing a plurality of private set intersection protocols and generating a plurality of intersected token subsets;
• combining the plurality of intersected token subsets, thereby generating an intersected token set and
• detokenizing the intersected token set, thereby generating an intersected set of data records.