2PC Private Set Intersection Optimized for asymmetrically sized sets [duplicate]

Question

I am researching some concepts of practical 2 party computation and was curious if anyone could point me to a research paper that is focused on private set intersection where one party has a very large set and the other has a comparatively small set. Specifically, a user has a small set and the server has a large set. Since the server will handle thousands or millions of requests, I am more concerned about the performance for the server.

The specific use case that I had in mind is contact discovery. Meaning, a user wants to know who else is using a service but does not want to disclose their contacts to the server in plain text. Ideally the server does not learn the outcome of the intersection. At a minimum the server should only learn the size of the users contact list and the results of the intersection.

I found this paper that appears to be a breakthrough in performance but it's benchmarks are based on two sets of equal size. Is there existing research on a PSI that is optimized for non-equal set size?

Answer 1

It is easy to observe that any secure protocol must touch every bit of both parties' inputs -- otherwise it's not secure.

However recent work has shown that you can amortize the protocol complexity over several runs, with state stored between the runs, so that not every execution will touch every bit. See here for the paper. It doesn't address set intersection directly, but since it covers a generic function it applies to your case.