Fast Privacy-Preserving Top-k Queries Using Secret Sharing

摘要: Over the past several years a lot of research has focused on distributed top-k computation. In this work we are interested in following privacy-preserving problem. A set parties hold private lists key-value pairs and want to find disclose k with largest aggregate values without revealing any other information. We use secure multiparty computation (MPC) techniques solve problem design two MPC protocols, PPTK PPTKS, putting emphasis their efficiency. uses hash table condense possibly large sparse space keys probabilistically estimate keys. PPTKS multiple tables, i.e., sketches, improve estimation accuracy PPTK. evaluate our protocols using real traffic traces show that they accurately efficiently distributions IP addresses port numbers globally most frequent numbers.