Efficient Private Set Intersection Cardinality Protocol in the Reverse Unbalanced Setting

Private set intersection cardinality (PSI-CA) is a variant of private set intersection (PSI) that allows two parties, the sender and the receiver, to compute the cardinality of the intersection without leaking anything more to the other party. It’s one of the best-studied applications of secure computation, and many PSI-CA protocols in balanced or unbalanced scenarios have been proposed. Generally, unbalanced scenario means that the private set size of the receiver is significantly smaller than that of the sender. This paper mainly focuses on a new scenario in which the receiver’s set size (client) is much larger than that of the sender (server) called the reverse unbalanced scenario. We study PSI-CA protocols that are secure against semi-honest adversaries, using the Hash-Prefix filter to effectively reduce the computation and communication overhead. We greatly optimize the previous unbalanced PSI-CA protocol and construct a reverse unbalanced PSI-CA protocol. In addition, we introduce private information retrieval (PIR) to resist the privacy leakage of the Hash-Prefix filter. By implementing all protocols on the same platform, we compare the protocols’ performance theoretically and experimentally. Combined with the Cuckoo filter, elliptic curve and multi-threading, the computational and communication efficiency of our protocol is 26.87 × and 8.48 × higher than the existing unbalanced PSI-CA protocols. By setting sets with significant differences in size, we also prove the feasibility of our protocol in anonymous identity authentication.