Private Set Intersection Demo

Technical Notes: GC-Backed PSI with Keyed BLAKE3

This demo implements a small, self-contained private set intersection (PSI) core and a Yao-style garbled circuit (GC) equality check, both compiled to WebAssembly. The browser UI is just a thin wrapper around a C library that:

• Hashes each input string with a keyed BLAKE3-based pseudorandom function.
• Performs PSI in two ways:
  • a hash-only, naive O(n²) comparator, and
  • a GC-backed equality comparator built from AND/XOR/NOT gates.

Set Model and Hashing

Let Alice and Bob hold finite sets of strings: \(A = \{a_0,\dots,a_{n-1}\}\), \(B = \{b_0,\dots,b_{n-1}\}\). We want the indicator mask \[ m_i = \begin{cases} 1 & \text{if } \exists j : a_i = b_j \\ 0 & \text{otherwise} \end{cases} \] so that the intersection is \(I = \{ a_i \mid m_i = 1 \}\).

Direct string comparison is replaced by hashing into a fixed-length digest space. In the C core, each string is mapped to a 128-bit digest using keyed BLAKE3 in MAC / PRF mode, truncated to 16 bytes:

// Conceptual model for each element s
H_k(s) = BLAKE3_keyed(k, s)[0..15]  // 16-byte (128-bit) digest

A' = { H_k(a_0), …, H_k(a_{n-1}) }
B' = { H_k(b_0), …, H_k(b_{n-1}) }

In the naive path, the PSI mask is then \[ m_i = \bigvee_{j=0}^{n-1} [\,H_k(a_i) = H_k(b_j)\,]. \] In the GC path, the same digests feed a Boolean equality circuit that computes a single bit per pair \((i,j)\).

Bit-Level Equality Circuit

Fix an element bit width \(k = \texttt{elem_bits}\). Each 16-byte digest is treated as a vector of bits: \[ A_i = (a_i^{(0)},\dots,a_i^{(k-1)}),\quad B_j = (b_j^{(0)},\dots,b_j^{(k-1)}). \] For each pair \((A_i,B_j)\) the circuit computes an equality bit \(\mathsf{eq}(A_i,B_j) \in \{0,1\}\) as:

// Bitwise XOR and equality flags
x_t  = a_i^{(t)} XOR b_j^{(t)}      for t = 0,…,k-1
e_t  = NOT(x_t)                     // e_t = 1 iff bits match

// Full equality = AND of all per-bit equalities
eq   = e_0 AND e_1 AND … AND e_{k-1}

In circuit terms:

• \(k\) XOR gates to compute \(x_t\),
• \(k\) NOT gates to compute \(e_t\),
• and a length-\(k\) AND chain to fold all \(e_t\) into a single output bit.

The GC backend allocates wires for all input bits and internal results, then builds this gate pattern for arbitrary elem_bits, not just 128; the output wire carries eq ∈ {0,1} for the given pair of digests.

Yao Garbled Circuits and Free-XOR

Yao’s protocol encodes each wire \(w\) with two random labels \(L_w^0, L_w^1 \in \{0,1\}^{\lambda}\), where \(\lambda\) is the label length (here 128 bits). Instead of sending bits, the garbler sends labels; correctness and privacy follow from the fact that labels look random unless the evaluator has the right keys.

This implementation uses the classic free-XOR optimization: pick a single global offset \(\Delta \in \{0,1\}^{\lambda}\) with the least significant bit set, and enforce

// Label relationship for every wire w
L_w^1 = L_w^0 XOR Δ,     with  L_w^0 chosen pseudorandomly

// "permute bit" = LSB of first byte, used to index table rows
permute_bit(L_w^b) = L_w^b[0] & 1

For XOR gates, this makes garbling free: \[ L_{\text{out}}^0 = L_{in0}^0 \oplus L_{in1}^0,\quad L_{\text{out}}^1 = L_{\text{out}}^0 \oplus \Delta, \] so the evaluator just XORs input labels and does not need any ciphertexts at all for XOR gates.

Gate Encryption with Keyed BLAKE3

Non-XOR gates (AND / NOT) still have a four-row garbled table. For each gate index \(g\) and each pair of input bits \((a,b) \in \{0,1\}^2\), we choose the correct output label \(K_{\text{out}} = L_{\text{out}}^{f(a,b)}\), where \(f\) is the gate’s truth table. Then we encrypt it under a PRF derived from the input labels:

// Conceptual pseudocode for a non-XOR gate row
row      = (permute_bit(K_a) << 1) | permute_bit(K_b)
keystream = BLAKE3_keyed(GC_PRF_KEY, K_a || K_b || gate_index || row)
cipher[row] = K_out XOR keystream

Here GC_PRF_KEY is a fixed 32-byte key; BLAKE3 in keyed mode acts as a pseudorandom function on the concatenated labels and gate metadata. At evaluation time, the evaluator:

1. Looks up the row using permute bits of the input labels.
2. Recomputes the same keystream with BLAKE3.
3. XORs the ciphertext with the keystream to recover the output label.

Because the evaluator only ever decrypts exactly one row per gate, even a simple one-time-pad style encryption (XOR with keystream) is secure in this setting.

From Equality Bits to PSI

The PSI GC backend conceptually computes, for each element of Alice’s digest set \(A'_i\): \[ m_i = \bigvee_{j=0}^{n-1} \mathsf{eq}(A'_i, B'_j), \] where \(\mathsf{eq}\) is implemented as the GC equality circuit described above. In this demo, all of that happens in a single process:

• The browser hashes strings to digests using a BLAKE3-based WASM helper.
• The C core runs PSI in both “hash-only” and “GC-backed” modes on those digests.
• The JavaScript layer compares the two masks to ensure they match.

In a full two-party deployment, Alice and Bob would hold their inputs on separate machines. They would then combine:

• Oblivious transfer (OT) or similar to deliver input labels without revealing bits, and
• the same garbled equality circuit and keyed BLAKE3 PRFs as used here.

The result is that each party learns only the intersection of their sets, and nothing else about the other party’s inputs, while the web demo here exposes a single-process simulation that makes performance and correctness visible.