Privacy-Enhancing Cryptography PEC

Private Set Intersection (PSI), and more generally Private Set Operations (PSO), can be used in myriad situations of privacy-preserving interactions. For example:

• Private contact discover: two parties can determine which contacts in their private contact lists are common between the two parties.
• Identifying double claims: Two mutually-exclusive administrative organizations can find which users are users claiming benefits in both organizations, when potentially that double claim is illegitimate, but the privacy of each list should be preserved.
• Private password breach . By using single-output PSI, a user can check which passwords may be privately listed in a database of leaked passwords. The user does not want to reveal the original passwords, and the server does not want to reveal the database entries, but the server is willing to let the user learn whether a small number of passwords are present in the database.

The requirements of a privacy-preserving application may require the use of variant versions of basic PSI. For example:

• Committed PSI/PSO: If the input and/or output of the private set operation (PSO) are committed (in a cryptographic sense: hiding and binding, and possibly non-malleably), then they can verifiably relate to other executions. For example, an application may require Alice to prove that the private set she is using, when performing a PSI with Bob, is the same set that was used in a previous interaction with Cai.
• Private Set Union: Two or more organization can jointly compute the union of several privates lists. Each party that learns the output does not get to know which elements were common with the other party.

More general cases:

• Linked records. The techniques used in PSI/PSO are foundational to broader more general problems of linkage, where the intended output is neither the elements of or a statistics from an output set, but rather a linked element. For example, while a basic PSI on two private lists of social security numbers (SSN) would result in a subset of SSN values, the application may instead return as output only an aggregate sum of the wages linked to the intersecting SSN values.
• PSI/PSO with secret-shared input. If the inputs are secret-shared, as in the case of resulting from a previous MPC, the final step of the interaction may be to compute a set operation.
• Private Information Retrieval (PIR). In PIR, a client is allowed to retrieve an indexed value from a database held by a server, without the server learning what the query was. In the illustration, DD is a key-value dictionary, such that DiDi​ is the value associated with the key (aka label) ii.

The PEC project draws PSI/PSO context from various informative initiatives:

1. WPEC 2024: The NIST Workshop on Privacy-Enhancing Cryptography (WPEC) hosted the "First PSI Day" (2024-Sep-24), which included 10 external talk on PSI related talks.
2. PEC-STPPA8 (2025): The 8th event of the STPPA series (on 2025-Sep-18) included an invited talk about PSI Implementations.
3. PEC-STPPA2 (2021): The 2nd event of the STPPA series (on 2021-Apr-19) included an invited talk with a technical overview about PSI.

Private Set Intersection (PSI)

PSI allows two parties to compute the intersection of their sets, without disclosing the non-intersecting elements.

If Alice has set {p,r,i,v,a,t,e} and Bob has {s,e,c,r,t}, then Alice gets {r,t,e}.

There are interesting/useful generalizations. For example:

• For PSI between multiple parties. The acceptance criterion may be the presence of an element in at least a threshold number of parties.
• Set-operations different from intersection,
• Taking into account the multiplicity of elements in each set / list.
• Applying a function to each element of the output set.
• Applying a function to the output set (e.g., counting)