Answer

The verified solution is complete and written to ~/psi-ca/SOLUTION.md (self-contained, with the full runnable source appended). Here is the solution.

---

Fixing js-private-set-intersection-cardinality-leak

Environment: Node 20+ (browser-compatible primitives) · Language: JavaScript Artifact: psi-ca.js (library) · test.js (18 tests) · demo.js (end-to-end session)

TL;DR

A naive browser PSI-CA implementation (clientSet.filter(x => serverHashes.has(sha256(x)))) leaks membership four independent ways and is trivially manipulable by the relay:

#	Root cause	Fix
A	Deterministic, unblinded hashing of identifiers	Blinded 2HashDH OPRF — server sees only H(x)·r, never x
B	Exact cardinality returned every query	Laplace noise + cumulative ε-budget (pure DP)
C	Transcript not bound to a session/order	HMAC-SHA256 hash-chained authenticated channel
D	No commitment to server input/key	Commit-before-blind Merkle roots + batched Chaum–Pedersen DLEQ
E	Full set re-materialised every update	Sparse Merkle tree, O(depth) incremental add/remove

1. Root-cause analysis

The vulnerable baseline leaks because:

• A — unblinded deterministic hashes. Identifiers are low-entropy (emails, IDs). Anyone with the public hash can enumerate the space offline. Hashing is not encryption and not blind.
• B — exact cardinality per query. Seeing c_t and c_{t+1} tells you whether one element was added/removed (±1) or nothing changed. Repeated answers reconstruct the set by difference; cardinality leakage is composable and unbounded in the number of queries.
• C — no transcript binding. Without session/order binding a malicious server or middlebox can replay an old OPRF response, reorder frames so the client pairs the wrong values, drop the server's token frame to shrink the count silently, or bit-flip payloads.
• D — no input/key commitment. A malicious server can choose its set after seeing the client's blinds, and can answer element i under a different key k_i; the client cannot detect it.
• E — no verifiability. A server can simply return any number.
• F — memory/perf. Re-hashing full sets on every update is O(n+m) (or O(n·m)), and the commitment is order-dependent.

2. The exact fix

Threat model: client holds X; server holds Y and secret k. Both semi-honest about inputs, but the server's evaluations are verified. The relay is fully adversarial (reorder/replay/drop/tamper). Goal: the client learns at most a DP boolean for X ∩ Y ≠ ∅, nothing else about Y; the server learns nothing about X beyond its size.

2.1 Blinded 2HashDH OPRF — kills A

h2q(x)  = SHA256("PSI-OPRF-H2C-v1\0" || x) mod Q      // random oracle
H(x)    = G^h2q(x) mod P
B       = H(x)^r          (client, r uniform)          // blind
Z       = B^k             (server)                     // evaluate
F       = Z^(r^-1) = H(x)^k                            // unblind
token   = SHA256("PSI-OPRF-FINAL-v1\0" || F)           // 256-bit token

The server sees only B = G^{h(x)·r}, uniformly random and independent of x; the client has no OPRF oracle for unsubmitted y, so nonmatching tokens are pseudorandom. Nonmatching values are never revealed.

2.2 Batched Chaum–Pedersen DLEQ — kills D/E

For all pairs (H_i, Z_i), one proof shares a single nonce v:

c = H(G, K, {H_i}, {Z_i}, G^v, {H_i^v});  s = v + c·k mod Q
verify: G^s·K^(−c) and H_i^s·Z_i^(−c) reproduce c

One proof binds every evaluation to the same k (~3n exponentiations). Mixed keys fail.

2.3 Commit-before-blind + canonical token commitment — kills C/D

Before any blind is revealed, the server publishes K plus two Sparse-Merkle roots: setRoot (opaque) and tokenRoot over its sorted derived tokens. The client rebuilds the token tree from the received frame and checks the root — order-independent, and any dropped/substituted token changes it.

2.4 Authenticated hash-chained transcript — kills C

Every frame is {sessionId, seq, payload, mac} with mac = HMAC(key, sessionId‖seq‖chain‖payload) and chain = SHA256(chain‖mac). The receiver enforces seq == expected, recomputes the MAC, then advances the chain. Tamper → MAC mismatch; replay → stale seq/session; reorder/drop → seq gap.

2.5 Differential privacy + budget — kills B

noisy = max(0, round(c + Laplace(0, 1/ε)))   // c never released raw

Each release charges ε. By sequential composition Σε_i ≤ ε_total; when exhausted the query is refused (checked before spending CPU).

2.6 Sparse Merkle tree — kills F

256-bit fixed depth, positioned by SHA256(value), storing only populated nodes. add/remove touch one root-to-leaf path, root is order-independent.

3. Files & commands

psi-ca/
├── psi-ca.js   # OPRF, batched DLEQ, SparseMerkleSet, SecureChannel,
│               # PrivacyBudget, psiCardinality, tokenSetRoot
├── test.js     # 18 verification tests (node --test)
└── demo.js     # end-to-end session

cd psi-ca
node demo.js
node --test test.js

4. Verification

$ node --test test.js
# tests 18
# pass 18
# fail 0

Covers: exact cardinality; disjoint/identical sets; nonmatching tokens not derivable; per-query re-blinding; DLEQ accept/forge; key-substitution rejection; tamper/replay/reorder/drop/cross-session detection; order-independent incremental Merkle add+remove; token-commitment drop/substitution detection; DP budget exhaustion; Laplace bias/scale; boolean release.

$ node demo.js
=== honest PSI-CA session ===
query 1: true=2 noisy=7 intersect=true  budget=0.25/1.00 digest=df57796aea1aeb7b…
query 2: true=2 noisy=0 intersect=false budget=0.50/1.00 digest=1c1bfa8b3a3a416f…
query 3: true=2 noisy=1 intersect=true  budget=0.75/1.00 digest=993f99c9afe2dfe8…
query 4 refused: PrivacyBudget: budget exhausted (query refused)

=== tamper / replay / drop detection ===
replay rejected: SecureChannel: unexpected sequence 0, expected 1 (reorder/replay/drop)
tamper rejected: SecureChannel: MAC mismatch (tampered transcript)
drop/reorder rejected: SecureChannel: unexpected sequence 2, expected 1 (reorder/replay/drop)

Query 2 (true=2 → noisy=0 → false) is the intended privacy/utility trade-off at ε = 0.25; the budget stops repeated-query differencing.

5. Cryptographic assumptions

Guarantee	Assumption
OPRF obliviousness	One-More-DH / DDH; uniform r ⇒ uniform B
Token pseudorandomness	CDH + SHA-256 as random oracle
Batched DLEQ soundness	Discrete-log/CDH + Forking Lemma in the ROM
Transcript integrity	HMAC-SHA256 is SUF-CMA
Set/token commitment	SHA-256 collision resistance
Session key	Authenticated key agreement (TLS 1.3 / signed ECDH)
Bounded repeated-query leakage	Pure ε-DP + sequential composition

Prime-order group: RFC 3526 modp14 (2048-bit) by default; production may use P-256/ristretto255.

6. Limitations

• Client learns the true count internally (DP bounds what is released).
• Server learns |X| (number of blinds) unless padded.
• Client can tell which of its own elements matched; true cardinality-only needs a private counting step (threshold OPRF / garbled circuit).
• PSI cannot stop a party lying about its own set; commitments stop mid-session adaptive change.
• JS BigInt is not constant-time — use WASM/native or WebCrypto curve code for a strong side-channel model.

---

The complete, self-contained document including the full source of psi-ca.js, test.js, and demo.js is at ~/psi-ca/SOLUTION.md.

# Evidence
- Problem class: js-private-set-intersection-cardinality-leak
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-10-05T04:17:05.458Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build a browser-side protocol for computing whether two parties\u2019 large identifier sets intersect without revealing nonmatching values, under a server that can reorder, replay, and selectively drop messages. The design must bound leakage across repeated queries, detect transcript tampering, and remain practical with memory limits and incremental updates; explain which cryptographic assumptions make the guarantees possible.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-private-set-intersection-cardinality-leak", "provider": "openrouter", "solved_at": "2026-10-05T04:17:05.459Z", "version": "20"}