Estimating Incidental Collection in
Foreign Intelligence Surveillance

Large Scale Multiparty Private Set Intersection with Union and Sum


Instructions
 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.
Setup
 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. πŸ‡ΊπŸ‡Έ
X0 (Intelligence Community)
  • harbor.1305@email4.com
  • stove1027@email1.com
  • wheel_1268@email4.com
  • about.1774@email2.com
  • stadiu_1846@email1.com
X1 (Email Service 1)
  • stove1027@email1.com πŸ‡ΊπŸ‡Έ
  • badge1672@email1.com πŸ‡ΊπŸ‡Έ
  • sick_1423@email1.com πŸ‡ΊπŸ‡Έ
  • spider.838@email1.com πŸ‡ΊπŸ‡Έ
  • stadiu_1846@email1.com πŸ‡ΊπŸ‡Έ
X2 (Email Service 2)
  • crisp_637@email2.com πŸ‡ΊπŸ‡Έ
  • togeth.1008@email2.com πŸ‡ΊπŸ‡Έ
  • tree_1277@email2.com πŸ‡ΊπŸ‡Έ
  • old_955@email2.com πŸ‡ΊπŸ‡Έ
  • about.1774@email2.com πŸ‡ΊπŸ‡Έ
X3 (Email Service 3)
  • centur.1733@email3.com πŸ‡ΊπŸ‡Έ
  • diagra405@email3.com πŸ‡ΊπŸ‡Έ
  • sign_1692@email3.com πŸ‡ΊπŸ‡Έ
  • torch_548@email3.com πŸ‡ΊπŸ‡Έ
  • april.249@email3.com πŸ‡ΊπŸ‡Έ
Protocol
  The Intelligence Community generates a random blinding key and blinds its input table as elliptic curve points in M.
​
M
  • 1a5ad2351a0c77e9cdb549bbf36d4e5b5f45fa76f64155a624707bbd69be2514
  • c4a6cb95af7f129eed69b9e2141af993a94eeda9df7bab1c9e94df911c3cec1f
  • 58368eb9e362940649dbdb1a203fce07695544df3b7c99c84e203b1e426af27a
  • 7e3e1e98887d624b296ac7d4550291b2e75e6ca60c34517fb5bf829e6a885718
  • f887177c8382e58b1fc1b6a0662b8dd2df9b99519c3334dcedfd519c8b99c35f
 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.
M
  • 1a5ad2...be2514
  • c4a6cb...3cec1f
  • 58368e...6af27a
  • 7e3e1e...885718
  • f88717...99c35f
R1
  • ae1e95...d72b51 & b80e34...1d8475
  • 12f9bf...187420 & 20644e...0cb143
  • 946e80...8e1b28 & 46f916...387145
  • a2473d...01e90d & 188b3b...e2f560
  • ac0627...76dc74 & 7cb520...a3b86d
R2
  • 10f82b...1e3e71 & 9e853e...dae124
  • 4c57c4...883730 & 5ab9bc...f38966
  • ee8f20...752420 & 1a9484...71d61e
  • 307219...91080b & f8efa6...34a654
  • 28afee...20ec39 & 206f2e...37092c
R3
  • 16b2cb...cce16e & d087b4...5a1402
  • 92ca69...eac424 & baa178...a7a82d
  • 009e96...285430 & ca7c7a...590a78
  • 6a710e...e38d79 & facdbc...514d78
  • ee68ba...528f59 & 8a3f8b...662025
 Email Service 3 uses M, R3 to build a shuffled and encrypted table B.
M
  • 1a5ad2...be2514
  • c4a6cb...3cec1f
  • 58368e...6af27a
  • 7e3e1e...885718
  • f88717...99c35f
R (created by Service 3)
  • 16b2cb...cce16e & d087b4...5a1402
  • 92ca69...eac424 & baa178...a7a82d
  • 009e96...285430 & ca7c7a...590a78
  • 6a710e...e38d79 & facdbc...514d78
  • ee68ba...528f59 & 8a3f8b...662025
B
  • 16b2cb...cce16e & 4f2bfa...cb183c
  • ee68ba...528f59 & 63a32a...094f0c
  • 6a710e...e38d79 & 835fcc...5db4fa
  • 92ca69...eac424 & 929ffb...f24d5e
  • 009e96...285430 & 7d30cf...9e9a7f
 Intelligence Community computes the intersection size using B and the blinding key .
​
B
  • (16b2cb...cce16e, 4f2bfa...cb183c)
  • (ee68ba...528f59, 63a32a...094f0c)
  • (6a710e...e38d79, 835fcc...5db4fa)
  • (92ca69...eac424, 929ffb...f24d5e)
  • (009e96...285430, 7d30cf...9e9a7f)
Result
  • Not matched
  • Matched πŸ‡ΊπŸ‡Έ
  • Matched πŸ‡ΊπŸ‡Έ
  • Matched πŸ‡ΊπŸ‡Έ
  • Not matched
​
No participant learns any other information.