Prism: Privacy-Preserving and Verifiable Set Computation Over Multi-Owner Secret Shared Outsourced Databases

Private set computation over multi-owner databases is an important problem with many applications - the most well studied of which is private set intersection (PSI). This article proposes Prism, a secret-sharing based approach to compute private set operations (i.e., intersection and union, as well as aggregates such as count, sum, average, maximum, minimum, and median) over outsourced databases belonging to multiple owners. Prism enables data owners to pre-load the data onto non-colluding servers and exploits the additive and multiplicative properties of secret-shares to compute the above-listed operations. Prism takes (at most) two rounds of communication between non-colluding servers (storing the secret-shares) and the querier for executing the above-mentioned operations, resulting in a very efficient implementation. Prism also supports result verification techniques for each operation to detect malicious adversaries. Experimental results show that Prism scales both in terms of the number of data owners and database sizes, to which prior approaches do not scale.