Shelf Oracle
Single-server computational private information retrieval: direct RLWE and bounded stateful preprocessing, in the browser.
Live demo: https://systemslibrarian.github.io/crypto-lab-shelf-oracle/
What It Is
A library catalog ordinarily answers which book do you want? by learning the answer. Private information retrieval (PIR) changes that interface: under an explicit security model and its assumptions, the client gets the requested record without revealing its index to the server.
The classic information-theoretic route shown here needs two servers that never collude. This lab also demonstrates computational routes with one.
The construction. Single-server computational PIR in the style of SealPIR — Sebastian Angel, Hao Chen, Kim Laine and Srinath Setty, PIR with Compressed Queries and Amortized Query Processing, IEEE Symposium on Security and Privacy, 2018. The mature baseline uses the direct one-hot form:
- The client encrypts a selection vector
b of length N under BFV: b[index] = 1, every other entry 0.
- The server computes
Σᵢ Rᵢ · Enc(bᵢ) over its own plaintext records — one plaintext-by-ciphertext multiplication per record, then homomorphic addition.
- Every term with
bᵢ = 0 contributes the zero polynomial. The single term with bᵢ = 1 contributes R_index. So the sum is the record, and one ciphertext comes back.
The Compressed Query exhibit covers the same 64-record catalog with four fixed 16-selector blocks. The selected block encrypts 16⁻¹ · X^localIndex; the other three encrypt zero. All four ciphertexts cross the wire, with no plaintext index or selected-block field; the choice is present only under encryption and hidden under the compressed path's stated assumptions. The server expands every block with the odd substitutions X → X^1025, X^513, X^257 and X^129, noisy binary-gadget key switching, additions and negacyclic shifts; scans all 64 records; and returns four fixed ciphertexts. The client keeps the response for its private block. The direct decrypt, compressed decrypt and independently built catalog record must agree byte for byte and pass the record's SHA-256 decode tag; that tag detects decoding errors here, not a malicious server.
The Stateful Preprocessing exhibit is a separate, bounded adaptation of Zhou, Park, Shi and Zheng's Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation (major revision dated 12 November 2023; IEEE S&P 2024). A client-specific setup streams the static 64-record database and privately retains PRF-defined parity hints, punctured backup hints and replacement records. An online request sends exactly one one-byte record index for each of eight chunks; the server XORs those eight 512-byte records and returns one 512-byte parity. That eight-byte upload is this fixed N = 64 lesson's canonical codec. The pinned reference implementation transports uint64 indices through protobuf, so eight bytes is neither its wire format nor a copied Piano benchmark. If the wanted record is x and its same-chunk replacement is r, the client recovers DB[x] = P ⊕ response ⊕ DB[r], then consumes a backup to refresh the used hint. Sampling deliberately permits r = x and duplicate replacements: both are valid in that equation. When r = x, the target index can therefore appear in its chunk on the wire; privacy is a distributional claim, not a promise that the target value is never transmitted. There is no server ProcessDB artifact in this adaptation—the server keeps the original database—so its preprocessing is identity/none; the expensive setup is the client-specific database stream and retained private state.
The BFV encryption — used by the direct and compressed routes, not the stateful one — follows Junfeng Fan and Frederik Vercauteren, Somewhat Practical Fully Homomorphic Encryption, IACR ePrint 2012/144, hand-rolled here over R_q = Z_q[X] / (X^n + 1). Key generation, encryption, decryption, plaintext multiplication and ciphertext addition remain the direct path. Expansion adds automorphisms and key switching, but still no ciphertext-by-ciphertext multiplication and therefore no relinearization. Dense switch-key products use two auxiliary NTT primes and exact CRT reconstruction with an executable coefficient bound; the record fold remains the readable schoolbook implementation.
The security models. On the direct path, Enc(0) and Enc(1) are indistinguishable without the secret key under the decision-RLWE assumption, so the query carries no index that a computationally bounded adversary can extract. The compressed path additionally publishes key-dependent Galois keys and therefore inherits the circular-security assumption stated below; ordinary IND-CPA alone does not cover that extra material. The stateful path instead relies on secret PRF-derived coordinates—modeled as independent for the stated availability calculation—and strict one-use state discipline: a real query, cached repeat, local setup miss or local failure still puts one index per chunk on the wire and receives 512 bytes. A cached repeat spends a fresh, previously unused effective target as its cover; once a request is committed, any target or refresh slot allocated to it stays consumed and is never rolled back for a retry. Live state always draws from WebCrypto; deterministic entropy injection exists only at the explicitly named test boundary. All three paths assume an honest-but-curious server for query privacy, not a malicious server, and they make separate computational assumptions. The word computational is the entire difference from Oblivious Shelf and Patron Shield, which are information-theoretic and pay for it with a second server that must never collude.
The parameters. The mature direct exhibits default to n = 1024, q prime just under 2²⁶, t = 17, a uniform ternary secret and centred-binomial error with η = 21 (σ = √10.5 ≈ 3.24). The compressed comparison fixes both its direct reference and expanded route at q = 2²⁷ − 39, the largest prime below 2²⁷, so the route comparison does not mix moduli while expansion gains one more bit of switching headroom. Those modulus bit lengths are at or below the 128-bit classical row's log q ≤ 27 ceiling in the Homomorphic Encryption Security Standard (HomomorphicEncryption.org, November 2018). That table assumes discrete-Gaussian error near σ = 3.19, while this lab uses a differently shaped centred-binomial law. The comparison is therefore only against the published bit ceiling, not a claim that the table's security estimate transfers. It also does not justify releasing key-dependent Galois hints: the evaluation-key path additionally relies on a circular-security assumption for that key-dependent BFV material. The page keeps both limitations visible.
The bounded stateful parameters. That exhibit fixes N = 64, record size B = 512 bytes, eight chunks of eight records, and a window ceiling Q = ⌊√N ln N⌋ = 33 committed requests. It uses 256 primary hints: ⌈ln 33 + (40 + 1) ln 2⌉ = 32 groups of eight, plus eight punctured backups and replacements per chunk. The extra bit follows the conservative exponential sizing rule used by the authors' current reference client; these are pinned teaching parameters, not the paper's asymptotic regime. In the independent-coordinate model, a fixed target's setup miss probability is exactly (7/8)^256 ≈ 2^-49.32. Across a session, after allowing seven programmed hints in one chunk to be deterministic non-hits, at least 249 coordinates remain uniform; the displayed union bound is 33 · (7/8)^249 ≈ 1.20 × 10^-13 ≈ 2^-42.92. That number covers only primary-hint availability under independent secret coordinates and this bounded refresh schedule. It is not a 128-bit claim or an end-to-end security bound. There are exactly eight refresh slots for the eight possible effective targets in each chunk; one-use targets mean a canonical epoch never needs a ninth. Repeating an application target uses a distinct unused effective target for cover; once all eight targets in one chunk are spent, later covers can only come from other chunks. The separate 33-commit outer window remains the normal epoch ceiling.
Not production cryptography. A row of a 2018 table is an estimate under its stated distribution, not a proof or a certificate for this different distribution, and it says nothing about this implementation. Nothing is constant time; the direct server loop skips zero plaintext coefficients, so its running time depends on its own data; secrets and retained state sit in ordinary browser memory; and none of it has been audited. Both "servers" are objects in one page, with no network involved. Each expansion is deliberately bounded to sixteen 512-byte records; four fixed blocks cover the 64-record catalog. Adding their folds into one answer has an inadequate, sample-dependent margin: deterministic regression samples include both exhausted answers and answers below half a bit. The bounded adaptation therefore returns all four fixed responses and spends four times the response bytes; the page measures the discarded sum from each run. This is not SealPIR's multi-dimensional recursion or production response path, and the page makes no claim that one ciphertext under this one-modulus engine can expand to 64 or 256 correct selectors.
The stateful lesson is likewise an adaptation, not a claim to reproduce Piano's theorem, reference benchmarks, pipelined construction or asymptotic storage. At this tiny N, keeping eight backups and replacements for every chunk is deliberately linear overprovision, and the full retained-state encoding is larger than the database. Its server has no global preprocessing structure, so it must not be described as the Lin–Mook–Wichs doubly-efficient construction. The lesson does not implement dynamic Piano, authenticated storage, crash recovery, multi-client sharing, malicious-server privacy, answer integrity, availability, traffic hiding or timing protection. What is real is the arithmetic and state transition: setup parities are computed from the displayed database, exact wire buffers are parsed, server probes execute, answers recover through the displayed XOR equation, and used hints refresh from consumed backups. Timing is never used to turn the formula ledger into a benchmark claim.
Exhibits
-
The Shelf — 64 public-domain works with real authors, dates and Library of Congress class letters. Pick one; that choice is the application value each retrieval path is meant to hide. Shows the exact 512-byte record a successful query returns, its SHA-256 integrity tag, and — behind a disclosure — the byte-to-coefficient packing, four bits at a time, taken from the record actually on screen. Also carries the run seed: pin one and the BFV and two-server exhibits become reproducible, including the secret key, with the warning that deserves. It deliberately does not control the live stateful panel, whose setup and cover choices always cross the platform-entropy boundary.
-
The Server's View — the plaintext selection vector greyed out as what never leaves your machine, beside 64 opaque ciphertexts as what the server gets. Guess which one encrypts the 1. Then a real distinguisher runs 40 trials and reports its measured accuracy against the 1-in-16 baseline — and a single clearly-marked switch reuses one random pair across every entry, at which point the same crude attack is right every time. Nothing about the attack changes; only the encryption does.
-
Homomorphic Selection — the headline mechanism, stepped. Fold one record, eight, or the rest, and watch all 64 light up as the server multiplies them in: this direct one-hot construction evaluates the encrypted selection over every record without learning which bit is the 1. The noise budget falls, measured — the running ciphertext is decrypted and compared against what it ought to hold — beside the six-sigma prediction derived from the parameters alone. Until the chosen record is folded in, the accumulator decrypts to literal zero. At the end, one decryption produces a record the server never identified.
-
Compressed Query — the selected catalog record is retrieved twice from the full 64-record catalog: first with 64 direct ciphertexts, then with four fixed ciphertext blocks that expand to 64 selectors. Only the client knows which block carries 16⁻¹ · X^localIndex; no block or index field crosses the wire. The panel serializes and round-trips the four reusable Galois keys, traces all four expansion rounds for each block, counts key-switch convolutions and all 64 record products, measures noise before and after expansion, and derives the upload-amortization crossover from actual buffers. It also shows the non-result: query compression leaves the 64-record scan intact and returns four responses to avoid exposing the selected block.
-
Stateful Preprocessing — preprocess the static shelf into a private, client-specific Piano-style state, then retrieve through an eight-byte request and 512-byte response while the server probes exactly eight records. The panel exposes the primary hint, replacement and punctured-backup refresh equation; repeat retrievals use an ordinary unused effective target as cover instead of sending a cache flag. Separate ledgers show the 32,768-byte setup stream, setup reads and parity XORs, retained client-state bytes, online wire bytes and online server probes without turning unlike operations into one score. Interactive exercises lose all client state, send a fixed-shape cover that cannot recover the record, update a non-target record retained by the old state, demonstrate that its old valid tag is not freshness, invalidate the changed snapshot, and rebuild before independently recovering the changed record. To make that stale-state failure reproducible, the update exercise deliberately chooses its target and replacement relation from client-private audit state; it is a controlled negative diagnostic, not an ordinary application query or evidence for the independent-target privacy and availability claims. Rollback, malformed-response and window-exhaustion transitions remain executable core tests and visible limitations, not buttons the panel pretends to exercise.
When to Use It
Use single-server computational PIR when you cannot get non-collusion. In the lab's original direct-BFV head-to-head, two-server PIR is cheaper on every displayed cost, but it needs two operators under genuinely separate control — separate staff, separate jurisdictions, separate subpoena exposure. That is an organisational problem, not a technical one, and it is the reason single-server constructions get built at all. The stateful panel has a different setup/storage/online lifecycle and is deliberately not collapsed into that timing table.
Use it when the query index is the sensitive thing. On this lab's one-dimensional BFV routes, the database must be small enough — or the deployment rich enough — to pay O(N) server work per query. Query expansion reduces the query ciphertexts sent after setup; it does not remove the record products. That full scan is a property of those routes, not a requirement for every PIR scheme's online query phase. The bounded stateful route demonstrates a different trade: a full client-specific setup and substantial private state in exchange for eight online probes.
Use preprocessing only when its lifecycle is acceptable. Corrigan-Gibbs, Henzinger and Kogan formalize a client-preprocessing model in which a linear setup produces a client hint for a bounded sequence of adaptive queries. Their paper says its most efficient scheme is optimal for its trade-off between server online time and client storage. Piano gives a PRF-based construction in that family. This lab now executes a deliberately small Piano-style adaptation, but its client must stream the whole static database, protect and advance private state, refresh every used hint, send a cover query for a cached repeat, and rebuild after state loss or any database update. The exhibit's concrete formula ledger is evidence about this N = 64 adaptation only; it does not numerically instantiate or transfer either paper's asymptotic theorem or lower bound.
Do NOT use it as an access-control mechanism. Nothing checks that an encrypted BFV selection is one-hot, and nothing can — the server cannot read it. A malformed direct query can ask for a linear combination and receive its sum; malformed compressed blocks can yield one such result for each returned block. The stateful server strictly parses one in-chunk byte per chunk, but it still authenticates no client and returns the requested eight-record XOR. PIR bounds what the server learns, not what the client is authorized to extract.
Do NOT use it when query-event metadata is sensitive. With fresh randomness, the requested indices in a sequence of full-scan BFV queries remain hidden under each route's stated multi-message assumptions. The stateful path keeps its request and response shapes fixed too, but its occurrence, timing, count, rate and client identity remain visible, and losing or rolling back state can make later behaviour linkable. ORAM addresses a different problem: hiding a logical access sequence from a server that observes data-dependent physical storage locations. Stateful PIR is not ORAM: this lesson's server receives one probe index in every fixed chunk, while its private client state supplies the hiding distribution.
Do NOT use this code. It is a teaching implementation. Production BFV work uses audited libraries such as SEAL, OpenFHE or Lattigo; production preprocessing PIR additionally needs a reviewed protocol implementation, protected persistent client state, authenticated database versioning and an operational recovery design.
Live Demo
https://systemslibrarian.github.io/crypto-lab-shelf-oracle/
You can: pick any of 64 books; watch the encrypted selection vector be built and try to distinguish Enc(1) from Enc(0) yourself; break the encryption's randomness and watch a distinguisher go from chance to certain; step the homomorphic inner product record by record with a live measured noise budget; retrieve the same full-catalog record through direct and actually expanded compressed queries; preprocess the shelf into private state, execute and refresh Piano-style hints, compare setup and online costs, lose that state, update the database and rebuild; run single-server and two-server PIR head to head with real byte counts; make the two servers collude and recover the index instantly; shrink the modulus until decryption returns garbage; trip the demonstrated failure codes; and watch what a network observer still sees after all of it.
What Can Go Wrong
- Decryption-feedback research — 20 October 2026. Ordinary encryption security (IND-CPA), correct decryption, and security when an adversary learns computation results (IND-CPA-D) are different guarantees. Choe, Kang and Stehlé report attacks on particular BFV/BGV configurations using heuristic correctness assumptions, with experiments in OpenFHE and HElib. Crafted operations can exceed heuristic noise bounds; two attacks recover keys, while a third breaks indistinguishability. Parameter tables and noise estimates alone do not establish security in this feedback model. This browser lab does not reproduce those attacks or establish that its implementation is vulnerable. Choe, Kang and Stehlé, New IND-CPA-D Attacks on BFV and BGV, ePrint 2026/2546, received 19 October and revised 20 October 2026; accepted to ACM CCS 2026. Demonstrated results; attack-model-conditional.
The threat models, failure states and recovery boundaries.
Who the adversary is. An honest-but-curious server that follows the selected protocol and tries to learn the index from what it receives, plus a passive network observer that sees traffic but no plaintext. Privacy against the server is computational. The BFV routes rest on decision-RLWE, with the compressed route's additional circular-security assumption; the stateful route rests on pseudorandom secret coordinates and correct one-use client state. These are separate models, not interchangeable evidence.
What breaks it.
NOISE_BUDGET_EXHAUSTED — every record folded into the answer contributes its own encryption error, including the ones multiplied by an encrypted zero. Past the ceiling the answer still decrypts; it decrypts to garbage. The page detects it three ways, and reports them separately because only two are things a real client could do: the record's own SHA-256 tag fails, coefficients come back outside [0, 16) where the encoder can never put them, and — using the secret key and the true record, which a real client has neither of — the measured budget reaches zero. A deployment sizes its parameters in advance; it does not discover exhaustion at runtime.PARAM_UNSAFE — the modulus bit length exceeds the cited HES 2018 128-bit-row ceiling for this ring degree, or would push this implementation past 2⁵³ where JavaScript integers stop being exact. The first means even the page's limited reference comparison no longer applies; it does not by itself prove insecurity. The second is more immediate: past that bound JavaScript arithmetic is not exact, so the demo could produce plausible garbage while claiming exactness.DIM_MISMATCH — the query is not the same length as the shelf. Refused before any homomorphic work, because a short query answers over a prefix and a long one reads past the end, and both return a ciphertext that decrypts to something.INDEX_OUT_OF_RANGE — the requested shelf position does not exist.
The stateful path reports its own state-machine failures rather than borrowing BFV's noise codes. WINDOW_EXHAUSTED requires a new setup epoch; STATE_LOST, DATABASE_UPDATED and ROLLBACK_DETECTED say why old private state cannot safely answer; and MALFORMED_RESPONSE and REQUEST_ABANDONED consume the committed request and invalidate the epoch instead of rolling it back. HINT_UNAVAILABLE, NO_COVER_TARGET and STATE_INVALID are defensive fail-closed guards if an internal invariant is ever broken, not naturally exhausted paths in the canonical fixed model: eight one-use targets in a chunk have eight refresh slots, while a 33-commit window cannot consume all 64 cover targets. Preflight failures still send one random index per chunk and accept a 512-byte response before reporting the local error, so a different error-shaped request is not introduced. That fixed shape is not availability: without the retained private state, the response cannot recover the requested record.
What the protocol does not defend against.
- A malicious server. These exhibits provide no answer integrity. A server that wants to lie can return a different record with a matching tag; the tag is part of the record it holds. On the stateful path, the ordered-database SHA-256 digest detects a change only when the client is given the current snapshot to compare, and a valid tag on an old record does not establish freshness. The external generation high-water mark can reject an older serialized state only if the application retains it separately. Neither mechanism authenticates the server or supplies a monotonic database commitment. Verifiable PIR and authenticated freshness are separate requirements.
- Traffic metadata. Occurrence, timing, frequency, count, client identity and database shape all leak. What does not leak is the index: the direct route always returns one ciphertext, while the compressed route always returns four, whichever record was requested. The direct observer exercise sends one ciphertext per shelf position; the compressed route sends four fixed query blocks after its reusable Galois-key setup. Those lengths are visible and fixed for the 64-record shape — they do not vary with the chosen index. Padding and traffic shaping are separate mechanisms for the things that do leak; PIR does not claim them.
- Repeated queries. With fresh randomness, each requested index on the BFV routes — and therefore the requested-index sequence — remains hidden under each route's stated multi-message assumptions: decision-RLWE for direct queries, plus the stated circular-security assumption for compressed evaluation material. On the bounded stateful route, an already cached application target triggers a normal query for a fresh unused effective target; that recovered cover record is cached too, and the requested cached record is returned locally. Every effective target is one-use within an epoch. This consumes online work and state even for repeats; it is not evidence for unbounded queries. Query occurrence, timing, count, rate and client identity remain visible on every route.
- A malformed client query. Unauthenticated by construction — see When to Use It.
- Side channels. Nothing here is constant time. The BFV server's inner loop skips zero plaintext coefficients, so its running time depends on its own data; that costs nothing in this demo because the shelf is public, and it is exactly the shortcut a deployment must not take. The stateful path also does not hide setup, rebuilds, failures or the cadence of requests. Fixed buffer sizes are not a timing- or traffic-analysis defense.
Real-World Usage
Single-server PIR is a live research and deployment area, not a museum piece.
- SealPIR (Angel–Chen–Laine–Setty, IEEE S&P 2018) uses query expansion: for a dimension that fits in one BFV polynomial, the client sends one ciphertext plus reusable Galois keys and the server expands it into the selection vector with substitutions and key switching. This lab executes that mechanism over sixteen positions per ciphertext and uses four fixed blocks to cover its 64-record catalog without revealing the selected block. It does not implement SealPIR's multi-dimensional recursion, modulus switching, seeded ciphertext compression or production parameter sets, and it copies none of the paper's benchmark numbers.
- Client-preprocessing PIR first pays for a client-specific hint, then amortizes that setup over a bounded adaptive query sequence. Corrigan-Gibbs, Henzinger and Kogan's EUROCRYPT 2022 paper says its most efficient scheme is optimal for its trade-off between server online time and client storage. That model-specific result is important context, not a numeric theorem this
N = 64 exercise instantiates or transfers.
- Piano (Zhou–Park–Shi–Zheng, ePrint 2023/452, major revision 12 November 2023; IEEE S&P 2024) builds sublinear-time preprocessing PIR from PRFs. This lab implements a bounded, inspectable adaptation of its current primary/backup-hint idea. It does not copy the paper's asymptotic guarantees, benchmark results, larger parameter choices, pipelining or separate dynamic-database construction.
- Doubly efficient PIR is a different preprocessing model. For any constant
ε > 0, Lin, Mook and Wichs construct an unkeyed Ring-LWE scheme with deterministic server preprocessing, O(N^(1+ε)) preprocessing time and size, polylogarithmic online query work and communication, and O(N^ε) updates (STOC 2023; SIAM Journal on Computing, published 5 March 2026). Shelf Oracle implements none of that machinery: its Piano-style state is client-specific, its server's ProcessDB is identity/none, and every database update invalidates the whole teaching epoch. The Lin–Mook–Wichs result is included to prevent the two models from being credited to each other.
- OnionPIR and the Spiral family push the same line further with better rate and smaller responses.
- Two-server, information-theoretic PIR (Chor–Goldreich–Kushilevitz–Sudan, FOCS 1995) remains active and practical; it is not obsolete, it simply buys its unconditional privacy with a non-collusion assumption. This lab implements it too, so the comparison can be measured rather than asserted.
How to Run Locally
npm install
npm run dev # http://localhost:5173/crypto-lab-shelf-oracle/
npm test # the cryptographic unit suite
npm run build # tsc --noEmit && vite build
npm run test:a11y # production-browser accessibility, claims and research gates
The browser gate builds first and serves the production bundle, so what passes is what ships. Playwright's Chromium is installed with npx playwright install chromium — never --with-deps.
Related Demos
- Oblivious Shelf — two-server XOR IT-PIR (Chor et al. 1995) over a 16-entry shelf, step by step. The other half of this lab's trade.
- Patron Shield — the same two-server scheme framed as library ethics, with a one-click collusion attack.
- FHE Arena — BGV/BFV with ciphertext-by-ciphertext multiplication, relinearization and the noise budget this lab borrows and puts to work.
- Search Vault — searchable encryption that deliberately leaks the access pattern, then inverts it with the count and IKK attacks. What happens when the leakage this lab refuses to produce is produced.
- ORAM Vault — Path ORAM hides a logical access sequence from a server that observes data-dependent physical storage locations. Shelf Oracle's BFV routes perform the same full 64-record scan for every query. Its bounded stateful route instead exposes one secret-distributed probe per fixed chunk and depends on private one-use client state. Neither model hides query-event timing or count, and neither turns PIR into ORAM.
Build & Verify
121 unit tests across eight files, all passing (npm test).
Primary-source anchors. Eight primary sources bound the implementation and its claims. The first two supply values that the suite checks directly; the others define constructions, models and security caveats rather than serving as invented interoperability vectors:
- RFC 8439 (ChaCha20 and Poly1305 for IETF Protocols) — the §2.3.2 block-function vector and the §2.4.2 encryption vector, in
src/pir/chacha20.test.ts. ChaCha20 samples every BFV ciphertext and its block function also supplies domain-separated stateful coordinates. The RFC vectors anchor that primitive implementation; they do not by themselves transfer Piano's security theorem to this adaptation.
- The Homomorphic Encryption Security Standard (HomomorphicEncryption.org, November 2018) — all 18 published modulus ceilings of the uniform-ternary-secret classical table (
n ∈ {1024 … 32768} × {128, 192, 256}-bit), checked one row at a time in src/pir/records.test.ts. Its error is discrete Gaussian; this lab's error is centred binomial. Tests require the UI to label the result as a bit-size comparison rather than transferring the table's security estimate. PARAM_UNSAFE marks a modulus above the cited 128-bit-row ceiling (or an exact-arithmetic failure), not a proof of insecurity.
- Fan and Vercauteren, Somewhat Practical Fully Homomorphic Encryption (IACR ePrint 2012/144) — the BFV construction from which this teaching implementation takes its ciphertext convention and key-switching setting.
- Angel, Chen, Laine and Setty, PIR with Compressed Queries and Amortized Query Processing (IACR ePrint 2017/1142) and the Microsoft SealPIR implementation — the paper's server-side inverse scaling and the implementation's algebraically equivalent client pre-scaling, plus the odd-automorphism expansion schedule exercised here.
- Geelen and Vercauteren, Fully Homomorphic Encryption for Cyclotomic Prime Moduli (IACR ePrint 2024/1587) — an explicit statement of the distinction the UI preserves: an IND-CPA reduction without evaluation keys does not by itself establish security for key-dependent evaluation material; the latter invokes a circular-security assumption.
- Corrigan-Gibbs, Henzinger and Kogan, Single-Server Private Information Retrieval with Sublinear Amortized Time (IACR ePrint 2022/081; EUROCRYPT 2022) — the client-preprocessing model and bounded adaptive queries. The paper says its most efficient scheme is optimal for its trade-off between server online time and client storage; this lab neither numerically instantiates nor transfers that model-specific theorem.
BFV and SealPIR do not supply interoperability test vectors for this implementation, so the rest of the suite uses independent definitions and cross-checks rather than pretending otherwise. The original path's strongest check is a three-way cross-scheme agreement: single-server RLWE PIR, two-server XOR PIR and a plain array read must return the identical bytes. The compressed path independently requires the direct BFV query, the expanded query and the separately built catalog record to agree byte for byte and pass the embedded SHA-256 tag.
Also covered: the negacyclic property checked directly (X^(n-1) · X = -1, not +1 — a cyclic ring round-trips perfectly and no correctness test would notice); schoolbook multiplication against a definitional oracle; the new NTT/CRT products against a separate quadratic definition, including the wraparound sign and an executable exactness bound; BFV round-trips over every plaintext value; additive homomorphism; that reused randomness makes Enc(1) − Enc(0) exactly Δ; every raw switch-key sample checked against B^j · σ(s) with its sampled error bound; the published odd substitution schedule; all sixteen one-hot expansion positions at the shipped modulus; full-catalog direct/expanded/plain retrieval agreement for an index outside the first block; positive but smaller post-expansion noise; canonical evaluation-key serialization and refusal of missing, truncated, mismatched and noncanonical setup material; detection that a canonical but corrupted evaluation key changes the output; an exact server-query shape with no block or index field; that the stepped fold reaches the same ciphertext as the one-shot server; that a partial answer decrypts to zero until the chosen record is folded in; that the measured budget falls monotonically; that the six-sigma prediction is a bound the measurement respects; UTF-8 truncation that never splits a sequence; wire-format round-trips at every modulus; and every failure code, raised and named.
The stateful suite independently reconstructs setup parities from the exact database, checks both recovery and backup refresh equations, and exercises all 64 targets. It treats r = x and duplicate replacements as valid cases rather than resampling them; verifies the exact eight-byte canonical query and 512-byte response parsers; and rejects truncated, oversized, cross-chunk and noncanonical forms. It also checks cached-repeat cover work, one-use effective targets, synthetic setup misses (including a cached-repeat cover and malformed or abandoned responses), the 33-request window boundary, fixed-shape local index failure, state loss, abandoned and malformed responses with no rollback, canonical state round-trips, stale-state rejection against an external high-water mark, rejection of a database update while a request is pending, and full invalidation after a database update. Live entry points are checked to cross the WebCrypto boundary, while reproducible entropy is limited to functions named ForTest.
The browser gate (npm run test:a11y) runs three test files against the production build:
e2e/a11y.spec.ts — zero WCAG 2.1 A/AA violations, at 1280px, 380px and 280px, across roughly forty driven states per width. It is not an axe wrapper: it asserts axe's incomplete bucket as well as violations (which is where aria-prohibited-attr and every color-mix() contrast decision live), computes contrast arithmetically over composited backdrops, measures non-text contrast per border side against a ratchet baseline that is currently empty, and adds reflow, scroller-reachability and invisible-focus-target oracles that axe has no rules for. Reduced motion is set through emulateMedia and asserted from inside the page; nothing is injected and no panel is revealed from script.e2e/claims.spec.ts — checks that the page tells the truth by comparing values the page itself printed rather than hardcoded strings: the record the fold returns against the record the shelf shows; the budget ceiling re-derived as log2(⌊q/t⌋) from the printed ring parameters; the query size re-derived from n and log q where the source measures a serialized buffer; the compressed-query buffer ledger, substitution schedule and executed operation counters independently re-derived; direct, expanded and plain-record bytes compared; and the head-to-head upload against the Server's View figure. The stateful checks independently re-derive the canonical wire shape, recovery and refresh equations, session bound, amortized crossover and codec/source limitations; confirm cached repeats spend a distinct target while unrelated renders preserve the session; and exercise stale output after a retained non-target database update, detection and rebuild. The file also checks that each failure code names its actual cause with numbers matching the controls on screen; verdict retirement (change a parameter or key and the stale measurement is gone and the page says why) alongside a no-op guard (re-selecting the same book retires nothing); the [hidden] cascade probe; and that the page does not fight its reader — focus stays on the control you activated across the rebuild, the live region is one node that survives every render, and a demonstration failure code does not overwrite a real retrieval verdict.e2e/research-2026-10.spec.ts — preserves the dated decryption-feedback research note, its IND-CPA-D and heuristic-correctness boundaries, its distinction between published attacks and this lab, and its primary-source link.
Defects found by the gate and by an adversarial review pass, and fixed rather than baselined: .panel { display: grid } outranking the UA's [hidden] rule, which left six tabpanels in the tab order painting nothing; a missing box-sizing: border-box plus the grid min-width: auto default, which pushed the document sideways at 380px; aria-label on role-less tiles; keyboard focus being thrown to <body> on every re-render; live regions rebuilt inside a cleared subtree, so none of them could announce anything; a demonstration failure code overwriting a real retrieval verdict; a retirement reason latched on the first change; a hidden panel re-encrypting a 64-ciphertext query nobody was looking at; the comparison table conveying "better" by colour alone; and two rows of the what-is-hidden table contradicting each other about query length.
Mutation-tested, by a committed runner. A green suite is not evidence until it has been watched failing. npm run test:mutations (scripts/mutations.mjs) replays seventeen named mutations from a clean baseline, and CI runs it on every pull request and push before the deploy job, uploading mutation-evidence.json as the mutation-evidence artifact. Each recipe names ONE owning test; the runner requires the unmodified copy to pass the whole unit suite and build, the named owner to be green, the patch to change the production bundle (JavaScript and CSS are hashed, because one recipe mutates the stylesheet), the owner to go red on a test failure — a timeout, a crash, a missing module or a preview server that failed to start is refused, not counted — and the source and bundle to be restored byte for byte with the owner green again. The original eight cover the negacyclic sign in the direct ring, the DIM_MISMATCH guard, fresh encryption randomness, the [hidden] rule, the no-op selection guard, focus restoration, live-region persistence, and the on-screen-panel re-render. Four target the compressed path: the odd Galois schedule, the automorphism's negacyclic sign, preservation of the substituted c0 term during key switching, and subtraction rather than addition when the NTT convolution is folded modulo X^n + 1. Five target the bounded Piano core: the replacement-record XOR in recovery, refresh-slot consumption before send, invalidation after a malformed response, rejection of an oversized query encoding, and database-digest equality. Twelve are owned by Vitest tests and five by Playwright claims run against a fresh production build. Measured on 2026-10-27: 17 of 17 caught, every owner green before and after.
Performance
Measured in-page, on the reader's own machine, at the shipped defaults (n = 1024, q ≈ 2²⁶, 64 records of 512 bytes):
| Shelf Oracle (1 server, RLWE) | Chor et al. XOR (2 servers) |
|---|
| Upload per query | ~416 KiB | 16 B |
| Download per query | ~6.5 KiB | 1 KiB |
| Client work | ~50 ms | ~0.1 ms |
| Server work | ~80 ms | ~0.6 ms |
| Records touched | 64 of 64 | ~half of 64, per server |
| Privacy | computational (RLWE) | information-theoretic |
| Trust assumption | none between operators | the two must never collude |
That table is the original 64-record direct baseline at its default 26-bit modulus. The separate Compressed Query exhibit compares both routes over all 64 records at the expansion path's 27-bit modulus. A ciphertext is 6,912 bytes: the 64-ciphertext direct query is 442,368 bytes, while four fixed compressed-query blocks total 27,648 bytes. Four binary Galois keys serialize to 746,520 reusable setup bytes, so the first compressed upload totals 774,168 bytes and cumulative compressed upload becomes smaller on query two. The direct response is 6,912 bytes; the compressed server returns four fixed responses totaling 27,648 bytes so response shape does not reveal the selected block. Both routes still perform 64 record products. Those figures are derived from actual serialized buffers; the exhibit separately measures the reader's timings and noise. Seeded compression of the uniform ciphertext half remains unimplemented and is named rather than assumed.
The stateful preprocessing ledger uses different units and stays separate from that BFV table:
Stateful component (N = 64, B = 512) | Exact teaching cost |
|---|
| Client-specific setup stream | 64 records = 32,768 B |
Server ProcessDB | identity/none; original database only |
| Setup parity work | 2,048 primary + 448 backup = 2,496 record-XOR contributions |
| Setup replacement retention | 64 record copies |
| Base private client state | 197,696 B before sparse caches |
| Normal-query cache ceiling | 33 × 513 B = 16,929 B |
| Online upload / download | 8 B / 512 B = 520 B per committed request |
| Online server probes / XOR contributions | 8 records / 8 per committed request |
| Bounded epoch | at most 33 committed requests, and at most eight target-chunk refreshes per chunk |
These are formula and serialized-buffer counts, not browser timings. The wire numbers count this lesson's canonical payloads and omit protobuf, HTTP and other transport framing. At the full 33-request window, setup traffic amortizes to 32,768 / 33 ≈ 992.97 bytes per request; adding the 520 online bytes gives ≈ 1,512.97 bytes per request. Against the deliberately simple baseline that re-downloads all 32,768 database bytes for every lookup, cumulative stateful wire traffic first wins on query two: 33,808 bytes versus 65,536. A client allowed to download and retain this static public database once would need no PIR queries at all, so that crossover is a wire-accounting exercise, not a deployment recommendation. In the update exercise, comparing the presented snapshot with the retained digest scans another 32,768 input bytes; the page records that separately from online wire traffic, and the digest still does not authenticate freshness. Any database update invalidates the whole epoch and pays the setup stream, parity work and state rebuild again; this lab implements no incremental update algorithm.
Noise budget at those defaults: the ceiling is log2(⌊q/t⌋) = 21.91 bits, a freshly encrypted record measures about 16.5 bits — encryption spends roughly five bits on its own sampled error before the server does anything — and the finished 64-record answer measures about 7.6. At q = 2¹⁸ the same query exhausts and the page says so through the record's own integrity tag.
One of the browser demos in the Crypto Lab suite.
"So whether you eat or drink or whatever you do, do it all for the glory of God." — 1 Corinthians 10:31
