Post-Quantum Cryptography for Stored Data: The Per-Record Cost Is Zero Bytes

8Braid Inc. Updated September 16, 2026 UTC. Contact: ashley@8braid.com.

Stored data can outlive the cryptography that first protected it. The useful question is whether the database can keep those records verifiable and usable as algorithms, keys and machines change.

8DB has completed a 100,000-record page-key derivation change with scheduled reads, an induced process kill and cold resume. In the latest offline evaluation under a four-CPU quota, all 689 eligible requests met the one-second deadline and all 100,000 records passed exact checks after reopening. Three earlier four-CPU evaluations preserved the records but missed deadlines. We retain those failures alongside the passing run so reviewers can examine both the capability and its remaining repeatability question.¹

The smaller cryptographic result remains useful: post-quantum key establishment adds zero bytes to each record in a controlled comparison using the same record cipher. Key establishment, signatures, indexes and migration have their own costs. The evidence below separates those measurements from live migration and two-host recovery.

The practical opportunity is to upgrade protection on retained data while keeping the familiar compact AES record representation. 8DB combines that design with migration, current-authority checks and recovery inside an embedded engine. For a team holding years of sensitive records, the useful test is whether those operations preserve the data and meet its operating budget. The same-cipher result establishes the record-size claim; full database storage and performance parity require a matched workload comparison.²

Why stored data

OMB memorandum M-26-15 ↗ directs agencies to prioritise identifying and re-encrypting long-lived sensitive data using keys protected by post-quantum mechanisms. NIST CSWP 39, updated June 29, 2026 ↗, section 5.1 addresses what happens to already-encrypted data when its algorithm must be replaced. That puts the migration and recovery behaviour of the storage engine directly in scope.

AES-256 protects record content. Post-quantum migration changes the vulnerable classical public-key mechanisms around it: how keys are established and how stored objects are signed. A database also has to replace protection on records already written when an algorithm is retired. 8DB, our embedded data engine, is designed around that operation.

How it works

• Key establishment for stored data uses ML-KEM-1024 (FIPS 203) in a hybrid with X25519, in software on commodity hardware.
• Each record is encrypted with AES-256. The microbenchmark below uses AES-256-GCM-SIV; the two-host recovery test uses the Required native AES-256-GCM and HKDF-SHA384 profile.
• Governed payload writes derive data keys when needed from a root secret and the record's captured governance state. This removes a persistent per-record key inventory from that path; protecting the root secret and enforcing current authority remain essential.
• Every ciphertext produced through the engine's cryptographic registry carries an algorithm version. Two algorithm versions can be registered at once, with the new version active for writes and the old version still decrypting, and an algorithm placed in quarantine refuses new writes while continuing to serve reads. This supplies a mechanism for the stored-data replacement problem in CSWP 39 section 5.1.³
• Batches of records are authenticated by one ML-DSA-87 (FIPS 204) signature over a SHA-384 Merkle root, with a per-record inclusion proof, so integrity costs one signature per batch instead of one per record.
• A sealed record can travel as the sealed object, so the transport is defence in depth rather than the security boundary.

What we measured

Release builds, same AEAD on both sides, one 115-byte record, 200 timed operations per arm after warm-up, four hosts across two operating systems and two architectures.

Reading: the per-record byte difference is exactly zero because the per-record cipher is unchanged. The three September runs' encrypt and decrypt medians agree within one percent. The historical July decrypt medians are 700 versus 600 ns, a 100 ns difference, so a claim of timing agreement across all four runs would be wrong. Key envelopes (including the measured 1,616-byte subtotal), signatures (4,627 bytes per signed batch), inclusion proofs, indexes and framing remain separate costs.²

Raw logs: Windows, Ryzen 7, 2026-07-19, Linux x86_64, Xeon, 2026-09-11, Windows, Ryzen 9, 2026-09-11 and Linux aarch64, Graviton3, 2026-09-12. The two September runs on shared hosts record their load in the log header.

Newer September 14 component runs ↗ used 2,000 timed operations per arm and measured clock resolution. WSL2 x86_64 encryption medians were 451/451 ns and decryption medians 441/441 ns for classical/PQC-established keys. Linux ARM recorded 1,172/1,171 ns and 1,188/1,188 ns, respectively. Ciphertext size remained 131/131 bytes. The 10 ns and 33 ns clock steps put those small timing differences in context: they support close component performance, not a speedup or a whole-database equivalence claim.⁴

Algorithm correctness

The ML-KEM-1024 (keyGen, encapsulation and decapsulation) and ML-DSA-87 (signature verification) implementations passed NIST's ACVP demonstration server on 2026-06-16, session 744723.⁵ An offline known-answer suite of 35 vectors reproduces the result: KAT report.

Inspect and reproduce

The public evidence repository ↗ includes readable results, known-answer vectors and OpenSSL interoperability artifacts. Its verification guide ↗ explains how to check artifact hashes, recorded ML-KEM shared secrets and valid and modified ML-DSA signatures without access to the engine. The timing history ↗ retains inconclusive and failed screens alongside their controls.

Engine re-execution uses the evaluation source and harness. The component benchmark runs with cargo test --release --features v2-mera --test cnsa_m1_bench -- --ignored --nocapture; the known-answer driver uses cargo run --bin run_acvp_demo. Public artifact verification and a fresh engine run answer different questions. Both are useful, and the evidence identifies which one was performed.

Recovery on two physical workstations

On September 15, we ran the Required native profile across two Linux environments on physical workstations connected by Ethernet. The channel used ML-KEM-1024 and trusted ML-DSA-87 sender authentication; the admitted native stores used AES-256-GCM, HKDF-SHA384 and HMAC-SHA384 authentication. The executed source and binary were frozen before either host started.⁶

The test admitted 512 distinct typed WordNet GNSE records, killed the receiver at 45 seconds, kept it down for 15 seconds and reopened the same retained store. It then required new readable content within 30 seconds and a full typed reread of every record on both hosts by the end of the 240-second campaign, including a final 30-second drain. The receiver retained 172 exact records, resumed new readable content in 1,074 ms, and both hosts finished with all 512 matching the independent fixture. Both commit and applied watermarks were 513.

The recovery evidence package ↗ exposes the exact synthetic record manifests, preregistered expected data, process results, clock reports and a Rust verifier. The public copies identify every redaction and retain the hashes of their originals. The earlier 293-of-512 result and the unpaired launch refusal are part of the same history. Their failures shaped the corrections and the explicit optimized profile used in the passing run.⁶

The transition on a running store

8DB's transition path prepares a replacement generation, re-encrypts and verifies its records, and activates it atomically. A useful migration qualification must also count reads served during that work, account for retained copies, and check authority again when a copy is restored. Algorithm versioning makes the transition possible; observed workload and recovery results determine which operating claims it has earned.³

The native lifecycle already checks current authority during payload migration and managed recovery, tracks retained managed copies, and emits a CycloneDX 1.6 cryptographic posture export for each dataset. The evaluation package includes the lifecycle, managed-restore and copy-accounting results and the posture schema-validation receipts. These capabilities make the transition and its remaining obligations inspectable at the storage layer.⁷

The September 15 live run changed HKDF-SHA256 to HKDF-SHA384 across 100,000 records, with AES-256-GCM-SIV unchanged. Two reader workers followed a fixed schedule of two requests per second through copying, index construction, verification and active serving. An acknowledged update, an added record and a deletion changed what the live view had to return. The migration process was killed after 50,048 accounted records and resumed in a new process.⁸

Every one of the 877 scheduled requests has a recorded outcome. Of these, 41 were scheduled during the deliberate process outage and one was interrupted in flight. All 835 completed requests met the original one-second scheduled-to-response deadline, including dispatch delay. Their p95 was 645.749 ms, p99 787.745 ms, and maximum 879.946 ms. These are the application's preregistered criteria, not a NIST latency standard. Final cold verification matched all 100,000 typed records and the lexical index, with 99,998 copied, one superseded by the update, one by the deletion and zero failed attempts.⁸

On September 16 UTC, we ran four fresh offline evaluations under the same four-CPU quota, 16 GiB memory limit, two-requests-per-second schedule and one-second deadline. Each executed the prebuilt engine without an engine checkout or build step, with external networking disabled. All four preserved the exact 100,000-record result after interruption and reopening.¹

The latest run recorded all 728 scheduled outcomes: 38 during the deliberate outage, one interrupted in flight and 689 within the read deadline. Its p99 was 739.035 ms. Cold verification again accounted for 99,998 copied records, one superseded by an acknowledged update, one by a deletion and zero failed copies. An independent custody check verified the executed binary, package, original evidence and actual container limits.¹

The batching changes reuse 8DB's existing Rust bulk-write primitive while preserving the migration's bounded work, durable commits and current-authority checks. The final change adds timing observations around the same engine. These sequential runs establish their individual results; they do not establish that diagnostics resolved the earlier deadline misses. Repeatability and final evaluator-package qualification remain active work. The four-CPU evidence supplement ↗ retains the full sequence for replay.¹

The public migration package ↗ includes the original inputs, the unchanged independent Rust auditor, all 31 controls and locked dependencies for offline replay. It also retains the preceding run's 16 deadline misses. Shared read admission and bounded diagnostic persistence corrected the implementation; the workload, one-second deadline and auditor stayed fixed. Public replay checks those retained records. A fresh engine run uses the evaluation executable and harness.⁹

What comes next

Bring one retained-data workload and the constraint that would determine adoption: live read availability, migration time, restore authority or storage cost. Send that evaluation question to Ashley. We can agree on the operation, the failure to inject and the evidence needed to decide whether 8DB solves it.

Footnotes

1. Fresh evaluations completed September 16, 2026 UTC, in the table's order, at sources 206f1a626f74699cad9c63e8276aa324d61bb48d, 0280898e8695a26330ce82006e129a98af1ca146, 41ca1c8d2f9c2e24959fe980b99257f58829a4de and 9c5ae6c9a4d1fa84b11fdf8ead679bab657e6af7. The latest run completed at 03:00:58 UTC. The quota limits CPU time rather than assigning four dedicated cores. All runs use the unchanged Rust auditor and the declared process-outage exclusion; deadline failures include expired requests where present. Percentiles use nearest rank over nonexcluded outcomes. One successful request in the latest run crossed an ordinary phase boundary and remains included. Public replay verifies retained evidence; fresh engine execution uses the evaluation package. The measured transition remains HKDF-SHA256 to HKDF-SHA384 with AES-256-GCM-SIV unchanged. ↩ ↩² ↩³ ↩⁴

2. Absolute times depend on the host; measured load and commands are in the raw headers. The July 100 ns difference remains unexplained by these runs and is retained as measured. The 1,616-byte subtotal is approximately 0.0123% of 100,000 already-encrypted 131-byte records. It counts the ML-KEM ciphertext and wrapped key, excluding other envelope fields and serialization. Total stored bytes also include AEAD overhead, signatures, inclusion proofs, metadata and indexes. One batch signature authenticates the signed root; whole-dataset verification additionally requires the intended records and their coverage to be checked. Whole-database parity needs matched cipher, authorization, indexing, durability and load, with complete stored-byte accounting and repeated latency/throughput measurements. These microbenchmarks do not establish that claim, and the separate AES-GCM compliance profile includes additional key-commitment work. ↩ ↩²

3. The public migration scope ↗ describes the recorded HKDF-SHA256 to HKDF-SHA384 transition. Detailed lifecycle, managed-restore and retained-copy tests are available with the evaluation engine. A registry supporting two versions does not by itself prove concurrent read availability or coverage of every historical copy. ↩ ↩²

4. Source 4efb7653b91216d0ed6e8c5aa463e7bb1806a211, release/v2-mera, 16 warmups per arm; keys were established before the timed AES-256-GCM-SIV calls. Original host, load and output records are linked with the results. The WSL2 run is distinct from the earlier native Windows and Xeon runs. Per-operation sample arrays were not retained, limiting statistical reanalysis. A separate provider comparison ↗, source cc994fc6e1ecdede60eb679c3c964fafc2c92946, compares AES-GCM with key commitment against the research SIV wrapper. It returns 185 versus 136 bytes and records higher operation times on both hosts. Those returned buffers use a different interface from the 131-byte same-AEAD comparison; changing both cipher and commitment measures a profile difference, not an isolated PQC penalty. Full protected-store costs remain a separate measurement. ↩

5. ACVP disposition and vector provenance ↗ identify the tested operations. 8DB has no CAVP certificate or CMVP module validation. Algorithm selection, module validation and deployment qualification are separate assessments. ↩

6. Run mesh-required-feature-opt2-ethernet-20260915-r9, source 7db11180d1a71f7d95cd9698c72ffd1f044d1e6e, optimized binary SHA-256 9596da2abf37ee0e22c714ecf407db138acfe4153fcbd96093b779f911377009. Rust 1.94.1, opt-level 2, debug assertions and overflow checks enabled. Both actual native tests and wrappers exited 0; both 270-second clock observations had zero regressions. Independent audit reconciled all 512 typed hashes and the full aggregate on both hosts. This is a fixed synthetic-corpus, current-admitted-copy qualification with a real process kill. Physical power loss, endurance, historical all-copy coverage and a general throughput claim require their own tests. The public package ↗ explains artifact verification and the evaluation access needed for a new engine run. ↩ ↩²

7. Evaluation-access runs include protection-lifecycle-2026-09-11, managed-restore-source-2026-09-12, combined-lifecycle-qualified-2026-09-12 and inventory-parts-qualified-2026-09-12. The latter runs include posture-*.cdx.json and posture-schema-validation.json. These receipts qualify their declared native paths and managed-copy inventory; historical external copies remain separate accounting obligations. Request the lifecycle evidence. ↩

8. Run p11-r6-chain-20260915-attempt1, September 15, 2026, source 206f1a626f74699cad9c63e8276aa324d61bb48d, Rust 1.94.1 release with stage diagnostics. Shared Ubuntu 24.04 WSL2 workstation, AMD Ryzen 9 9950X3D reported CPU, 16 guest logical processors; synthetic Wordnet lexical workload. The host record and original inputs ↗ identify the exact build, oracle and executed binary. Percentiles use nearest rank over the 835 nonexcluded outcomes, including two successful phase crossings. The engine cold-reopened and checked the stored records; public replay checks its retained evidence. This KDF change preserves the cipher and is separate from migration into the complete CNSA 2.0 deployment profile or formal validation. ↩ ↩²

9. The governed profile derives a key from the write's governance state; its ingestion, migration and recovery costs require their own workload measurements. The component table holds the AEAD key fixed and varies how it was established. The older managed-copy run recorded no successful concurrent reads. The separately implemented live operation now has the R6 result reported here; neither changes the older result. Other workloads, architectures, retained-copy retirement and independent engine reproduction retain their own acceptance requirements. ↩

Continue the technical conversation

Where could this help your work?

Bring a research question, a database workload or an application you want to build. Let’s connect the ideas in this article to an evaluation that matters to your team.

Discuss this work