WorksComputer Science
QUASI: Post-Quantum Quorum Attestation of Pre-Validated Statements
Abstract
We present QUASI, a newly conceived class of protocols that enable a group of parties to produce a publicly verifiable attestation about a pre-validated statement. Designed for quorum-based systems, QUASI enables parties to attest to external entities that the statement is valid. Surprisingly, each party need not sign the entire statement: authenticating only a small subset of symbols suffices for the quorum to attest to the whole. A simple deterministic construction illustrates this possibility. Built purely from hashing and error correction, QUASI achieves small per-party contributions and low attestation generation and verification costs, without relying on SNARKs for aggregation. Our main contribution is a randomized construction achieving reductions of more than in per-party contribution size and hash computations for generation and verification, compared with full hash-based signatures. QUASI is a generic primitive supporting diverse applications. Two principal use cases are external attestation for signature-free consensus, enabling clients to verify statements about committed state; and preprocessing for SNARK-based aggregation, compounding QUASI's savings with succinct-proof compression.
Introduction
We present QUASI, a newly conceived class of protocols that enable a group of parties to produce a publicly verifiable attestation about a pre-validated statement. Designed for quorum-based systems, QUASI enables parties to attest to external entities that the statement is valid. The QUASI family is based purely on hashing and incorporates error correction. Its protocols have small per-party contributions compared with full hash-based signatures, have low quorum-attestation generation and verification costs, and do not rely on SNARKs for aggregation.
The need for compact, publicly verifiable post-quantum (PQ) signature aggregation has been articulated in several reports [5, 1]. NIST’s recent Threshold Call identifies aggregation into sublinear-size results, quantum resistance, and ZKP-friendliness as features of interest [6 Sections 3.2 and 11.1]. Our constructions build on one-time hash-based authentication, exemplified by Lamport-OTS [16] and WOTS [18]. Such primitives also underpin hash-based signature management schemes such as XMSS [13] and SLH-DSA [20], which play a prominent role in PQ migration. Hash-based signature schemes lack BLS-style native aggregation: the prevailing approach uses SNARK-based aggregation to compress full signatures contributed by every party [10]. Thus, aggregating 100 hash-based signatures today means either concatenating them ( the size and the verification work) or proving all 100 verifications inside a hash-based SNARK, as in Ethereum’s plan [11].
Core insight and terminology. QUASI is not a signature aggregation scheme, nor does it provide the guarantees of threshold signatures. It addresses a weaker task: honest parties in a quorum-based system have already validated and agreed on a single statement per context, and the goal is to attest to external parties that this statement is valid.
This distinction enables a surprising approach: each party authenticates only a small subset of the symbols that make up the statement, rather than providing a full signature. This is possible because hash-based authentication treats individual input symbols independently. We call a party’s contribution a quasi-signature share (qShare); a quorum of qShares produces a publicly verifiable joint quorum attestation (qAttest). Together, these contributions suffice to recover the entire pre-validated statement and attest to its validity. The number of symbols that a qShare needs to authenticate decreases as the number of parties increases, reaching as few as two symbols per party.
Use-cases. QUASI is a generic primitive supporting diverse applications. As a compelling first use-case, QUASI provides external attestation for signature-free Byzantine consensus protocols and blockchains. These protocols, also known as information-theoretic (IT) consensus protocols, achieve agreement using authenticated point-to-point channels. Examples include IT-HotStuff (IT-HS), Forget-IT, TetraBFT, Simple-IT, Quintus, Floor-IT, DQS and Quantum Cadence [4, 2, 22, 23, 17, 3, 15, 14]. Although these protocols provide post-quantum-secure agreement, their internal authentication does not produce publicly verifiable attestations about committed state. QUASI fills this gap by providing an external attestation layer, enabling clients to verify statements about committed state.
Another use case compounds the QUASI advantage with SNARK-based compression. Advances in SNARK proof systems have improved both general-purpose proving and specialized workloads and brought them into reality: PLONK provides succinct verification with a universal, updatable setup [12], while HyperPlonk enables linear-time proving with high-degree custom gates [8]. More recently, Flock accelerates batched Boolean computations, including standard cryptographic hashes, hash chains, and Merkle-path verification [7]. Taking advance of these advances, Succinct’s Telepathy service is a prominent deployed example of SNARK proofs to compress the attestation originating with Ethereum’s 512-member “sync committee” [21]. A QUASI-based alternative would improve the attestation layer feeding this pipeline; succinct proving could remain a subsequent compression step.
Technical approach. The key idea is to distribute authentication across parties: each party authenticates a small subset of symbols, and a quorum of their contributions jointly attests to the pre-validated statement. The challenge is to prevent corrupt parties from changing any symbols left unauthenticated by honest parties.
To demonstrate this is not impossible, a simple deterministic construction illustrated in the table below addresses this challenge and provides modest savings:
| Statement | |||||
| Party | Symbol assignment | qShare | |||
| ✓ | ✓ | ✓ | |||
| (corrupt) | × | × | × | ||
| ✓ | ✓ | ✓ | |||
| ✓ | ✓ | ✓ | |||
| Valid qAttest | , non-conflicting qShares | ||||
| Invalid qAttest | , conflicting qShares |
Table 3.
Each symbol of the statement is authenticated by parties. Rotating these assignments balances the load, so that each party authenticates approximately two-thirds of . A qShare by a party consists of a hash-based signature over the symbols assigned to it; any standard hash-based signatures may be employed (§ 3 elaborates on one choice). A qAttest contains valid, mutually non-conflicting qShares, ensuring that every symbol is authenticated by at least one honest contributor. While this construction already reduces the per-party contribution by one-third (asymptotically), we are confident that better deterministic parameters are achievable and are currently exploring improved designs.
Our main focus in this paper, however, is on larger systems, where randomization enables more dramatic savings. Here, QUASI authenticates a codeword rather than the statement itself. Provided the number of altered symbols remains within the code’s correction capacity, the symbols authenticated by honest parties suffice to recover the original pre-validated statement. This creates a tradeoff between qShare size and codeword expansion. Table 4.1 illustrates the randomized approach with qShares of two symbols, and a codeword with correcting resilience.
Performance. Compared with a naive collection of hash-based signatures, QUASI targets savings of more than in (i) per-party contribution size, (ii) generation effort, and (iii) verification effort. These gains arise from reducing the number of hash-chain values and preimages maintained or revealed by each party, as well as the hash computations required for generation and verification. For a 256-bit statement digest , QUASI represents the input as symbols over and employs an error-correcting code with expansion. It sets the number of symbols authenticated per qShare to ensure that undetected symbol flipping occurs with probability less than . Table 3 shows a selection of concrete parameters and the resulting savings.
Preliminaries
This work introduces a newly conceived class of attestation protocols named QUASI. A glossary of notations and terms which will be used throughout the construction is provided here.
| Term | Notation | Meaning |
| Statement | , | Input to be certified, has symbols |
| Encoded statement | , | Input expanded thru ECC with rate |
| Symbol space | An alphabet of 8-bit values | |
| Symbol | , , , | The ’th symbol of or |
| QUASI-OTS | A one-time hash-based signature over a word | |
| qShare map | , | Party ’s randomized symbol selection |
| qShare | Party ’s contribution (quasi signature-share) over | |
| qAttest | A full attestation over |
Table 1. A glossary.
In QUASI, a group of parties, up to of which may be corrupt, can produce an attestation about a pre-validated statement on behalf of quorums of parties, and no such quorum can forge an attestation, which the honest parties in the quorum did not intend to provide, except with negligible probability1. We assume an adaptive adversary who may select parties to corrupt at any time.
Parties in the QUASI primitive each hold an independently generated private key for signing, similar to multi-signature schemes [19]; the public keys of all parties are known to everyone. Each party contributes a quasi-signature share (qShare) on a statement, which does not constitute by itself a valid signature on the statement, akin to classical threshold signature schemes [9]. A quorum of qShares produces a joint quorum attestation (qAttest), which is not required to look like a single signature. Furthermore, there is no secrecy guarantees, and a qAttest may reveal and hold accountable who contributed to an attestation, similar to aggregate signature paradigms [5]. The QUASI primitive is thus a hybrid of the three flavors of signature aggregations known in the literature, incorporating and mixing ingredients from all three while not adhering to either one in full.
Most importantly, QUASI is not a signature aggregation scheme, nor does it provide the guarantees of threshold signatures. QUASI is designed for quorum-based systems to attest to a pre-validated statement. The goal is to attest to external parties that this statement is valid.
More formally, a QUASI scheme is defined as follows.
Definition 1 (QUASI). A QUASI scheme is a tuple of probabilistic polynomial-time algorithms involving parties and a threshold with , defined as follows.
. On input a security parameter , and environment parameters , and , outputs public parameters shared by all parties, including: a description of the statement space ; an error correcting code over which includes a expansion parameter ; the quasi signature share (qShare) space which includes a qShare size parameter ; and the quorum attestation (qAttest) space .
. A randomized algorithm run independently by each party ; outputs a verification key and a signing key . The combined verification key is .
. On input the public parameters, party ’s signing key, and a statement , outputs a quasi signature share (qShare) . A qShare does not constitute a valid signature over on its own.
or . On input the public parameters, the combined verification key, an index set with , a statement , and the qShares , outputs either an qAttest signature or a failure symbol .
. On input the public parameters, the combined verification key, a statement , and a purported qAttest , outputs 1 (accept) or 0 (reject).
We require the following properties.
Correctness. For all , all , all statements , all index sets with , and all shares for :
Weak--Unforgeability. For all , all , all probabilistic polynomial-time adversaries controlling a coalition of corrupted parties with , having access to a signing oracle which is allowed to make requests only on a pre-validated :
Transparency. The quorum attestation output by may encode the signing set and is not required to be indistinguishable from a single-signer signature. In particular, no anonymity guarantee is imposed on with respect to the identities of the signers in .
Remarks. It is worthy of noting how Weak--Unforgeability differs from traditional threshold-unforgeability: in the latter, we would allow the adversary to query honest parties on a set of statements, rather than a unique statement ; we would then require negligible forging success probability for all statements , instead of , not queried to any honest party. QUASI is not designed to withstand this form of attack.
Adversary models
We consider two possible adversary models: fully adaptive and semi-adaptive. Both models allow adversary to corrupt up to parties, but differ in when adversary can select which parties to corrupt. In the fully adaptive adversary model, having an access to the oracle, adversary can select parties to corrupt at any point during the protocol execution, which includes immediately before a party executes qShareSign(pp, , ). The semi-adaptive adversary model requires the adversary to commit to specific set of at most parties before the protocol begins. In both models, the adversary can then interact with the remaining honest parties through oracle that provides information about their qShares. The following sections prioritize security against a fully adaptive adversary, however also considers the semi-adaptive model, which enables stronger efficiency advancements.
Performance Measure
Our primary performance measure is the number of input bits authenticated per party, or equivalently, the number of symbols when the symbol size is fixed. For a statement containing symbols, we measure the reduction from authenticating all symbols to authenticating only symbols per qShare, giving a reduction factor of .
The following costs are all derived directly from this measure: the authentication storage required for a qAttest containing qShares, the communication cost of collecting those shares and responding to client queries, and the hash computations required to generate and verify each party’s contribution. Per -symbol authentication costs are inherited directly from the underlying authentication method, such as WOTS, without modification; the savings arise from reducing the number of input symbols it authenticates.
These reductions also benefit SNARK-based aggregation. The attestation size and the hash computations required for verification contribute directly to the input size and verification work represented within the proof. Reducing these quantities relative to a collection of full hash-based signatures therefore yields proportional savings in the corresponding components of the proving workload.
Building Blocks
QUASI-OTS
We employ an underlying hash-based signature scheme for -symbol authentication. Each key pair is used for at most one signing invocation.
Let be the symbol alphabet. QUASI-OTS is a hash-based one-time signature construction for words of symbols, using WOTS to authenticate the concatenated -bit word, including its WOTS checksum. Its standard signing interface is
. Output public parameters specifying the security parameter , the word space , the WOTS instantiation and its parameters, and the signing-key, verification-key, and signature spaces.
. Generate a WOTS key pair for authenticating words in .
. For , concatenate the symbols in their given order and apply WOTS encoding and signing, including the checksum. Output the resulting signature .
. Reject malformed inputs. Otherwise, apply WOTS verification to the same ordered word and its checksum.
QUASI-OTS inherits correctness and one-time unforgeability from the underlying WOTS instantiation. For completeness, we elaborate on the details of the underlying WOTS signing scheme in Appendix A.
Expanding input to a codeword.
We employ a Reed-Solomon error-correcting code (ECC), denote by , over statements (other codes may be substituted if needed).
A statement is represented as a vector of symbols over an alphabet of -bit symbols. We need to make sure that symbol width is sufficiently large. The reason is that employs polynomials over . In order to be able to encode interpolation points, the field must have size at least , i.e., . In our case, usually the statement to sign is a cryptographic digest of length . The smallest that satisfies is . Therefore, henceforth is represented by symbols, each of 8 bits.2
With a code of size , an RS code can correct corruptions in unknown symbols, where . It can correct a combination of corruptions in unknown places with omissions in known places, such that . The expansion factor is . For instance, only-corruption resilience is and only-omission resilience for as well as and for correspondingly.
The QUASI Scheme
A statement is represented as a vector of symbols over an alphabet of 8-bit symbols; denotes the ’th symbol. It is easy to see that unless each symbol of is authenticated by parties, there exists a collection of parties and a symbol such that is not authenticated by any honest party. We refer to such a as a flip-risk, or simply flipped: an adversary could produce a qAttest mixing authenticators over valid symbols by honest parties with authenticators only by corrupt parties over flipped (i.e., modified).
In order to nevertheless get below authenticators per symbol, QUASI authenticates a codeword over , rather than itself. Provided the number of flipped symbols is bounded accordingly, the valid symbols which are authenticated by honest parties suffice to correct these flips. Our goal is ambitious: each party should authenticate only symbols, for a small constant chosen as a function of . Table 4.1 illustrates the QUASI approach with qShares of symbols.
This probabilistic approach creates a tradeoff between the size of per-party qShare contribution and the code resilience. Here we fix the resilience to be one third and employ an encoding with expansion and adjust accordingly. We provide an analysis proving that the adversarial errors remain within the code’s correction capacity with probability for suitable choices of , focusing on and for large systems and on slightly larger for more common system sizes.
The construction
The construction implements the QUASI functionalities defined in § 2:
qSetup. On input the security parameter , the number of parties , and the corruption threshold , check that ; otherwise, output .
Let be the statement space. Choose a deterministic Reed–Solomon encoding with expansion , so that and the code rate is . Let Decode denote its error-and-erasure decoder. Select according to , , , and the bounds in § 4.3.
Run . Let be the signature space of QUASI-OTS, and let the qAttest space be
Output public parameters specifying , , , , , , , , and .
qKeyGen. Each party independently generates a QUASI-OTS key pair
and samples a mapping , choosing each independently and uniformly at random, without repetition. Set
The parties publish their verification keys. The combined verification key is , which also specifies all public mappings.
qShareSign. For a pre-validated statement , party computes and concatenates its selected codeword symbols, in mapping order, into the word
It outputs
Thus, the selected symbols are authenticated as one ordered word, as if they were contiguous. Each party uses its QUASI-OTS key pair for at most one qShareSign invocation.
Valid and non-conflicting qShares. A qShare over is valid if
Two qShares and are non-conflicting if they authenticate identical values at every codeword position covered by both:
qCombine or . Reject if , , or any supplied qShare is malformed. Form the candidate joint quorum attestation, i.e., the qAttest, simply as the collection:
Output if qVerify; otherwise, output . A qAttest therefore contains valid, mutually non-conflicting qShares from at least distinct parties and satisfies the decoding check below.
qVerify. Parse . Reject malformed inputs, statements outside , or attestations containing fewer than distinct parties. Verify that every qShare authenticates the symbols at positions corresponding to ’s published mapping , i.e. for :
| Statement | ||||||||||||||
| Codeword | ||||||||||||||
| Party | : a mapping of party to symbols | qShare | ||||||||||||
| (corrupt) | ||||||||||||||
| Invalid qAttest | no codeword has distance 1 from |
Table 2. QUASI distributes symbol authentication across parties to attest to a pre-validated statement. The probabilistic approach assigns each party to a small number of symbols (here, two) chosen uniformly at random from a codeword , which corrects a bounded number of symbol errors (here, up to four). Symbol , authenticated by the corrupt party , is also authenticated by the honest party . Therefore, an attempt by to change this symbol creates a detectable conflict. Symbol has no honest party authenticating it, so an alteration by goes undetected by individual authentication checks. However, the code detects an error.
Weak-f-Unforgeability
We will show that given a judicial choice of as indicated below, an adversary cannot forge a qAttest on a statement that the honest parties did not intend to attest, except with negligible probability , and use in our concrete instantiations. We ignore the probability that the underlying hash-based authentication is broken and focus on the new threat introduced by qShare assignment failure. It is worth noting that the nature of our construction is that if the count of corrupt colluding parties passes the threshold , the guarantee against forgery need not immediately drop to 0 at , but may gradually decay as the corruption level increases.
Lemma 2. Let over an input . Then contains qShares that pass individual QUASI-OTS signature verification over .
Proof. No matter how was generated, by construction must find qShares and verify them. For each qShare it finds by , the procedure verifies the QUASI-OTS signature over as defined in the lemma statement.
Lemma 3. Let , and let be the set of distinct qShares passing verification inside the procedure ( is well defined by Proposition 2). Suppose there exists a subset of qShares by honest parties which have been queried to qShareSign a statement . Denote by the set of symbols not authenticated by any qShare in (‘holes’). If , where is correctable by the code , then .
Proof. An honest qShare where authenticates the correct value of the ’th symbol . The non-conflicting requirement enforced in qVerify prevents any qShare in from undetectably flipping that value. Hence, the codeword verified inside qVerify has , i.e., the correct value for such symbol.
This leaves the set of ‘holes’, namely, symbols of which are not authenticated by any qShare in and may be undetectably flipped by the remaining qShares in . However, if , the code’s distance, then no other codeword can match in symbols. We obtain that qVerify succeeds iff and the lemma follows.
Lemma 4. Let honest parties generate qShares over . Let the adversary pick a subset of these qShares containing at least distinct ones. Denote by the set of symbols in which are not authenticated by (holes). Then except with negligible probability, .
Proof. The proof is given in the probabilistic analysis below.
Theorem 5 (Weak--Unforgeability). Let . Suppose that honest parties have been queried to qShareSign a statement (if at all). Then except with negligible probability, .
Proof. According to Proposition 2, contains a set of qShares that pass individual QUASI-OTS verification over symbols of . At most of them are corrupt, so there exists a subset containing at least qShares by honest parties which have been queried to qShareSign a statement . Denote by the set of symbols which are not authenticated by any qShare in . By Proposition 4, we have that , except with negligible probability. We obtain that contains and satisfying the conditions of Proposition 3, and as claimed.
Determining
Given are parameters , the number of 8-bit symbols in an input statement; , a security parameter; , , the environment.
The threat against a worst-case (fully adaptive) adversary is as follows: honest parties choose their mappings uniformly at random and publish them along with their public QUASI-OTS keys.
The adaptive adversary may select parties to corrupt after seeing the honest parties’ mappings. In both adversarial models, after the honest parties have authenticated a statement , the adversary can select any subset of honest parties out of the honest qShares and supplement them into a qAttest using the corrupt parties under its control. The adversary wins if the fraction of the symbols in that leaves unauthenticated exceeds , allowing the adversary to undetectably flip one or more symbols.
We determine a lower bound on to guarantee that the adversary wins with probability . Abstractly, this game consists of a set of honest throws , representing the mappings selected by honest parties, where every contains balls. Each throw places balls into bins uniformly at random, such that no two balls in a throw can land in the same bin. For each subset of out of the throws, denote the total number of bins left empty by the throws in . The game’s outcome is the maximum empties over all selections of sets out of the honest throws: . We seek the minimal as a function of , , , such that w.h.p .
Consider a subset of bins; we estimate the probability that there exists a subset of throws that entirely avoid . The probability that avoids the set entirely is . We can bound this probability from above by assuming the selection of bins is fully independent (i.e., allow repetitions):
Crucially, we require , hence .
Since the set of throws are independent, this experiment forms a Bernoulli trial with repetitions, each with success probability . The probability of successes is .
The preceding argument applies to a fixed set of bins. Taking a union bound over all subsets of bins bounds the probability that the maximal number of holes left by any subset exceeds (namely ) as follows:
Since , applying a Chernoff bound yields:
where is KL-divergence with parameters and , where which leads to:
For , Stirling’s approximation gives . We use the upper bound . Combining these bounds and substituting to obtain:
The probability above now depends on two parameters: , the number of symbols per throw, and , the number of overall parties. Given , we can determine an appropriate to achieve the desired security guarantees as , so the probability of more than holes will be negligible in . This provides an explicit formula for in terms of both and ; we will show concrete values for a fixed to obtain the desired security level in the next section.
Semi-adaptive adversary: The bound above assumes the strongest possible adversary for the current setting. If we force the adversary to commit to specific corrupt parties before all parties reveal their selections, we can offer to use and the bound can be tightened to:
Validity (Correctness)
We establish the validity of QUASI under the same setting used in the Weak--Unforgeability proof, with parameters . We will show that honest parties will be able to produce the qAttest with unit probability.
Theorem 6 (Validity). for honest parties producing qShares on .
Proof. honest parties create a set of mutually non-conflicting qShares that pass individual QUASI-OTS signature verification over . for any distribution of qShares, produced by them, including once that omit some of the symbols of .
Concrete Values
The goal of probabilistic constructions is to significantly reduce the bit complexity of signatures, while guaranteeing negligible odds of forging. Given a desired security forging probability , we demonstrate below concrete values that satisfy this security level, using the bounds derived in § 4.
Minimum number of shares per signer
For bounds in § 4.3 to hold, we established that is required for a fully adaptive adversary, and we maintain this requirement through our analysis ( is possible for semi-adaptive adversary, and analyzed below). However, we can show that choosing or is reasonable for a realistic number of participating parties:
Derivation for $d=3 Using the bound from § 4 with and , we receive an upper bound on the probability that parties collectively leave more than ‘holes’ () in the worst case:
| Symbols | 2 | 3 | 4 | 5 | 10 | 21 |
| Reduction | ||||||
| Fully adaptive | ||||||
| Parties | – | 46,588 | 2,950 | 1126 | 208 | 70 |
| Corrupt parties | – | 15,529 | 983 | 375 | 69 | 23 |
| Semi-adaptive | ||||||
| Parties | 36,184 | 2,479 | 988 | 577 | 169 | 64 |
| Corrupt parties | 12,061 | 826 | 329 | 192 | 56 | 21 |
caption: Concrete parameters and savings under fully adaptive and semi-adaptive adversary models
:::
To ensure that this probability is at most , it suffices to have .
Derivation for . Using the same derivation with we receive:
To ensure that this probability is at most , it suffices to have , which is a significant improvement from .
Semi-adaptive adversary Under weaker adversary assumption, we can enable the use of achieving the desired probability guarantees for while reducing the required bound for to only 826.
Generalized strategy
We can generalize the strategy to arbitrary qShare sizes while guaranteeing unforgeability with probability . Table 3 summarizes the results from § 5.1 as well as additional data points to demonstrate scaling for both adversary models, where reduction refers to reduction in the number of signed symbols compared to signing all symbols. Notice that is the largest optimal qShare size for , as for any larger value of , we can use deterministic construction in which every symbol is signed by parties.
Hence, the overall strategy is as follows. The deterministic construction provides a modest improvement for , while for any larger number , we can apply QUASI to achieve a substantially greater improvement reaching over .
Discussion
The construction and analysis leave substantial room to improve the constants. In particular, the union bound used to select is fairly crude, and a tighter analysis may yield smaller qShares or support smaller systems.
Our analysis also gives the adversary considerable freedom: it may choose which parties to corrupt after setup and key generation have completed and the public keys have been published. However, this adaptive choice does not also permit changing those parties’ mappings. Once a party’s mapping is fixed during setup and key generation, it remains fixed even if the party is subsequently corrupted. Accounting more precisely for this restriction may improve the bounds.
Further improvements may come from sharing Winternitz checksum symbols across qShares. Applications may also tolerate a failure probability higher than , allowing more favorable parameters. Likewise, corruption thresholds other than merit exploration. These and other directions offer opportunities to improve efficiency and bring QUASI into practice.
QUASI-OTS: Forming a qShare
In order for a party to authenticate an ordered subset of symbols selected from a codeword , QUASI concatenates the selected symbols in their specified order into a word, and employs WOTS encoding (as if the symbols were contiguous) to sign it. Quasi One-Time Authentication Scheme (QOTS) is thus an adaptation of WOTS that uses its underlying signing and verification algorithms as well as inherits its one-time unforgeability guarantees for the selected symbols. The key distinction is that QOTS authenticates the selected symbols, not the full input statement. For completeness, we describe the construction below, fixing the positions of the selected symbols as part of the verification key and reducing security directly to WOTS. The checksum follows the standard Winternitz approach, and hash-function assumptions depend on the chosen WOTS variant.
Quasi One-Time Authentication Scheme (QOTS) Let be the symbol alphabet, let be the codeword input space. Let be a fixed ordered tuple of distinct positions in . For a statement , define its selected word as:
Let be a one-time signature scheme for words in .
WOTS encoding. For a word , WOTS appends the fixed-length base- encoding of the checksum . The checksum requires symbols. We can then write the resulting encoding as , where are base- checksum digits. Following the basic WOTS construction, the scheme samples an independent secret starting value for each encoded symbol. To create the public endpoint, the scheme constructs hash chains of length with public endpoints . The signature will be defined as . To verify the signature, it is sufficient to check:
Here, denotes successive hash applications of the hash function . Alternatively, a concrete instantiation may instead use the addressed, randomized chains of WOTS+, with its corresponding security assumptions and verification algorithm.
QOTS interface. The scheme is defined as follows. In the terminology of QUASI, its authentication output is a .
. Run for words in . Output .
. Check that contains distinct positions in . Generate . Output and . The assignment is bound to the verification key.
. Check that and output
. Reject malformed inputs. Otherwise, output
Correctness. For every valid , every , and every honestly generated key pair, an honestly generated qShare verifies with probability 1. Indeed, signing and verification apply WOTS to the same word . For the basic hash-chain construction, each component satisfies
Thus, correctness follows directly from WOTS correctness, as completing the hash chain from each signature component yields its corresponding public endpoint.
One-time unforgeability on selected symbols. An adversary receives vk and may request a qShare on one chosen statement . It wins by producing such that it passes verification and . QOTS is one-time unforgeable on selected symbols if every probabilistic polynomial-time adversary wins with probability negligible in .
Security argument. Any successful QOTS forgery immediately yields a WOTS forgery. A reduction embeds its WOTS verification key in , answers the sole QOTS signing query by requesting a WOTS signature on , and outputs . This is a valid signature on a different word. Consequently, QOTS inherits one-time unforgeability from WOTS, with the same success probability.
The role of the checksum parallels that of the unrevealed preimages in Lamport-OTS. An adversary can advance a revealed hash-chain value, thereby increasing its encoded symbol. However, any distinct word either decreases a data symbol or, if all data symbols only increase, decreases the checksum. In either case, some encoded symbol decreases, requiring a chain value that cannot be obtained by merely advancing the revealed values. The underlying WOTS security theorem formalizes this argument under its hash-function assumptions.
Scope and one-time restriction. A qShare authenticates only . It therefore also verifies for statements that agree with at every position in ; this is intentional. Certification of the complete statement is provided by the quorum construction. Each QOTS key pair must be used for at most one signing query. Post-quantum security follows from the same reduction when the underlying WOTS instantiation is secure against quantum polynomial-time adversaries.
References
- [1]Aaronson, S., Boneh, D., Drake, J., Kannan, S., Lindell, Y., and Malkhi, D. Quantum Computing & blockchain. Position paper, Coinbase Independent Advisory Board on Quantum Computing and Blockchain, Apr. 2026.
- [2]Abraham, I., Das, S., Efron, Y., and Komatovic, J. Forget-IT: Optimal good-case latency for information-theoretic BFT. Cryptology ePrint Archive, Paper 2026/355, 2026. Also published at PODC 2026.DOI
- [3]Abraham, I., Efron, Y., Komatovic, J., and Ranchal-Pedrosa, A. Floor-IT: Information-theoretic BFT in partial synchrony with two round good case latency and optimal resilience. Cryptology ePrint Archive, Paper 2026/1496, 2026.
- [4]Abraham, I., and Stern, G. Information theoretic HotStuff. arXiv:2009.12828, 2020.arxiv.org/abs/2009.12828
- [5]Boneh, D., Gentry, C., Lynn, B., and Shacham, H. Aggregate and verifiably encrypted signatures from bilinear maps. In Advances in Cryptology—EUROCRYPT 2003 (2003), E. Biham, Ed., vol. 2656 of Lecture Notes in Computer Science, Springer, pp. 416–432.
- [6]Brandão, L. T. A. N., and Peralta, R. NIST first call for multi-party threshold schemes. NIST Interagency/Internal Report 8214C, National Institute of Standards and Technology, Jan. 2026.
- [7]Bünz, B., Rothblum, R., and Wang, W. Flock: Fast proving for batch boolean computations. Cryptology ePrint Archive, Paper 2026/1329, 2026.arxiv.org/abs/2607.27491
- [8]Chen, B., Bünz, B., Boneh, D., and Zhang, Z. HyperPlonk: Plonk with linear-time prover and high-degree custom gates. In Advances in Cryptology—EUROCRYPT 2023, Proceedings, Part II (2023), C. Hazay and M. Stam, Eds., vol. 14005 of Lecture Notes in Computer Science, Springer, pp. 499–530.DOI
- [9]Desmedt, Y., and Frankel, Y. Shared generation of authenticators and signatures. In Advances in Cryptology – CRYPTO ’91 (1992), vol. 576 of Lecture Notes in Computer Science, Springer, pp. 457–469.
- [10]Drake, J., Khovratovich, D., Kudinov, M., and Wagner, B. Hash-based multisignatures for post-quantum Ethereum. IACR Communications in Cryptology 2, 1 (2025). Article 13.
- [11]Ethereum Foundation Post-Quantum Team. Post-quantum Ethereum. Project website and roadmap. Accessed November 3, 2026.
- [12]Gabizon, A., Williamson, Z. J., and Ciobotaru, O. PLONK: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Paper 2019/953, 2019.
- [13]Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., and Mohaisen, A. XMSS: eXtended merkle signature scheme. RFC 8391, Internet Research Task Force, May 2018.DOI
- [14]Jalalzai, M. M., Klenze, T., and Komatovic, J. Quantum cadence: Post-quantum consensus with multiple concurrent proposers. arXiv:2610.32803, 2026.arxiv.org/abs/2610.32803
- [15]Kniep, Q., Sliwinski, J., and Wattenhofer, R. Byzantine fault-tolerant post-quantum distributed quorum signatures. arXiv:2607.17700, 2026.arxiv.org/abs/2607.17700
- [16]Lamport, L. Constructing digital signatures from a one way function. Tech. Rep. CSL-98, SRI International, Computer Science Laboratory, Oct. 1979.
- [17]Liu, C., Malkhi, D., Nayak, K., and Shrestha, N. Quintus: Two-round good-case information theoretic BFT for n = 5f + 1. Cryptology ePrint Archive, Paper 2026/1520, 2026.
- [18]Merkle, R. C. A certified digital signature. In Advances in Cryptology—CRYPTO ’89 (1990), G. Brassard, Ed., vol. 435 of Lecture Notes in Computer Science, Springer, pp. 218–238.
- [19]Micali, S., Ohta, K., and Reyzin, L. Accountable-subgroup multisignatures. In Proceedings of the 8th ACM Conference on Computer and Communications Security (2001), ACM, pp. 245–254.
- [20]National Institute of Standards and Technology. Stateless hash-based digital signature standard. Federal Information Processing Standards Publication 205, National Institute of Standards and Technology, Aug. 2024.
- [21]Succinct Labs. Introducing Telepathy: The first decentralized and secure zkSNARK interoperability protocol for Ethereum. Blog post. Accessed November 5, 2026.
- [22]Yu, Q., Losa, G., and Wang, X. TetraBFT: Reducing latency of unauthenticated, responsive BFT consensus. arXiv:2405.02615, 2024. Full version of the PODC 2024 paper.arxiv.org/abs/2405.02615
- [23]Yu, Q., Villacis, J., Losa, G., Xiang, Z., and Wang, X. Simple-IT: Practical low-latency signature-free BFT consensus. arXiv:2606.14404, 2026.arxiv.org/abs/2606.14404