What is privacy set intersection?

Private set intersection (PSI) is a privacy-preserving protocol that allows two parties to determine the intersection of two private sets without revealing any information about the individual elements in those sets. In this way, the two parties can calculate the common elements between two sets, but neither party can determine the individual components in the other party's set. PSI is used in various applications, such as secure information sharing, privacy-preserving record linkage, and secure set operations, to ensure the privacy of sensitive data while still allowing for meaningful computation.

Why is privacy set intersection important?

The importance of PSI lies in its ability to protect sensitive information while still allowing for meaningful computation. In many applications, such as secure information sharing, privacy-preserving record linkage, and secure set operations, PSI can be used to ensure that sensitive data remains confidential and protected from unauthorized access.

For example, imagine two organizations that want to determine if their customers are common to both organizations. If they were to share their customer lists, this would expose sensitive information about their customers to another organization. With PSI, organizations can calculate the intersection of their customer lists without revealing individual customer data to each other.

How does privacy set intersection technically work?

PSI uses cryptographic techniques to securely compute the intersection of two private sets without revealing any information about the individual elements in those sets. Here's a high-level overview of the process:

1. Preprocessing: The parties involved generate cryptographic representations of their private sets. These representations are used to hide the actual values in the sets and make it difficult for an adversary to determine the individual elements.
2. Comparison: The cryptographic representations of the two sets are compared to determine the intersection. The comparison is performed in such a way that the actual elements in the sets remain confidential.
3. Output: The final result of the PSI protocol is the size of the intersection (i.e., the number of common elements) or a representation of the common elements (such as a hash or an encrypted representation).

The specific techniques used for the preprocessing, comparison, and output phases can vary depending on the particular implementation of the PSI protocol. Some common techniques include secure sketching, secure multi-party computation, and homomorphic encryption.

The security of PSI protocols relies on the underlying cryptographic primitives and the correct implementation of the protocol. Therefore, it's important to thoroughly evaluate the security of a PSI implementation before deploying it in a sensitive environment.

‍