4
$\begingroup$

Typically, Private Set Intersection (PSI) protocols let you learn the subset of items on each party's dataset that are in the intersection. The problem in this case is a relaxation of these kind of constructions. I would like to learn only the number of elements on the intersection.

I could achieve this by using proxy re-encryption on a 2-party setting, however it is non-trivial (at least to me) to do the same on an n-party setting without disclosing the intersection of any parties subset.

I wonder if this problem has a specific name and whether it has been studied before (some literature you can point me to). Any idea on how to achieve this is also welcome.

$\endgroup$
3
$\begingroup$

This problem was studied under the name of private set-intersection cardinality (PSI-CA) by De Cristofaro et al. They give protocols for the two-party case both in the honest-but-curious and malicious setting, and the complexity grows only linearly in the size of the sets. A result for the multi-party case was given by Egert et al. using Bloom Filters.

In case you are interested in only testing whether two sets are disjoint without revealing anything else then the problem has been studied by Kiayias and Mitrofanova and under the name private intersection predicate evaluation.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! this is exactly what I was looking for. If you have any recommendations for the multiparty case of PSI-CA, I am all ears! I $\endgroup$ – DaWNFoRCe May 19 at 6:38
  • $\begingroup$ Added one result for the multi-party case. I would recommend going through google scholar citations of these papers if you are interested in more recent results. $\endgroup$ – Occams_Trimmer May 19 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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