Unbalanced Private Set Union with Reduced Computation and Communication

We consider a protocol allowing a whistleblower to report an alert to an institution. The institution is expected to have much more computational resources than the whistleblower, who might only use a phone to communicate. The expected security in such a protocol is the following: The institution should not learn which data are common to its data set and the whistleblower's, because it could leak some clue on the identity of the whistleblower and compromise its anonymity. Also, the whistleblower should not learn anything from the data owned by the institution, so in particular, it should not learn which data the institution already had. To realize this, a possibility is to use an unbalanced private set union protocol (UPSU), where a receiver inputs a large data set and a sender inputs a small data set. The protocol should output to the receiver the union of the two sets, without learning anything on the intersection of the sets, while the sender should not learn anything. Our main goals in the conception of an UPSU are to achieve a communication volume that is linear in the size of the small set, and a computation cost for the sender independent of the size of the receiver's set. We reach those goals using efficient homomorphic algorithm on polynomials. Up to our knowledge, we present the first UPSU in which the communication volume is independent of the size of the receiver's set.