Binding keys to time: temporal provenance with HD derivation

Understand how hierarchical deterministic key derivation is used to make a timestamp unforgeable, how large artifacts are committed with a Merkle root, and how the watermark is embedded invisibly across formats and enforced by a mandatory rejection protocol.

Track

Research

Module

5 · Research case studies

Prerequisites

Digital signatures · Merkle trees · Hash chains and transparency

Integrity and authenticity are the easy guarantees: a content hash plus a signature give you both with standard tools. Temporal binding is the hard one. A signer can simply write any value into a sourced_at field and sign it; the signature then faithfully authenticates a lie. The question the proposal answers is: how do you make the timestamp itself unforgeable, so that back-dating is not just discouraged but cryptographically self-defeating?

The idea is to stop treating the timestamp as a mere signed field and start treating it as an input to key derivation. If the key you must sign with is a deterministic function of the time, then claiming a different time means signing with a different key — one whose matching public key is not the registered one, so verification fails.

BIP32 defines a tree of keys: from one master secret you can derive child keys by index, and the derivation is one-way — a child key reveals nothing about its parent or siblings without the master secret. BIP39 turns a human-memorable mnemonic into that master seed. The proposal adapts this so that the derivation path encodes time and context rather than wallet account numbers.

temporal-domain key derivation (schematic — transformed from the paper's Definition 3)
master seed  ms = PBKDF2-HMAC-SHA512(mnemonic, "ews-v1" || origin_id)
master key   k_m = BIP32_root(ms)      # master public key is published in the registry

# for an artifact created at time tau, in domain d, with header H:
k_epoch   = BIP32(k_m,     floor(tau / 86400))   # one key per day-epoch
k_domain  = BIP32(k_epoch, FNV32(d))             # branch per content domain
k_content = BIP32(k_domain, H.content_hash[0:4]) # leaf per artifact
sig       = EdDSA_sign(k_content, canonical(H))

The path is time -> domain -> content. The epoch index is the creation day; the domain index separates, say, medical from financial signing authority; the leaf is tied to the artifact's own content hash. A verifier re-derives the expected public key from the claimed timestamp and domain and checks the signature against it.

This is the one place the paper states a proof, so it is worth separating clearly what is PROVEN from what is merely asserted. The proposition is: a signature produced under the key for epoch T1 cannot verify under the key for a different epoch T2.

• ▸BIP32 child derivation is one-way: given k_epoch(T1), computing k_epoch(T2) requires the master private key k_m. An attacker who only stole a day's signing key cannot roll it forward or backward to another day.
• ▸EdDSA verification is key-specific: a signature under k_epoch(T1) verifies only against the public key of k_epoch(T1), which differs from that of k_epoch(T2).
• ▸Therefore, to present an artifact as created on a different day, the attacker would need that day's key — which requires the master secret, not just the artifact.

For artifacts too large to hash in one pass (images, documents), the content anchor becomes a Merkle root over fixed-size chunks instead of a single flat hash. This lets a verifier check or progressively load part of an artifact without recomputing the whole thing — the same partial-verification property Merkle trees give elsewhere in the course.

large-artifact commitment
content_hash = MerkleRoot( SHA256(chunk_1), ..., SHA256(chunk_n) )
# each chunk a fixed size (the paper uses 1 MB); enables partial verification

Keys are not forever. The proposal uses an append-only, publicly auditable registry — modeled on Certificate Transparency — so that rotation and revocation are verifiable by anyone without a central authority making trust decisions in the request path.

• ▸Scheduled rotation: an emitter periodically publishes a new master public key with a validity window. A verifier selects the key whose window contains the artifact's sourced_at, so historical artifacts keep verifying against the key that was valid when they were signed.
• ▸Emergency revocation: on key compromise, the emitter publishes a revocation entry with a compromise time t_revoke. Artifacts with sourced_at after t_revoke are rejected; artifacts signed before the compromise stay valid, because temporal binding ties each signature to its epoch.

The header is then embedded invisibly, per format, so the artifact is unchanged to normal consumers. The paper reports a format table: a structural field in JSON/CSV, an XMP metadata stream in PDF, a private tag in medical images, a response header for HTTP feeds, and least-significant-bit steganography for raster images.

LSB embedding for images (as described by the paper)
# header is base64-encoded, then spread across the
# least-significant bits of the image's blue channel.
# the paper reports ~32 KB of capacity in a 512x512 image,
# enough for the header; the image looks visually identical.
# verification zeroes the LSBs and recomputes content_hash
# over the cleaned image before checking the signature.

All of the above is enforced at one chokepoint: a mandatory rejection protocol run on every artifact at the ingestion boundary, before any belief is derived. The paper specifies five checks that must all pass; each failure has a distinct, logged rejection reason.

1. 1Extract the header using the format-specific method. Missing header -> reject (no-header).
2. 2Recompute the content hash and compare to header.content_hash. Mismatch -> reject (integrity).
3. 3Re-derive the public key from the claimed timestamp and domain, and verify the signature. Fail -> reject (authenticity).
4. 4Look up origin_id in the trusted registry. Unknown or revoked -> reject (unknown-emitter).
5. 5Check freshness: pass sourced_at and ttl_hint to the agent's freshness gate. Stale for this action class -> reject (stale).

The paper also defines a transitional pragmatic mode for the adoption period: an unsigned artifact is not dropped but admitted with a time-to-live of zero for irreversible actions and flagged unverified, and that flag propagates to every belief and decision derived from it so a human operator sees it explicitly. This is the honest acknowledgment that a mandatory-only scheme cannot be switched on overnight across a world of legacy data.

What is established versus what is claimed, stated honestly:

• ▸PROVEN (with proof): temporal binding — a back-dated timestamp forces a non-verifying key, reducing to one-wayness of HD derivation and unforgeability of EdDSA. Scope: it defeats back-dating by anyone who does NOT hold the master secret.
• ▸ESTIMATED, not independently benchmarked: the paper reports verification overhead below ~6 ms end-to-end for a 1 MB artifact on a single commodity CPU thread, dominated by SHA-256 (~3 ms for 1 MB), with BIP32 derivation ~2 ms and EdDSA verification ~0.1 ms. The paper itself calls these estimates on one hardware profile — treat them as order-of-magnitude, not a measured benchmark.
• ▸OPEN: key-management complexity is the real operational cost — each emitting organization must guard a master seed whose compromise invalidates all past and future signatures. Hardware security modules mitigate this at added cost; the paper lists it as a limitation, not a solved problem.
• ▸OPEN: the LSB and metadata embeddings survive only lossless handling; the paper does not claim robustness to re-encoding, resizing, or aggressive transcoding of carrier files.

Expected direction: CAN: forge/sign new artifacts dated to that same epoch and domain (they hold the valid leaf key), and those will verify until the key is revoked. CANNOT: back-date or forward-date to a different epoch — that needs a different k_epoch, which requires the master secret (one-way derivation); and CANNOT sign in a different domain — that needs a different k_domain branch, again derivable only from the master secret. Revocation with a compromise time also invalidates everything signed after t_revoke.

How does deriving the key from the timestamp make back-dating fail?

The key for one day-epoch is a one-way BIP32 child; a different claimed day means a different required key, whose matching public key is not the registered one, so the signature does not verify — unless the attacker holds the master secret.

What exactly is proven, and what is only estimated, in this part?

Temporal binding is proven by reduction to one-way derivation and EdDSA unforgeability. The ~6 ms verification cost is an estimate on one commodity CPU, not an independently reproduced benchmark.

Why does the append-only key registry let old artifacts keep verifying after a rotation?

Because each signature is bound to its epoch, a verifier selects the key whose validity window contained sourced_at, so historical artifacts verify against the key that was valid when they were signed.