XYZ: Cryptography and Private Set Intersection Protocols

Monografiak

1The problem

Two parties, Alice and Bob, each hold a private set. Alice holds $X$ with $n$ elements and Bob holds $Y$ with $m$ elements. Alice wants to compute

X \cap Y = \{\, z : z \in X \text{ and } z \in Y \,\}

(1)

She must learn nothing about the elements of $Y$ outside the intersection, and Bob must learn nothing about $X$ at all. The only things that may leak are the set sizes $n$ and $m$ .

The problem shows up wherever two organisations or devices need to match records they are not allowed, or not willing, to share:

Contact discovery. A messaging app wants to tell you which of your contacts already use it without uploading your address book.
Compromised credentials. A browser checks whether your password appears in a breach corpus without disclosing the password.
Advertising measurement. An advertiser and a publisher count how many people who saw an ad later bought the product, without exchanging customer lists.
Public health and finance. Institutions cross-check watch lists or patient registries under strict data-protection rules.

2Why hashing is not enough

The usual first attempt is for Bob to send $H (y)$ for every $y \in Y$ , where $H$ is a cryptographic hash function such as SHA-256. Alice hashes her own elements and compares. Hashes cannot be inverted, so this looks private.

It is not. A hash hides its input only when the input is hard to guess. Phone numbers, e-mail addresses and national identifiers come from small, enumerable universes. With a universe $U$ , Alice can recover all of $Y$ by brute force at a cost of

|U| \text{ hash evaluations;}\quad |U| \approx 10^{10} \text{ for phone numbers.}

(2)

Ten billion SHA-256 evaluations take a few seconds on a single modern GPU. Salting doesn't help, because both sides need the same salt for the comparison to work. Hashing hides structure. It doesn't hide low-entropy data.

3Preliminaries

Let $𝔾$ be a cyclic group of prime order $q$ with generator $g$ . In practice this is an elliptic-curve group such as ristretto255 or P-256. We also need a hash function $H : {0, 1}^{*} \to 𝔾$ that maps arbitrary strings to group elements. It is standardised as hash-to-curve in RFC 9380 [9].

Definition 1 (Decisional Diffie–Hellman). For uniformly random $a, b, c \in ℤ_{q}$ , no efficient algorithm can distinguish

(g, g^a, g^b, g^{ab}) \;\approx_c\; (g, g^a, g^b, g^c)

(3)

where $\approx_{c}$ denotes computational indistinguishability.

Security is defined by comparison with an ideal world. In that world a trusted third party receives $X$ and $Y$ and returns $X \cap Y$ to Alice. A protocol is secure if anything a participant learns from a real run, it could also have computed from its own input and the ideal output. A semi-honest adversary follows the protocol but tries to learn more from the transcript. A malicious adversary may deviate arbitrarily.

4Diffie–Hellman PSI

The oldest PSI protocol traces back to Meadows [1] and to Huberman, Franklin and Hogg [2]. It rests on one algebraic fact: exponentiation in $𝔾$ commutes.

\bigl(H(x)^a\bigr)^b = H(x)^{ab} = \bigl(H(x)^b\bigr)^a

(4)

Alice picks a secret $a$ and Bob a secret $b$ , both uniform in $ℤ_{q}$ . An element blinded by both exponents comes out the same whichever order the exponents were applied in. Without the exponents, however, a blinded value looks random. Figure 1 shows the exchange.

Sequence diagram between Alice and Bob in three steps. Step 1: Alice sends H(x) to the a for each x in X. Step 2: Bob returns each value raised to b in the same order, and sends H(y) to the b for each y in Y, shuffled. Step 3: Alice raises Bob's values to a and compares. — **Figure 1.** Message flow of Diffie–Hellman PSI. Alice sends one message and Bob replies once. The intersection is found locally by Alice in step 3.

Alice sends $u_{i} = H (x_{i})^{a}$ for each $x_{i} \in X$ .
Bob replies with $u_{i}^{b}$ in the original order, so Alice can tell which value belongs to which $x_{i}$ . He also sends $v_{j} = H (y_{j})^{b}$ for each $y_{j} \in Y$ , randomly permuted.
Alice computes $v_{j}^{a}$ . If $u_{i}^{b} = v_{j}^{a}$ for some $j$ , then $x_{i} \in X \cap Y$ .

Each party performs $n + m$ exponentiations, and the parties exchange $2 n + m$ group elements in total. Against semi-honest adversaries the protocol is secure under the DDH assumption when $H$ is modelled as a random oracle. Bob sees only values of the form $H (x)^{a}$ , which look random. Alice sees $H (y)^{b}$ for every $y$ , but she cannot test a guess $y^{'}$ without knowing $b$ . That closes the dictionary attack from §2.

The protocol fits in a page of code and needs only a standard elliptic-curve library. It still runs in production today, for example in Google's Private Join and Compute [7].

5PSI from oblivious pseudorandom functions

A pseudorandom function $F_{k}$ is a keyed function whose outputs look random to anyone without $k$ . It is oblivious (an OPRF) when two parties evaluate it together, with the following roles:

\underset{\text{Bob}}{(k)},\ \underset{\text{Alice}}{(x)} \;\longmapsto\; \underset{\text{Bob}}{(\bot)},\ \underset{\text{Alice}}{(F_k(x))}

(5)

Bob learns nothing and Alice learns only the output. PSI follows directly. Bob publishes ${F_{k} (y) : y \in Y}$ . Alice obtains $F_{k} (x)$ for each of her elements through the OPRF and checks for membership.

The Diffie–Hellman construction is itself an OPRF, standardised in RFC 9497 [10]:

F_k(x) = H'\bigl(x,\, H(x)^k\bigr)

(6)

Alice never reveals $x$ . She sends the blinded value $H (x)^{r}$ for a random $r$ , Bob applies his key to get ${(H (x)^{r})}^{k}$ , and Alice removes the blind by raising the result to $r^{- 1} mod q$ .

For very large sets, the fastest protocols avoid public-key operations on each element. Pinkas, Schneider and Zohner [4] built PSI from oblivious transfer extension, which turns a small number of public-key operations into millions of cheap symmetric ones. Kolesnikov et al. [5] recast this as a batched OPRF. Later work based on vector oblivious linear evaluation (VOLE) [8] reduces communication further. These protocols intersect sets of millions of elements in seconds on a fast network.

6PSI from homomorphic encryption

Freedman, Nissim and Pinkas [3] encode Alice's set as the roots of a polynomial:

P(z) = \prod_{i=1}^{n} (z - x_i) = \sum_{i=0}^{n} \alpha_i z^i

(7)

Alice encrypts the coefficients $α_{i}$ under an additively homomorphic scheme such as Paillier and sends them to Bob. Bob can evaluate the encrypted polynomial at his own points without decrypting anything. For each $y \in Y$ , with fresh randomness $ρ$ , he returns

\mathrm{Enc}\bigl(\rho \cdot P(y) + y\bigr)

(8)

If $y \in X$ then $P (y) = 0$ and Alice decrypts $y$ itself. Otherwise she decrypts a uniformly random value. Bucketing with hashing keeps the cost from growing as $n \cdot m$ .

Modern lattice-based homomorphic encryption makes this approach effective for unbalanced PSI, where a phone with a few hundred contacts queries a server holding hundreds of millions of records. Chen, Laine and Rindal [6] give a protocol whose communication is linear in the small set and only logarithmic in the large one.

7What PSI does not promise

PSI computes a function. It does not judge whether revealing that function's output is wise. Three limits are worth stating plainly:

Input choice is free. No protocol stops Alice from putting every phone number in a city into $X$ . The output then reveals exactly which of those numbers are in $Y$ . Deployments defend against this outside the cryptography: they cap set sizes, rate-limit queries, or attest the client.
Sizes leak. Standard protocols reveal $n$ and $m$ . Padding with dummy elements hides the true sizes at extra cost.
The output may be too much. Often only the size $| X \cap Y |$ (PSI-cardinality) or an aggregate over matched records (PSI-sum [7]) is needed. Asking for the narrower function is the cheapest privacy gain there is.

8Choosing a protocol

**Table 1.** The main PSI families compared qualitatively. Concrete performance depends on the implementation, the network and the security model.
Family	Core primitive	Communication	Best suited to
Diffie–Hellman [1] [2]	Group exponentiation	Linear, in group elements	Simplicity, low bandwidth, small to medium sets
OT / VOLE OPRF [5] [8]	Symmetric crypto + OT extension	Linear, small constants	Very large balanced sets on fast networks
Lattice HE [6]	Leveled homomorphic encryption	Linear in small set, logarithmic in large	Unbalanced: light client, huge server
Polynomial / Paillier [3]	Additive homomorphic encryption	Linear, in ciphertexts	Historical foundation; teaching

Diffie–Hellman PSI over a modern curve is the right default for most first deployments. It is easy to audit, it is built from standardised parts (RFC 9380, RFC 9497), and its cost is predictable. Move to OT- or VOLE-based protocols when the sets reach millions of elements, and to homomorphic encryption when one side is far smaller than the other.

XYZ

Abstract Laburpena