Estimating Incidental Collection in
Foreign Intelligence Surveillance

Large Scale Multiparty Private Set Intersection with Union and Sum

 This example is a gross simplification. Please refer to the paper for the exact protocol.
 In this example, there are 4 participants: Intelligence Community, Email Service 1, Email Service 2, Email Service 3.
 For simplicity, all participants have input tables of the same size.
 Hover over each table to view a list of participants it is visible to.
 Random tables can be generated by selecting the table and intersection sizes below.

 Each participant builds an input table consisting of email addresses.
 Intelligence Community's input table X0 contains all addresses they incidentally collected emails to or from.
 Service providers' input tables X1, X2, X3 contain all email addresses believed to be controlled by users located in the U.S. 🇺🇸

  The Intelligence Community generates a random blinding key and blinds its input table as elliptic curve points in M.

 Email Service 1 uses M, X1 to build R1. Email Service 2 uses M, X2, R1 to build R2. Email Service 3 uses M, X3, R2 to build R3. R1, R2, and R3 contain two elliptic curve points in each row.

 Email Service 3 uses M, R3 to build a shuffled and encrypted table B.

 Intelligence Community computes the intersection size using B and the blinding key .

No participant learns any other information.