PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Object Authentication: Context-Closed Post-Quantum Authentication for the WebPKI

Anis Bkakria

arXiv:2608.30004v1cs.CR

TL;DR

Post-quantum WebPKI compression must preserve mutable authorization context, not merely authenticate compressed certificate objects. The paper formalizes context closure and implements LR+ with an update plane for authenticated CA-context state and state-local warm selectors; on a pinned CCADB reconstruction, LR+ substantially reduces warm-path bytes relative to a stateless signed bundle while retaining explicit state and update costs.

  • Problem

    Post-quantum WebPKI authentication becomes bandwidth-intensive, and object-only compression may omit mutable authority facts needed to evaluate a selected certification context.

  • Method

    LR+ formalizes context closure using event-coverage witnesses and typed CA-context dependencies, then separates authenticated authority updates from warm-path state-local dependency references.

  • Results

    296, 776, and 872 bytes are LR+ warm closure costs at the median, p95, and maximum, compared with 3,842, 5,932, and 6,350 bytes for stateless SPB.

  • Takeaways & Limitations

    The pinned reconstruction shows that context-closed semantics can retain a large warm-bandwidth advantage while exposing retained-state and update-plane costs.

  • Takeaways & Limitations

    LR+ is a semantic compression layer rather than a complete browser implementation, and deployment still requires source adapters, browser update-channel integration, and decisions about leaf-local status semantics.

Abstract

from arXiv · show

Post-quantum migration increases WebPKI authentication cost, but authenticating a compressed certificate object does not by itself preserve the mutable authorization context under which a relying party accepts it. We formalize \emph{context closure}: the authenticated projection accepted by a verifier must determine the selected authorization semantics it claims, relative to declared source contracts and event-coverage witnesses. We instantiate this idea with \LRp, a two-plane post-quantum construction that authenticates mutable CA-context state in an update plane while the warm path carries only state-local dependency references selected by explicit profile negotiation. In a pinned CCADB reconstruction, we obtain 44,912 path/view contexts and 16,858 physical CA lineages across Apple, Chrome, Microsoft, and Mozilla views. The core compiler yields $m_{50}=6$, $m_{95}=16$, and $m_{\max}=18$ typed dependencies. A warm LR+ selector therefore costs 296, 776, and 872 bytes at median, p95, and maximum, compared with 3,842, 5,932, and 6,350 bytes for a one-signature stateless bundle carrying the same dependency vector. The retained all-view closure state is 16.15 MB, and per-view lifecycle crossovers range from 19.60 to 50.41 median-path warm authentications/day under the stated checkpoint and update model. The implementation and evaluation artifact are available at https://github.com/nserser/LR-WebPKI

1 Introduction

Post-quantum certificate compression reduces object-authentication cost but can omit mutable authorization facts tied to a selected certification context. The paper formalizes context closure and instantiates LR+ with typed CA-context dependencies, state-local warm selectors, and a two-plane update architecture.

  • Motivation: Post-quantum signatures make WebPKI certificate authentication a bandwidth problem, motivating compressed and state-reusing authentication schemes.The paper distinguishes compression efficiency from preserving the authorization semantics of the selected context.
  • Context closure: A compressed authenticator can verify unchanged certificate objects while omitting an independently mutable authority fact attached to the selected lineage.Such a transcript may authenticate the object yet fail to determine whether the selected context remains admissible.
  • Context closure: Context closure requires accepted authentication information and retained monotone state to determine every independently mutable fact needed for the selected-path decision.Decision-relevant events must be reflected by current authenticated state, excluded by authenticated complete coverage, or neutralized by an authenticated bounded grant.
  • LR+ design: LR+ separates full end-entity validation from retained CA-context terminals and uses explicit profile negotiation for state-local warm selectors.Global state identifiers remain on the update/checkpoint plane, while warm authentication carries references interpreted against installed authenticated state.
  • Evaluation: 44,912 path/view contexts represent 16,858 physical CA-certificate sequences in the pinned CCADB reconstruction.The evaluation uses four configured trust-store views reconstructed from a pinned CCADB archive corpus.
  • Evaluation: 296, 776, and 872 bytes are LR+ warm closure costs at the median, p95, and maximum, versus 3,842, 5,932, and 6,350 bytes for stateless SPB.The retained all-view reference state is 16,150,580 bytes, with per-view median-path crossovers from 19.60 to 50.41 warm authentications/day.

2 Authenticated Object, Wrong Context

The same certificate object can belong to multiple certification contexts, so authenticating the object alone may leave the selected authorization decision ambiguous. The paper uses a two-world example to show how mutable policy, status, distrust, and parent-context state can change while certificate bytes remain unchanged.

  • Compression setting: MTCs and related compression schemes authenticate objects through shared tree state, cached landmarks, or separately distributed authenticated frontiers.These mechanisms address where authentication evidence is carried, not necessarily which mutable authorization context governs acceptance.
  • Multiple contexts: A CA subject and key can be authenticated under two parent contexts, making the same lower certificate compatible with both lineages.The relying party selects one lineage for the semantic authorization decision.
  • Two-world failure: At t1, the certificate bytes and signature remain unchanged while the selected context becomes inadmissible in world w1.A transcript authenticating only unchanged objects therefore cannot distinguish the admissible and inadmissible worlds.
  • Semantic gap: Selected authorization depends on object authenticity, parent context, root-program state, status and distrust state, and time.Thus a cryptographically strong object-only representation can remain semantically incomplete.
  • Design response: LR+ retains terminals for CA authorization lineages rather than for every end-entity certificate.The end-entity certificate stays in baseline evidence, while retained topology scales with CA authorization contexts and CCADB structure.

3 Context-Closed Authentication

Context closure requires accepted authentication, together with retained trusted state, to determine the mutable facts that govern a selected certification context. The paper formalizes completeness and characterizes sufficient coverage through reflected state, complete coverage, or deliberate neutralization.

  • Context closure: Context closure requires accepted transcripts and retained monotone state to determine every independently mutable fact needed for the selected path.The definition is representation-independent: the sufficient context may be explicit data, a commitment, or retained client state.
  • Context closure: The context-omission theorem shows that stronger cryptography cannot close a gap when identical authenticated inputs and verifier state require different selected decisions.The theorem is a separation result: if relevant world distinctions are absent from the compiler input and trusted pre-state, the verifier cannot recover them.
  • Dependency completeness: Dependency completeness requires equal baseline evidence and equal abstractions of every declared mutable dependency to imply equal selected semantics.The condition is explicitly no-hidden-dependency: richer browser or root-program semantics require adding the relevant fact or stream to the declared profile.
  • Event coverage: F, C, and L witnesses respectively determine current state, exclude unrepresented events, or neutralize events through an authenticated grant.A composite descriptor may use different witnesses for different event classes, with its safe horizon set by the minimum constituent horizon.
  • Event coverage: The selected-path characterization requires every decision-relevant event class to be covered by a valid F, C, or L witness through the verification time.Without such coverage, the accepted context is not sufficient; with bound descriptors and deterministic policy/time evaluation, the dependency vector is context-sufficient.
  • Operational boundary: Withholding is handled separately from rollback: monotone epochs prevent reinstalling old state, while path-local horizons eventually make suppressed updates fail closed.A short-lived dependency in an unrelated context does not expire the selected path.

4 LR+: Context-Closed PQ Authentication

LR+ separates authenticated CA-context state updates from compact warm-path selectors, while typed topology binds each selector to the selected lineage and profile. Its update mechanisms provide validated transitions and catch-up, and explicit negotiation handles heterogeneous client views.

  • Two-plane design: LR+ separates infrequent authority updates from repeated warm authentications, which carry compact selectors into previously authenticated state.The design retains CA-context lineages separately from end-entity evidence and keeps global state identifiers off the warm origin message.
  • Dependency state: Typed dependency records encode stream identity, semantic type, authority context, generation, effective value, source contract, horizon, and evidence metadata.Stable references identify streams rather than epochs or current values, while mutable records are retained in authenticated state.
  • Stable topology: The terminal/compiler invariant requires each retained lineage’s terminal to equal the compiler’s current reference vector, with profile changes treated as topology updates.Record-only updates do not rewrite terminals; a compiler/profile change advances the topology version.
  • Update plane: Consecutive deltas, range deltas, and checkpoints provide chained updates, endpoint catch-up, and monotone snapshot recovery on the update plane.Range acceptance recomputes the endpoint commitments and is equivalent to installing a valid consecutive transition sequence, rather than serving as a freshness shortcut.
  • Warm authentication: Warm verification accepts a header plus 48-byte references, then deterministically derives terminal identities and check values from the selected lineage and reference vector.The warm message carries neither the global state identifier nor terminal key and check value; mismatched compiler vectors fail under the binding invariant.
  • Warm authentication: Replayed selectors resolve against current installed state, so changed selected records yield new values or policy failures, while compiler-vector changes invalidate old vectors.If updates are withheld, residual acceptance is bounded by selected dependency horizons and source-contract failure terms.
  • Profile negotiation: Explicit profile negotiation lets origins select a warm selector compatible with each client’s trust-store view and candidate path.This avoids requiring the origin to guess which browser view or CA lineage the client selected.

5 Security of LR+

LR+ provides conditional post-quantum selected-context soundness by independently authenticating update state and interpreting warm selectors against installed authenticated state. Its security bound separates cryptographic failures from source-contract failures and adaptive selected-context choice.

  • Adaptive source failures: The adaptive selected-source failure term evaluates the selected context in the first accepted winning transcript rather than assuming marginal source failures remain marginal after path selection.The probability accounts for experiment randomness, source histories, and the adversary’s adaptive transcript choice.
  • Security theorem: Theorem 3 establishes conditional PQ selected-context soundness for the LR+ profile under ML-DSA-44, SHA-384 commitments, sound validation, trusted time, and declared source contracts.The theorem’s guarantee is conditional on the stated primitive, validation, time, and source assumptions.
  • Adaptive source failures: Corollary 1 recovers a path-local source bound when each source contract supplies an adaptive conditional guarantee for every selected dependency event.The stronger conditional source formulation supports the compact path-local summation.
  • Security construction: LR+ authenticates the update plane independently, while warm selectors are interpreted only against installed authenticated state.The proof treats unauthorized state installation and warm-path acceptance as separate stages.
  • Assumptions and scope: Source-contract errors are operational bounds: a valid update signature authenticates the publisher’s statement but does not establish that upstream source data was true.The text allows protocol guarantees, deployment SLAs, explicit assumptions, or measured source reliability as possible contract bases.
  • Assumptions and scope: The security argument does not itself require a QROM step, while lower-level QROM analyses of ML-DSA or SHA-384-derived instantiations remain modular.The composition proof assumes post-quantum EUF-CMA signatures and quantum collision resistance without programming, reprogramming, or measuring random-oracle queries.

6 WebPKI Evidence and Source Contracts

The evaluation rebuilds a multigraph from a pinned CCADB archive and evaluates typed dependencies separately across four trust-store views. It also makes source-contract requirements explicit for reflected state, coverage claims, and bounded leases, while limiting claims about live deployment data.

  • Evaluation scope: The evaluation uses pinned CCADB data to rebuild CA authorization structure and run the typed compiler over regenerated path/view rows.It does not claim a live browser census, live OCSP/CRLite acquisition, or complete platform-policy reconstruction.
  • CCADB reconstruction: 10,234 records/nodes, 24,653 edges, 365 roots, 228,249 graph paths, and 17,051 active TLS paths comprise the rebuilt graph before per-view expansion.The reconstruction treats certification data as a multigraph rather than forcing it into a tree.
  • Per-view evaluation: 44,912 selected path/view contexts represent 16,858 physical CA-certificate sequences and 72,020 typed dependency records across Apple, Chrome, Microsoft Server Authentication, and Mozilla Websites views.Identical physical lineages remain distinct when trust-store views differ because the selected authorization semantics include the view.
  • Source contracts: A nonce-bearing OCSP response provides reflected state at acquisition time, but a forward horizon requires an explicit source-latency or effectivity contract.The response’s nextUpdate field alone does not prove that no newer revocation exists.
  • Source contracts: CRLite-like coverage mechanisms require an authenticated universe, scope, and coverage cut, while bounded leases represent deliberate acceptance until expiry.LR+ attaches semantic deadlines and does not infer completeness from a filter digest alone.
  • Deployment model: A browser vendor or root-program closure publisher can sign authority-state deltas and checkpoints, while origins send ordinary object authentication plus LR+ warm selectors.MTC can authenticate certificate-issuance objects and CRLite/OCSP can handle selected leaf-local status alongside LR+.

7 Evaluation

The evaluation reconstructs WebPKI path/view contexts from pinned CCADB data, measures typed dependency and communication costs, and tests semantic sensitivity and explicit evaluation boundaries.

  • Typed compilation: The compiler emits typed dependencies with provenance, source contracts, horizons, evidence digests, and correlation metadata.The core profile remains regular in depth, with m(d) = 2 + 2d.
  • Communication: Profile-hint mode sends one state-local selector, while the verifier re-derives the terminal identity and check value from the selected lineage and references.The global state identifier, terminal key, and terminal check value remain off the warm path.
  • Sensitivity: The policy-augmented profile changes the global dependency distribution from 6/16/18 to 7/17/19 and separates equal-depth contexts.This sensitivity experiment adds a root/view policy stream and is not a complete browser-policy reconstruction.
  • Scope: The evaluation covers pinned CCADB reconstruction, typed communication, retained state, checkpoints, and lifecycle costs, but not end-to-end TLS, browser integration, or live authority acquisition.The artifact verifies the protocol and reconstruction pipeline rather than a full browser/TLS benchmark.

8 Lifecycle and Deployment

The lifecycle model compares LR+ background-update and retained-state costs with SPB’s stateless warm-message cost across views and operating assumptions.

  • Cost model: LR+ shifts work into retained state and background updates, whereas SPB carries a larger self-contained object on every warm authentication.The daily model charges one signed update batch and accounts for warm authentications/day, changed records/day, and checkpoint amortization.
  • Per-view lifecycle: 19.60, 37.98, 47.02, and 50.41 warm authentications/day are the LR+–SPB crossover points for Chrome, Mozilla, Apple, and Microsoft, respectively.These values use each view’s median warm sizes, its checkpoint size, H = 30, and k = 16.
  • Sensitivity: Larger checkpoint amortization horizons lower the crossover, while higher update rates increase it.The sensitivity surface evaluates k ∈ {1, 4, 16, 64, 256} and H ∈ {7, 30, 90}.
  • Deployment boundary: LR+ targets high-reuse relying parties, while very low-use fresh clients may prefer SPB.The paper does not claim universal LR+ dominance.
  • Offline recovery: 32,152 bytes is the cost of a seven-day signed range catch-up delta carrying 112 changed records once.Seven consecutive daily deltas would cost 47,656 bytes under the same changed-record setting.

9 Related Work and Scope

The paper positions LR+ as complementary to certificate compression, authenticated state, root-policy frameworks, revocation systems, and cross-signing work.

  • Scope relative to prior work: LR+ addresses whether compressed authentication preserves mutable selected-authorization facts, rather than replacing certificate compression or revocation sources.Its scope includes root/profile state, parent authorization, status or distrust, policy generation, and bounded grants.
  • Policy and trust: Root-store and validation-policy systems make policy semantics or trust more explicit, aligning with LR+’s declared-profile boundary.LR+ asks which mutable policy and authority facts must be authenticated.
  • Conceptual distinction: Context-separable interfaces also make implicit boundaries explicit, but LR+ concerns mutable selected-authorization state rather than secret-key interface reuse.The conceptual overlap is limited to making the context boundary explicit before proving security.
  • Authenticated state: Existing authenticated data structures provide membership, freshness, and completeness tools, while LR+ focuses on sufficiency for selected authorization semantics.The distinction is between authenticating state and proving that the authenticated projection closes the selected context.
  • Cross-signing and PQ migration: Cross-signing creates multiple admissible lineages for one subject/key identity, motivating LR+’s context-closure condition and path-local realization.The paper distinguishes this contribution from caching or Merkle authentication alone.

10 Discussion and Limitations

The discussion scopes LR+ as a semantic compression layer evaluated through reconstruction and lifecycle models, with deployment assumptions and engineering work remaining.

  • Limitations: LR+ is not a complete browser implementation and excludes full TLS integration, live browser telemetry, and live OCSP/CRLite acquisition.The artifact measures retained-state serialization and a lifecycle model.
  • Assumptions: The update publisher is assumed pinned and policy-consistent, while equivocation detection is outside the core theorem.Transparency or witnessing could add equivocation detection.
  • Evaluation boundary: The evaluation uses a pinned CCADB reconstruction rather than traffic-weighted browser telemetry.Per-view state and checkpoint values are structural deployment estimates for a configured browser/root-store profile.
  • Open engineering work: Deployment still requires source adapters, browser update-channel integration, and decisions about leaf-local status semantics.These are identified as remaining engineering work before deployment.

11 Conclusion

LR+ preserves authorization-context semantics during post-quantum WebPKI compression by making mutable CA-context dependencies explicit and reusing authenticated state through state-local warm selectors.

  • F/C/L witnesses close event ambiguity, while typed CA-context dependencies define retained state for context-closed authentication.
  • State-local warm selectors reuse authenticated state without requiring global warm-state synchronization.
  • The pinned CCADB reconstruction reports a large warm-bandwidth advantage over a one-signature stateless baseline for high-reuse relying parties.The comparison is presented together with retained-state and update-plane costs.

A Open Science and Artifact

The artifact defines typed compilation, authenticated state installation, negotiated warm selection, and verification checks for reproducing the paper’s context-closed WebPKI construction.

  • Open Science and Artifact: The implementation and evaluation source is available on GitHub, with README steps for reproducing the reported results.
  • Typed compilation: The compiler emits typed root, authorization, edge, and context-status records ordered into the dependency vector hashed into each terminal.
  • Record identity: Stable references derive from semantic stream identities and remain usable across unrelated record updates.
  • State installation: Consecutive and range deltas require authenticated predecessor and successor consistency, canonical updates, and monotone generations before installation.
  • State installation: Checkpoints authenticate complete mutable maps and topology, but warm acceptance remains bounded by the selected dependency horizon.
  • Warm verification: Warm selectors carry only an 8-byte header and canonical 48-byte stable-reference vectors, which verification resolves against installed authenticated state.
  • View/path negotiation: Profile-hint and catalog modes negotiate exactly one matching profile identifier before warm verification.
  • Failure cases: Wrong views, dependency vectors, predecessors, generations, or selected records cause terminal, update, policy, or horizon checks to fail.

D Adaptive Security Game

The adaptive security game models adversarial updates and selected transcripts, then uses a hybrid proof to reduce accepted invalid warm authentications to explicit bad events and cryptographic assumptions.

  • Game and win condition: The adversary adaptively requests honest transitions, checkpoints, and warm selectors, then wins by producing an accepted transcript whose ideal selected semantics reject.
  • Bad events: Five bad-event classes cover signature forgery, hash or encoding collision, baseline failure, clock failure, and selected-source-contract failure.
  • Hybrid sequence: Game G1 reduces invalid update or checkpoint statements to a PQ-EUF-CMA attack against ML-DSA.
  • Hybrid sequence: Game G2 reduces state, identifier, reference, and evidence collisions to quantum collision resistance.
  • Hybrid sequence: Game G3 aborts on baseline or clock failure, leaving an honestly authenticated publisher state for the remaining argument.
  • State-local warm argument: Because warm selectors omit a global state identifier, verification interprets them against the verifier’s own installed authenticated state.
  • Conclusion: Full-path lifting and compiler completeness bind accepted transcripts to the ideal selected semantics, with residual probability bounded by Theorem 3’s bad-event terms.
Loading 2608.30004v1…