In our everyday life, sharing of electronic information among mutually distrustful parties increases rapidly. Naturally, this raises important privacy concerns with respect to the disclosure and long-term safety of sensitive content. In this area, an interesting problem is to compute intersection of private data sets of two mutually dishonest entities. A few relevant applications are presented below:
Government tax authority wants to detect whether any suspected tax evaders have accounts with a certain foreign bank and, if so, obtain their account records. The bank’s domicile forbids wholesale disclosure of account holders while the tax authority cannot disclose its list of suspects;
Two national law enforcement bodies (e.g., IND’s CBI and USA’s FBI) seek to know the list of common terrorist suspects from their respective databases, while they are not allowed to reveal the whole list ot each other;
A detective agency may want to verify whether a given biometric appears on a government watch-list. Note that privacy of biometric owner has to be preserved if no matches found, while at the same time, unrestricted access to the watch-list cannot be approved.
Private set intersection (PSI) can be utilized to solve the aforementioned problems. It is a two-party cryptographic protocol where each party engages with their private sets. On completion of the protocol either only one of the participants learns the intersection and other learns nothing, yielding one-way PSI or both of them learn the intersection, yielding mutual PSI (mPSI). On the other hand, if the participants wish to determine the cardinality rather than the intersection then that variant of PSI is known as Private set intersection cardinality (PSI-CA). Similar to PSI, it can be divided into two types: one-way PSI-CA and mutual PSI-CA (mPSI-CA).