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.
5
3
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.
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 .