client

Overview ¶

Package client for the client-side of the Private Set Intersection protocol.

In PSI, two parties (client and server) each hold a dataset, and at the end of the protocol the client learns the size of the intersection of both datasets, while no party learns anything beyond that (cardinality mode).

This variant of PSI introduces a small false-positive rate (i.e., the reported cardinality will be slightly larger than the actual cardinality. The false positive rate can be tuned by the server.

The protocol works as follows.

1. Setup phase

The server encrypts all its elements x under a commutative encryption scheme, computing H(x)^s where s is its secret key. The encrypted elements are then inserted in a Bloom filter, which is sent to the client in the form of a serialized protobuf. The protobuf has the following form:

{
  "num_hash_functions": <int>,
  "bits": <string>
}

Here, `bits` is a binary string.

2. Client request

The client encrypts all their elements x using the commutative encryption scheme, computing H(x)^c, where c is the client's secret key. The encoded elements are sent to the server as an array together with a boolean reveal_intersection that indicates whether the client wants to learn the elements in the intersection or only its size. The payload is sent as a serialized protobuf to the client and holds the following form:

{
  "reveal_intersection": <bool>,
  "encrypted_elements": [ H(x_1)^c, H(x_2)^c, ... ]
}

3. Server response

For each encrypted element H(x)^c received from the client, the server encrypts it again under the commutative encryption scheme with its secret key s, computing (H(x)^c)^s = H(x)^(cs). The result is sent back to the client as a serialized protobuf holding the following form:

{
  "encrypted_elements": [ H(x_1)^c, H(x_2)^c, ... ]
}

If reveal_intersection is false, the array is sorted to hide the order of entries from the client.

4. Client computes intersection

The client decrypts each element received from the server's response using its secret key c, computing (H(x)^(cs))^(1/c) = H(x)^s. It then checks if each element is present in the Bloom filter, and reports the number of matches as the intersection size.