Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
cleaned up comments – mikeazo Jan 13 '14 at 17:47

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.