💻 computer science

Finality Before Disclosure for Ledger Authenticators in the Quantum Random Oracle Model

This paper introduces the concept of ledger authenticators and a corresponding unforgeability model ( $\LAEUF$ ) to secure reactive authorization protocols in public ledgers, proving a multi-user quantum security bound in the Quantum Random Oracle Model that accounts for adversarial ordering, censorship, and the critical requirement of closing evidence eligibility before credential disclosure.

Original authors: Maja Lie, Benjamin Marsh

Published 2026-08-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maja Lie, Benjamin Marsh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, a ledger is simply a shared record of who owns what and what has happened. Think of it as a public notebook where every transaction is written down, verified, and added to the history. For decades, the security of these notebooks relied on a single, portable key: a digital signature. Much like a physical signature on a check, this digital mark proved that the owner authorized a specific action. The system was designed so that anyone could verify the signature using a public key, without needing to know the history of the account or the timing of the transaction. This worked well for simple transfers, but modern digital ledgers have become more complex. They now manage state, order events, and rely on the finality of the record—the point where a transaction is considered unchangeable and permanent. The old model of a standalone signature began to feel insufficient for these new, reactive systems, where the validity of an action might depend on what happened just before it or how the network agreed on the order of events.

This shift created a new challenge for security, especially as we look toward a future where powerful quantum computers might break the current encryption methods. Researchers Maja Lie and Benjamin Marsh asked a fundamental question: when a digital ledger authorizes a change, how much of that security comes from the secret key held by the user, and how much comes from the public history of the ledger itself? In many modern systems, the ledger does more than just carry a signature; it helps decide if an action is valid by checking the timeline, the order of events, and the final state of the account. The authors realized that standard security tests, which treat signatures as isolated objects, missed the unique dangers of this environment. They identified that an attacker could potentially exploit the time between when a secret is revealed and when it is officially recorded, or use the ability to delay and reorder transactions to create a forgery.

To solve this, the researchers built a new framework called a "ledger authenticator." This is a model that treats the entire process of authorization as a game played against the ledger's history, rather than just a check of a signature. They introduced a specific test, called LA-EUF, which simulates a scenario where an attacker can watch every honest transaction before it is recorded, delay its inclusion, and even reorder the sequence of events. The goal of this test is to see if the attacker can trick the system into accepting a new, unauthorized action using a secret that was just revealed. The paper proves that for certain types of protocols, security relies on a specific condition: the ledger must "close" the list of possible actions before the secret is revealed. If the system allows new actions to be created after the secret is out, the ledger is vulnerable. However, if the system fixes the list of valid actions based on the final, unchangeable state of the ledger before the secret leaks, the system remains secure.

The researchers demonstrated that this approach works by defining a "commit, close, reveal" process. In this method, a user first commits to an action and waits for the ledger to finalize a specific window of time. Only after this window is closed and the list of valid commitments is fixed does the user reveal the secret. This ensures that even if an attacker sees the secret, they cannot create a new, valid action because the ledger has already locked in the rules for that moment. The authors provided a mathematical proof showing that this method is secure even against quantum computers, provided the system follows these strict timing and finality rules. They showed that the security of the system is not just about the strength of the secret key, but about the precise moment the ledger decides what is allowed.

The study also clarified the limits of this approach. It found that if a protocol relies on a single event that does not depend on the ledger's history, it essentially collapses back into a standard signature scheme, losing the extra protection the ledger could provide. Conversely, if a protocol allows a secret to be reused or rebound to a different action after it is revealed, it is inherently unsafe unless the ledger has already frozen the list of valid actions. The researchers proved that by separating the safety of the system from the speed at which it processes transactions, they could create a robust defense. They showed that safety can be guaranteed even if the network is slow or if an attacker tries to censor honest transactions, as long as the ledger's final state is used to lock down the rules before secrets are exposed.

This work offers a clear path forward for building secure digital ledgers in a post-quantum world. It moves beyond the idea of simply swapping old signatures for new, quantum-resistant ones. Instead, it suggests that the ledger itself should be an active participant in the security argument, using its public, finalized history to prevent fraud. The researchers' findings suggest that the most secure systems will be those that carefully manage the timing of when secrets are revealed and when the rules of the game are set in stone. By doing so, they ensure that the ledger remains a trustworthy record, capable of withstanding even the most sophisticated attacks, without relying on the hope that a secret will never be guessed. The result is a more resilient way to manage digital trust, where the history of the system is as important as the key that starts it.

Technical Summary: Finality Before Disclosure for Ledger Authenticators in the Quantum Random Oracle Model

1. Problem Statement

Current post-quantum ledger authentication is predominantly framed as a direct substitution of classical signature schemes (e.g., ECDSA) with post-quantum alternatives (e.g., ML-DSA, SLH-DSA). This approach treats authentication as a portable, local predicate involving only a public key, a message, and a signature. However, ledger protocols inherently expose additional context: prior transactions, finalized state, timing, and ordering.

The standard unforgeability games (EUF-CMA) fail to capture the specific security dynamics of ledger-based authorization because they omit:

Public Pending Pools: Honest credentials become visible to the adversary before inclusion.
Adversarial Scheduling: The adversary can suppress honest events, reorder transactions, and censor reveals indefinitely.
Finality vs. Inclusion: A distinction between provisional inclusion and immutable finalization is missing.
Transcript-Dependent Verification: Verification often relies on a finalized transcript rather than just a static public key.
Quantum State Persistence: In the Quantum Random Oracle Model (QROM), an adversary may retain quantum state across multiple authorizations and across the "finalization cut," while verifier evaluations on submitted events consume query budgets.

The central question addressed is: Which part of authentication hardness derives from a private credential, and which part derives from the finalized history? Specifically, for protocols where a credential is revealed after a commitment (rebindable reveals), safety requires that no efficient scheduler can make newly constructed evidence eligible for a different action after the credential is disclosed.

2. Methodology and Framework

2.1 Ledger Authenticators and LA-EUF

The authors introduce Ledger Authenticators (LA), a tuple $(Setup, Init, Authorize, Judge)$, where the Judge algorithm is a deterministic public predicate that reads a finalized transcript.

Reactive Authorization: The Authorize algorithm is a reactive protocol that may emit events, read finalized prefixes, and update private state before fixing a canonical action $\tau$ .
LA-EUF Experiment: A multi-user unforgeability game where the adversary controls submission, inclusion, ordering, and finalization calls. The adversary wins if they produce a valid judgment for an action $\tau$ on an uncorrupted account $a$ , where $\tau$ was not requested by the honest process prior to the acceptance step.
Safety vs. Liveness: The model separates safety (no unauthorized redirection of authorization, even under indefinite censorship) from completeness (progress), which is analyzed under explicit liveness assumptions.

2.2 Structural Boundaries

The paper identifies two conditional resource boundaries that determine the security properties of a ledger authenticator:

The Single Event Frontier: Protocols that authorize an action by emitting a single event whose validity depends only on registration state and a fixed public context are shown to be equivalent to contextual one-time signatures. If a protocol satisfies specific "single event" conditions (isolated emission, local completeness, and the ability to embed a censored event into a finalized extension), it collapses to a standard one-time signature scheme.
Eligibility Closure for Rebindable Reveals: For protocols where a credential is revealed after a commitment (e.g., hash preimages), safety requires computational post-disclosure non-admissibility. If a credential $s$ is disclosed, no newly constructed evidence for a different action $\tau'$ should be admissible. If the admission policy relies only on public computation and ledger scheduling, this is enforced by closing the set of eligible evidence in the finalized state before the credential is disclosed.

2.3 The Ledger QROM Execution Model

The authors define a joint execution model where:

A quantum adversary interacts with classical ledger interfaces (mempool, finalization, corruption).
The ledger and honest parties evaluate a common Random Oracle $H$ .
Query Accounting: The model distinguishes between direct quantum queries ( $Q_{adv}$ ), verifier-mediated evaluations ( $Q_{med}$ ), and honest evaluations ( $Q_{hon}$ ). Crucially, verifier-mediated evaluations on adversarial inputs are charged to the query budget, as they provide a classical test dependent on the oracle.
Adaptive Finalized Cuts: The model introduces a "closed finalized cut" where the set of admissible targets becomes immutable. Quantum state persists across this cut; it is not a reset.

2.4 The Finalized Target Lemma

A key technical result is the Finalized Target Search Lemma. For a closed finalized cut with a target set $C$ of size at most $K$ , the probability of a successful fresh target search is bounded by:
$\Pr[W] \le 3\beta_{cut}^2 + \frac{3 c_{co} K Q^2}{2^\lambda} + \frac{6\ell}{2^\lambda}$
Where:

$\beta_{cut}$ accounts for "bad" amplitude (fresh openings already present at the cut).
$Q$ is the total query budget after the cut.
$\ell$ is the number of retained checked points.
$c_{co}$ is a universal constant.

This lemma proves that if the set of eligible targets is fixed (closed) before disclosure, the adversary's success probability scales quadratically with queries ( $Q^2$ ) and linearly with the target set size ( $K$ ), rather than allowing for generic collision attacks.

3. Key Contributions

Definition of Ledger Authenticators and LA-EUF: A formal unforgeability experiment for reactive authorization protocols that incorporates public pending pools, adversarial scheduling, censorship, and transcript-dependent verification. The model shows that ordinary post-quantum signatures embed into this framework, while protocols satisfying single-event conditions yield contextual one-time signatures.
Isolation of the Closure Condition: The paper proves that for rebindable reveal protocols, safety requires that the set of admissible evidence be closed in the finalized state before the credential is disclosed. If this closure does not occur, an adversary can censor the honest reveal and bind the disclosed credential to a new action, resulting in a forgery.
Ledger QROM and Security Bounds: A specification of the Ledger QROM execution model and a proof of a finalized target search rule. This rule accounts for persistent quantum state and charges verifier evaluations. It yields a multi-user lifetime security bound for a Commit, Close, Reveal (CCR) authenticator.

4. Results and Instantiation

The authors instantiate the framework with a Commit, Close, Reveal (CCR) authenticator, a hash-based construction inspired by Guy Fawkes authentication and Fawkescoin.

Construction: The protocol involves committing to an action and a successor head, waiting for a "close" (a finalized window where the set of eligible commitments is frozen), and then revealing the secret.
Security: The CCR scheme satisfies the eligibility closure condition. The authors prove a multi-user lifetime QROM bound for CCR:
$\text{Adv} \le \Delta_{PRF} + \epsilon_{fin} + \epsilon_{can} + \epsilon_{state} + \frac{c_h N_{life}(Q_{head}+1)^2}{2^{\min(\lambda_s, \lambda_h)}} + \frac{c_c K_{life} Q_1^2}{2^{\lambda_c}} + \frac{6\ell_{life}}{2^{\lambda_c}}$
This bound demonstrates that safety is maintained even if the honest reveal is censored, provided the target set is closed before disclosure.

5. Significance and Claims

The paper claims to provide a formal foundation for understanding how ledgers contribute to cryptographic security beyond mere transport.

Reframing Authentication: It argues that ledger authentication is not merely signature substitution but a distinct primitive where the "finalized history" acts as a cryptographic resource.
Safety vs. Portability: The framework highlights a trade-off: ledger authenticators exchange portability (verification without context) for safety derived from consensus and finality.
Necessity of Closure: The paper asserts that for rebindable reveals, "finalized eligibility closure before disclosure" is a necessary condition for safety. Without this, the ledger cannot prevent the binding of a disclosed credential to unauthorized actions.
QROM Realism: By modeling quantum state persistence across finalization cuts and charging verifier evaluations, the paper provides a more accurate security analysis for post-quantum ledger protocols than standard QROM models applied to isolated signatures.

The authors explicitly state they do not claim to be the first to propose temporal remedies (citing Guy Fawkes, Fawkescoin, etc.) but rather to formalize the unforgeability game for the full execution, prove the necessary closure theorem for rebindable reveals, and provide a lifetime QROM analysis that accounts for the specific dynamics of ledger scheduling and censorship.