Search Vault
Single-keyword SSE · OXT conjunctions · public-key and fuzzy search · multi-user collusion
Executable searchable encryption across five query models: a symmetric encrypted index whose access pattern enables inference attacks, a bounded OXT conjunction whose cross-tokens change the leakage, public-key searchable tags whose exposed trapdoor enables offline keyword guessing, a gram-based fuzzy index whose typo recovery exposes query-neighborhood overlap, and a multi-writer/multi-reader construction whose iterative-testing trace enables collusion.
Live demo: https://systemslibrarian.github.io/crypto-lab-search-vault/
What It Is
An encrypted inverted index, built and searched in your browser, plus published attacks that turn its leakage back into queries. A bounded two-keyword OXT extension compares one structured conjunction with two independent SSE searches. A focused PEKS extension separates public sender, recipient, and server roles with real BLS12-381 pairings. A fuzzy-search lesson compares exact SSE with a deletion-gram candidate index and makes added similarity leakage executable. The final lesson separates writers from readers, propagates one colluding reader’s known label through a real pairing-based iterative-testing transcript, and compares that leak with a bounded two-server split.
The scheme is a single-keyword SSE construction in the Song–Wagner–Perrig (2000) / Curtmola–Garay–Kamara–Ostrovsky (SSE-1, 2006) style, with real primitives throughout:
| Value | Derivation | Primitive |
|---|
search token t_w | HMAC(K_prf, "token" ‖ w) | HMAC-SHA-256 (RFC 2104 / FIPS 198-1) |
posting key k_w | HMAC(K_enc, "posting" ‖ w) | HMAC-SHA-256 |
index address addr_i | HMAC(t_w, "address" ‖ i) | HMAC-SHA-256 |
| posting value | AES-256-GCM(k_w, docId), AAD = addr_i | AES-256-GCM (NIST SP 800-38D) |
| document body | AES-256-GCM(k_d, title ‖ body) | AES-256-GCM |
The SSE primitives run through WebCrypto. Keys are generated per session with crypto.getRandomValues, held in memory, and never persisted or transmitted.
The conjunctive extension. Exhibit 7 accepts exactly two distinct indexed keywords joined by AND. In isolated state, the naïve route issues two real existing-SSE queries and intersects both complete posting lists at the client. The bounded OXT route chooses the lower-frequency term s from client-only corpus knowledge (ASCII order breaks ties), walks only its flat addressed TSet, and tests the other term x against a sorted exact XSet of canonical RFC 9496 ristretto255 encodings:
XSet(w,id) = [F_X(w) F_I(id)]B
y(s,c,id) = F_I(id) / F_Z(s,c) mod l
xtoken(c) = [F_Z(s,c) F_X(x)]B
[y]xtoken = [F_I(id) F_X(x)]B
Five independent OXT-only keys feed length-framed HMAC-SHA-256 labels, HMAC-SHA-512-to-nonzero-scalar derivation, and AES-256-GCM identifier ciphertexts. TSet scalars use canonical 32-byte little-endian encodings, and every identifier has one fixed UTF-8 byte length so ciphertext length does not distinguish document identifiers. Each keyword list is CSPRNG-shuffled before its one-based counters are bound; all 55 TSet rows are shuffled again before server insertion so setup order does not expose list boundaries. XSet membership is exact, not a Bloom filter. This is a static two-term teaching adapter, not the original paper’s optimized TSet and not a transfer of its complete proof. RFC 9496 specifies the group encoding and operations; decisional Diffie–Hellman hardness is a separate explicit assumption.
The public-key extension. Exhibit 8 implements an algebra-preserving Type-3 BLS12-381 adaptation of Boneh–Di Crescenzo–Ostrovsky–Persiano PEKS (EUROCRYPT 2004). With e : G1 × G2 → GT, the recipient chooses x and publishes X = xP2. A sender with only X and keyword w samples fresh nonzero r, stores A = rP2 and B = H2(e(H1(w), rX)), and discards r. The recipient issues T_w = xH1(w); the server tests whether B = H2(e(T_w, A)). H1 is RFC 9380 hash-to-BLS12-381-G1 under a PEKS-specific domain, while H2 is SHA-256 over a domain-separated, length-framed 576-byte noble Fp12 coefficient encoding.
Bilinearity proves executable correctness: e(xH1(w), rP2) = e(H1(w), rX). It does not prove that the original symmetric-pairing BDH reduction transfers to this Type-3 adaptation. A precisely stated Type-3 hardness assumption and a separate formal reduction would be required; this lab supplies neither and makes no such security claim. The recipient, sender, server, and attacker are separate objects in one browser tab, not production network or process isolation.
The fuzzy-search extension. Exhibit 9 is a bounded adaptation of Li et al., IACR ePrint 2009/593, §§3.4–6 and Algorithm 2. At threshold d, every indexed word and query produces the set of relative-order-preserving subsequences obtained by deleting from zero through d characters. HMAC-SHA-256 turns each gram into a deterministic 32-byte trapdoor; every keyword–gram association carries an independently randomized AES-256-GCM payload bound to that trapdoor as associated data. The honest-but-curious server performs exact trapdoor lookups and returns encrypted candidate rows. Only the client decrypts candidate keywords, computes unit-cost Levenshtein distance, and requests documents for candidates within the threshold.
This is the beginning of the README. Read the rest at the original. Read the full README ↗
