<sc>Prism</sc> <underline>Pr</underline>ivacy-Preserving and Ver<underline>i</underline>fiable <underline>S</underline>et Computation over <underline>M</underline>ulti-Owner Secret Shared Outsourced Databases

Private set computation over multi-owner databases is an important problem with many applications &#x2014; the most well studied of which is private set intersection (PSI). This paper proposes <sc>Prism</sc>, a secret-sharing based approach to compute private set operations (<italic>i.e.</italic>, intersection and union, as well as aggregates such as count, sum, average, maximum, minimum, and median) over outsourced databases belonging to multiple owners. <sc>Prism</sc> 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. <sc>Prism</sc> 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. <sc>Prism</sc> also supports result verification techniques for each operation to detect malicious adversaries. Experimental results show that <sc>Prism</sc> scales both in terms of the number of data owners and database sizes, to which prior approaches do not scale.