betaFeedback

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 10×10\times 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 (100×100 \times the size and 100×100 \times 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 MMb1b_1b2b_2b3b_3b4b_4
PartySymbol assignmentqShare
p1p_1✓✓✓σ1=Sign⁡QOTS(b1∥b2∥b3)\sigma_1 = \operatorname{Sign}_{\mathrm{QOTS}}(b_1 \mathbin\Vert b_2 \mathbin\Vert b_3)
p2p_2 (corrupt)×××σ2=Sign⁡QOTS(b2∗∥b3∗∥b4∗)\sigma_2 = \operatorname{Sign}_{\mathrm{QOTS}}(b_2^* \mathbin\Vert b_3^* \mathbin\Vert b_4^*)
p3p_3✓✓✓σ3=Sign⁡QOTS(b1∥b3∥b4)\sigma_3 = \operatorname{Sign}_{\mathrm{QOTS}}(b_1 \mathbin\Vert b_3 \mathbin\Vert b_4)
p4p_4✓✓✓σ4=Sign⁡QOTS(b2∥b3∥b4)\sigma_4 = \operatorname{Sign}_{\mathrm{QOTS}}(b_2 \mathbin\Vert b_3 \mathbin\Vert b_4)
Valid qAttest(σ1,σ3,σ4)(\sigma_1,\sigma_3,\sigma_4), non-conflicting qShares
Invalid qAttest(σ1,σ2,σ3)(\sigma_1,\sigma_2,\sigma_3), conflicting qShares

Table 3.

Each symbol of the statement MM is authenticated by 2f+12f + 1 parties. Rotating these assignments balances the load, so that each party authenticates approximately two-thirds of MM. A qShare by a party consists of a hash-based signature Sign⁡QOTS\operatorname{Sign}_{\mathrm{QOTS}} over the symbols assigned to it; any standard hash-based signatures may be employed (§ 3 elaborates on one choice). A qAttest contains 2f+12f + 1 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 1/31/3 correcting resilience.

Performance. Compared with a naive collection of hash-based signatures, QUASI targets savings of more than 10×10 \times 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 MM, QUASI represents the input as m=32m = 32 symbols over GF⁡(28)\operatorname{GF}(2^{8}) and employs an error-correcting code with 3×3 \times expansion. It sets the number dd of symbols authenticated per qShare to ensure that undetected symbol flipping occurs with probability less than 2−1282^{-128}. 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.

TermNotationMeaning
StatementMM, mmInput to be certified, has mm symbols
Encoded statementc(M)c(M), m^\hat{m}Input expanded thru ECC with rate ρ=m/m^\rho= m/\hat{m}
Symbol spaceAAAn alphabet of 8-bit values
Symbolbjb_j, cjc_j, MjM_j, c(M)jc(M)_jThe jj’th symbol of MM or c(M)c(M)
QUASI-OTSSign⁡QOTS(w)\operatorname{Sign}_{\mathrm{QOTS}}(w)A one-time hash-based signature over a word ww
qShare mapπi:[d]→[m^]\pi_i : [d] \to[\hat{m}], ddParty ii’s randomized symbol selection
qShareσi(M)\sigma_i(M)Party ii’s contribution (quasi signature-share) over MM
qAttestσ(M)\sigma(M)A full attestation over MM

Table 1. A glossary.

In QUASI, a group of n=3f+1n = 3f + 1 parties, up to ff of which may be corrupt, can produce an attestation about a pre-validated statement on behalf of quorums of ≥2f+1\ge2f + 1 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 ff 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 Π=(qSetup,qKeyGen,qShareSign,qCombine,qVerify)\Pi= (\mathsf{qSetup},\mathsf{qKeyGen},\mathsf{qShareSign},\mathsf{qCombine},\mathsf{qVerify}) involving nn parties p1,…,pnp_1,\ldots,p_n and a threshold ff with 1≤f≤n1 \le f \le n, defined as follows.

  • qSetup(1κ,n,f)→pp\mathsf{qSetup}(1^\kappa,n,f) \to\mathsf{pp}. On input a security parameter κ\kappa, and environment parameters nn, and ff, outputs public parameters pp\mathsf{pp} shared by all parties, including: a description of the statement space M\mathcal{M}; an error correcting code c(⋅)c(\cdot) over M\mathcal{M} which includes a expansion parameter λ\lambda; the quasi signature share (qShare) space Σsh\Sigma_{\mathrm{sh}} which includes a qShare size parameter dd; and the quorum attestation (qAttest) space Σ\Sigma.

  • qKeyGen(pp)→(vki,ski)\mathsf{qKeyGen}(\mathsf{pp}) \to(\mathsf{vk}_i,\mathsf{sk}_i). A randomized algorithm run independently by each party pip_i; outputs a verification key vki\mathsf{vk}_i and a signing key ski\mathsf{sk}_i. The combined verification key is VK=(vk1,…,vkn)\mathsf{VK}=(\mathsf{vk}_1,\ldots,\mathsf{vk}_n).

  • qShareSign(pp,ski,M)→σi\mathsf{qShareSign}(\mathsf{pp},\mathsf{sk}_i,M) \to\sigma_i. On input the public parameters, party PiP_i’s signing key, and a statement M∈MM \in\mathcal{M}, outputs a quasi signature share (qShare) σi∈Σsh\sigma_i \in\Sigma_{\mathrm{sh}}. A qShare does not constitute a valid signature over MM on its own.

  • qCombine(pp,VK,S,M,{σi}i∈S)→σ\mathsf{qCombine}(\mathsf{pp},\mathsf{VK},S,M,\{\sigma_i\}_{i\in S}) \to\sigma or ⊥\bot. On input the public parameters, the combined verification key, an index set S⊆[n]S \subseteq[n] with ∣S∣≥2f+1|S| \ge2f+1, a statement MM, and the qShares {σi}i∈S\{\sigma_i\}_{i\in S}, outputs either an qAttest signature σ∈Σ\sigma\in\Sigma or a failure symbol ⊥\bot.

  • qVerify(pp,VK,M,σ)→{0,1}\mathsf{qVerify}(\mathsf{pp},\mathsf{VK},M,\sigma) \to\{0,1\}. On input the public parameters, the combined verification key, a statement MM, and a purported qAttest σ\sigma, outputs 1 (accept) or 0 (reject).

We require the following properties.

Correctness. For all pp←qSetup(1λ)\mathsf{pp} \gets\mathsf{qSetup}(1^\lambda), all (vki,ski)←qKeyGen(pp)(\mathsf{vk}_i,\mathsf{sk}_i) \gets\mathsf{qKeyGen}(\mathsf{pp}), all statements M∈MM \in\mathcal{M}, all index sets S⊆[n]S \subseteq[n] with ∣S∣≥2f+1|S| \ge2f+1, and all shares σi←qShareSign(pp,ski,M)\sigma_i \gets\mathsf{qShareSign}(\mathsf{pp},\mathsf{sk}_i,M) for i∈Si \in S:

Pr⁡[qVerify(pp,VK,M,qCombine(pp,VK,S,M,{σi}i∈S))=1]=1.\Pr\left[\mathsf{qVerify}(\mathsf{pp},\mathsf{VK},M,\mathsf{qCombine}(\mathsf{pp},\mathsf{VK},S,M,\{\sigma_i\}_{i\in S}))=1\right]=1.

Weak-ff-Unforgeability. For all pp←qSetup(1λ)\mathsf{pp} \gets\mathsf{qSetup}(1^\lambda), all (vki,ski)←qKeyGen(pp)(\mathsf{vk}_i,\mathsf{sk}_i) \gets\mathsf{qKeyGen}(\mathsf{pp}), all probabilistic polynomial-time adversaries A\mathcal{A} controlling a coalition C⊂[n]C \subset[n] of corrupted parties with ∣C∣≤f|C| \le f, having access to a signing oracle OMO^M which is allowed to make qShareSign(pp,ski,M)\mathsf{qShareSign}(\mathsf{pp},\mathsf{sk}_i,M) requests only on a pre-validated MM:

Pr⁡[qVerify(pp,VK,M∗,σ∗)=1 | M∗≠M, σ∗←AOM(pp,VK,{ski}i∈C)]≤negl⁡(κ).\Pr\left[\mathsf{qVerify}(\mathsf{pp},\mathsf{VK},M^*,\sigma^*)=1 \,\middle|\, M^* \ne M,\ \sigma^* \gets\mathcal{A}^{O^M}(\mathsf{pp},\mathsf{VK},\{\mathsf{sk}_i\}_{i\in C})\right] \le\operatorname{negl}(\kappa).

Transparency. The quorum attestation σ\sigma output by qCombine\mathsf{qCombine} may encode the signing set SS and is not required to be indistinguishable from a single-signer signature. In particular, no anonymity guarantee is imposed on σ\sigma with respect to the identities of the signers in SS.

Remarks. It is worthy of noting how Weak-ff-Unforgeability differs from traditional threshold-unforgeability: in the latter, we would allow the adversary to query honest parties on a set Q\mathcal{Q} of statements, rather than a unique statement MM; we would then require negligible forging success probability for all statements M∗∉QM^* \notin\mathcal{Q}, instead of M∗≠MM^* \ne M, 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 ff 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 ff parties to corrupt at any point during the protocol execution, which includes immediately before a party executes qShareSign(pp, skisk_i, MM). The semi-adaptive adversary model requires the adversary to commit to specific set of at most ff parties before the protocol begins. In both models, the adversary can then interact with the remaining 2f+12f + 1 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 MM containing mm symbols, we measure the reduction from authenticating all mm symbols to authenticating only dd symbols per qShare, giving a reduction factor of m/dm/d.

The following costs are all derived directly from this measure: the authentication storage required for a qAttest containing 2f+12f + 1 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 dd-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 dd-symbol authentication. Each key pair is used for at most one signing invocation.

Let A={0,1}8\mathcal{A} = \{0,1\}^{8} be the symbol alphabet. QUASI-OTS is a hash-based one-time signature construction for words of dd symbols, using WOTS to authenticate the concatenated 8d8d-bit word, including its WOTS checksum. Its standard signing interface is

ΠQOTS=(SetupQOTS,KeyGenQOTS,SignQOTS,VerifyQOTS).\Pi_{\mathrm{QOTS}} = (\mathrm{Setup}_{\mathrm{QOTS}}, \mathrm{KeyGen}_{\mathrm{QOTS}}, \mathrm{Sign}_{\mathrm{QOTS}}, \mathrm{Verify}_{\mathrm{QOTS}}).
  • SetupQOTS(1κ,d)→ppQOTS\mathrm{Setup}_{\mathrm{QOTS}}(1^{\kappa}, d) \to\mathrm{pp}_{\mathrm{QOTS}}. Output public parameters specifying the security parameter κ\kappa, the word space Ad\mathcal{A}^{d}, the WOTS instantiation and its parameters, and the signing-key, verification-key, and signature spaces.

  • KeyGenQOTS(ppQOTS)→(vkQOTS,skQOTS)\mathrm{KeyGen}_{\mathrm{QOTS}}(\mathrm{pp}_{\mathrm{QOTS}}) \to(\mathrm{vk}^{\mathrm{QOTS}}, \mathrm{sk}^{\mathrm{QOTS}}). Generate a WOTS key pair for authenticating words in Ad\mathcal{A}^{d}.

  • Sign⁡QOTS(ppQOTS,skQOTS,a)→τ\operatorname{Sign}_{\mathrm{QOTS}}(\mathrm{pp}_{\mathrm{QOTS}},\mathrm{sk}^{\mathrm{QOTS}}, a) \to\tau. For a=a1⋯ad∈Ada = a_1 \cdots a_d \in\mathcal{A}^d, concatenate the symbols in their given order and apply WOTS encoding and signing, including the checksum. Output the resulting signature τ\tau.

  • Verify⁡QOTS(ppQOTS,vkQOTS,a,τ)→{0,1}\operatorname{Verify}_{\mathrm{QOTS}}(\mathrm{pp}_{\mathrm{QOTS}},\mathrm{vk}^{\mathrm{QOTS}}, a, \tau) \to\{0,1\}. 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 RS(⋅)RS(\cdot), over statements M∈MM \in\mathcal{M} (other codes may be substituted if needed).

A statement MM is represented as a vector of m=∣M∣/wm = |M|/w symbols over an alphabet of ww-bit symbols. We need to make sure that symbol width ww is sufficiently large. The reason is that RSRS employs polynomials over GF(2w)GF(2^w). In order to be able to encode mm interpolation points, the field GF(2w)GF(2^w) must have size at least mm, i.e., 2w≥m2^w \ge m. In our case, usually the statement to sign is a cryptographic digest of length m=2562m = 256^2. The smallest ww that satisfies 2w≥2562^w \ge256 is w=8w = 8. Therefore, henceforth MM is represented by m=32m = 32 symbols, each of 8 bits.2

With a code of size m^=∣RS(M)∣=λm\hat{m} = |RS(M)| = \lambda m, an RS code can correct ee corruptions in unknown symbols, where 2e≤(λ−1)m2e \le(\lambda- 1)m. It can correct a combination of ee corruptions in unknown places with oo omissions in known places, such that 2e+o≤(λ−1)m2e + o \le(\lambda- 1)m. The expansion factor is λ=m^/m\lambda= \hat{m}/m. For instance, only-corruption resilience is 1/31/3 and only-omission resilience 2/32/3 for λ=3\lambda= 3 as well as 2/52/5 and 4/54/5 for λ=5\lambda= 5 correspondingly.

The QUASI Scheme

A statement MM is represented as a vector of m=∣M∣/8m = |M|/8 symbols over an alphabet A\mathcal{A} of 8-bit symbols; M∣jM_{\mid j} denotes the jj’th symbol. It is easy to see that unless each symbol of MM is authenticated by 2f+12f+1 parties, there exists a collection of 2f+12f+1 parties and a symbol b∗=M∣∗b^* = M_{\mid*} such that b∗b^* is not authenticated by any honest party. We refer to such a b∗b^* as a flip-risk, or simply flipped: an adversary could produce a qAttest mixing authenticators over valid MM symbols by honest parties with authenticators only by corrupt parties over b∗b^* flipped (i.e., modified).

In order to nevertheless get below 2f+12f+1 authenticators per MM symbol, QUASI authenticates a codeword c(M)c(M) over MM, rather than MM 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 dd symbols, for a small constant dd chosen as a function of nn. Table 4.1 illustrates the QUASI approach with qShares of d=2d = 2 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 c(M)c(M) with expansion λ=3\lambda= 3 and adjust dd accordingly. We provide an analysis proving that the adversarial errors remain within the code’s correction capacity with probability 1−2−1281 - 2^{-128} for suitable choices of dd, focusing on d=2d = 2 and d=3d = 3 for large systems and on slightly larger dd for more common system sizes.

The construction

The construction implements the QUASI functionalities defined in § 2:

qSetup(1κ,n,f)→pp(1^{\kappa}, n, f) \to\mathrm{pp}. On input the security parameter κ\kappa, the number of parties nn, and the corruption threshold ff, check that n=3f+1n = 3f+1; otherwise, output ⊥\perp.

Let M=Am\mathcal{M} = \mathcal{A}^{m} be the statement space. Choose a deterministic Reed–Solomon encoding c:Am→Am^c : \mathcal{A}^{m} \to\mathcal{A}^{\hat{m}} with expansion λ=3\lambda= 3, so that m^=3m\hat{m} = 3m and the code rate is 1/31/3. Let Decode denote its error-and-erasure decoder. Select dd according to nn, ff, κ\kappa, and the bounds in § 4.3.

Run ppQOTS←SetupQOTS(1κ,d)\mathrm{pp}_{\mathrm{QOTS}} \leftarrow\mathrm{Setup}_{\mathrm{QOTS}}(1^{\kappa}, d). Let Σsh\Sigma_{\mathrm{sh}} be the signature space of QUASI-OTS, and let the qAttest space be

Σ:={{σi}i∈S∣S⊆[n], ∣S∣=2f+1, σi∈Σsh}.\Sigma:= \left\{ \{\sigma_i\}_{i \in S} \mid S \subseteq[n],\ |S| = 2f+1,\ \sigma_i \in\Sigma_{\mathrm{sh}} \right\}.

Output public parameters pp\mathrm{pp} specifying nn, ff, M\mathcal{M}, cc, λ\lambda, dd, ppQOTS\mathrm{pp}_{\mathrm{QOTS}}, Σsh\Sigma_{\mathrm{sh}}, and Σ\Sigma.

qKeyGen(pp)→(vki,ski)(\mathrm{pp}) \to(\mathrm{vk}_i,\mathrm{sk}_i). Each party pip_i independently generates a QUASI-OTS key pair

(vkiQOTS,skiQOTS)←KeyGenQOTS(ppQOTS)(\mathrm{vk}^{\mathrm{QOTS}}_i,\mathrm{sk}^{\mathrm{QOTS}}_i) \leftarrow\mathrm{KeyGen}_{\mathrm{QOTS}}(\mathrm{pp}_{\mathrm{QOTS}})

and samples a mapping πi:[d]→[m^]\pi_i : [d] \to[\hat{m}], choosing each πi(j)\pi_i(j) independently and uniformly at random, without repetition. Set

vki=(πi,vkiQOTS),ski=(πi,skiQOTS).\mathrm{vk}_i = (\pi_i,\mathrm{vk}^{\mathrm{QOTS}}_i), \qquad\mathrm{sk}_i = (\pi_i,\mathrm{sk}^{\mathrm{QOTS}}_i).

The parties publish their verification keys. The combined verification key is VK=(vk1,…,vkn)\mathrm{VK} = (\mathrm{vk}_1,\ldots,\mathrm{vk}_n), which also specifies all public mappings.

qShareSign(pp,ski,M)→σi(\mathrm{pp},\mathrm{sk}_i, M) \to\sigma_i. For a pre-validated statement M∈MM \in\mathcal{M}, party pip_i computes c(M)c(M) and concatenates its selected codeword symbols, in mapping order, into the word

ai:=c(M)∣πi(1)⋯c(M)∣πi(d).a_i := c(M)|_{\pi_i(1)} \cdots c(M)|_{\pi_i(d)}.

It outputs

σi←SignQOTS(ppQOTS,skiQOTS,ai)\sigma_i \leftarrow\mathrm{Sign}_{\mathrm{QOTS}}(\mathrm{pp}_{\mathrm{QOTS}},\mathrm{sk}^{\mathrm{QOTS}}_i,a_i)

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 σi\sigma_i over ai∈Ada_i \in\mathcal{A}^{d} is valid if

VerifyQOTS(ppQOTS,vkiQOTS,ai,σi)=1.\mathrm{Verify}_{\mathrm{QOTS}}(\mathrm{pp}_{\mathrm{QOTS}},\mathrm{vk}^{\mathrm{QOTS}}_i,a_i,\sigma_i) = 1.

Two qShares σi\sigma_i and σk\sigma_k are non-conflicting if they authenticate identical values at every codeword position covered by both:

∀u,v∈[d]:πi(u)=πk(v)⟹ai∣u=ak∣v.\forall u,v \in[d] : \quad\pi_i(u) = \pi_k(v) \Longrightarrow a_i|_u = a_k|_v.

qCombine(pp,VK,S,M,{σi}i∈S)→σ(\mathrm{pp}, \mathrm{VK}, S, M, \{\sigma_i\}_{i\in S}) \to\sigma or ⊥\bot. Reject if S⊈[n]S \not\subseteq[n], ∣S∣<2f+1|S| < 2f+1, or any supplied qShare is malformed. Form the candidate joint quorum attestation, i.e., the qAttest, simply as the collection:

σ=(S,{σi}i∈S).\sigma= (S, \{\sigma_i\}_{i\in S}).

Output σ\sigma if qVerify(pp,VK,M,σ)=1(\mathrm{pp}, \mathrm{VK}, M, \sigma) = 1; otherwise, output ⊥\bot. A qAttest therefore contains valid, mutually non-conflicting qShares from at least 2f+12f+1 distinct parties and satisfies the decoding check below.

qVerify(pp,VK,M,σ)→{0,1}(\mathrm{pp}, \mathrm{VK}, M, \sigma) \to\{0,1\}. Parse σ=(S,{σi}i∈S)\sigma= (S, \{\sigma_i\}_{i\in S}). Reject malformed inputs, statements outside M\mathcal{M}, or attestations containing fewer than 2f+12f+1 distinct parties. Verify that every qShare σi\sigma_i authenticates the c(M)c(M) symbols at positions corresponding to pip_i’s published mapping πi\pi_i, i.e. for ai:=(c(M)∣πi(1)⋯c(M)∣πi(d))a_i := (c(M)|_{\pi_i(1)} \cdots c(M)|_{\pi_i(d)}):

Verify⁡QOTS(ppQOTS,vkiQOTS,ai,σi)=1.\operatorname{Verify}_{\mathrm{QOTS}}(\mathrm{pp}_{\mathrm{QOTS}}, \mathrm{vk}_{i}^{\mathrm{QOTS}}, a_i, \sigma_i) = 1.
Statement MMb1b_1b2b_2b3b_3b4b_4
Codeword c(M)c(M)c1c_1c2c_2c3c_3c4c_4c5c_5c6c_6c7c_7c8c_8c9c_9c10c_{10}c11c_{11}c12c_{12}
Partyπi\pi_i: a mapping of party pip_i to symbolsqShare
p1p_1✓\checkmark✓\checkmarkσ1=Sign⁡QOTS(c2∥c6)\sigma_1 = \operatorname{Sign}_{\mathrm{QOTS}}(c_2 \mathbin\Vert c_6)
p2p_2✓\checkmark✓\checkmarkσ2=Sign⁡QOTS(c5∥c9)\sigma_2 = \operatorname{Sign}_{\mathrm{QOTS}}(c_5 \mathbin\Vert c_9)
p3p_3 (corrupt)✓\checkmark×\timesσ3=Sign⁡QOTS(c5∥c8′)\sigma_3 = \operatorname{Sign}_{\mathrm{QOTS}}(c_5 \mathbin\Vert c_8')
p4p_4✓\checkmark✓\checkmarkσ4=Sign⁡QOTS(c1∥c11)\sigma_4 = \operatorname{Sign}_{\mathrm{QOTS}}(c_1 \mathbin\Vert c_{11})
⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots
pn−1p_{n-1}✓\checkmark✓\checkmarkσn−1=Sign⁡QOTS(c3∥c12)\sigma_{n-1} = \operatorname{Sign}_{\mathrm{QOTS}}(c_3 \mathbin\Vert c_{12})
pnp_n✓\checkmark✓\checkmarkσn=Sign⁡QOTS(c4∥c7)\sigma_n = \operatorname{Sign}_{\mathrm{QOTS}}(c_4 \mathbin\Vert c_7)
Invalid qAttest(σ1,σ2,σ3,…,σ2f+1)(\sigma_1, \sigma_2, \sigma_3, \ldots, \sigma_{2f+1})no codeword c(M′)c(M') has distance 1 from c(M)c(M)

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 c(M)c(M), which corrects a bounded number of symbol errors (here, up to four). Symbol c5c_5, authenticated by the corrupt party p3p_3, is also authenticated by the honest party p2p_2. Therefore, an attempt by p3p_3 to change this symbol creates a detectable conflict. Symbol c8c_8 has no honest party authenticating it, so an alteration by p3p_3 goes undetected by individual authentication checks. However, the code detects an error.

Weak-f-Unforgeability

We will show that given a judicial choice of dd 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 2−κ2^{-\kappa}, and use κ=128\kappa= 128 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 ff, the guarantee against forgery need not immediately drop to 0 at f+1f+1, but may gradually decay as the corruption level increases.

Lemma 2. Let qVerify(pp,VK,M′,σ′)=1qVerify(\mathrm{pp}, \mathrm{VK}, M', \sigma') = 1 over an input σ′\sigma'. Then σ′\sigma' contains 2f+12f+1 qShares σi\sigma_i that pass individual QUASI-OTS signature verification over ai=(c(M′)∣πi(1)⋯c(M′)∣πi(d))a_i = (c(M')|_{\pi_i(1)} \cdots c(M')|_{\pi_i(d)}).

Proof. No matter how σ′\sigma' was generated, by construction qVerifyqVerify must find 2f+12f+1 qShares and verify them. For each qShare σi\sigma_i it finds by πi\pi_i, the procedure verifies the QUASI-OTS signature over aia_i as defined in the lemma statement.

Lemma 3. Let qVerify(pp,VK,M′,σ′)=1qVerify(\mathrm{pp}, \mathrm{VK}, M', \sigma') = 1, and let SS be the set of 2f+12f+1 distinct qShares passing verification inside the procedure (SS is well defined by Proposition 2). Suppose there exists a subset S′⊂SS' \subset S of f+1f+1 qShares by honest parties which have been queried to qShareSign a statement MM. Denote by EE the set of c(M)c(M) symbols not authenticated by any qShare in S′S' (‘holes’). If ∣E∣≤e|E| \le e, where e=m^/3e = \hat{m}/3 is correctable by the code c(M)c(M), then M′=MM' = M.

Proof. An honest qShare σi∈S′\sigma_i \in S' where j∈πij \in\pi_i authenticates the correct value of the jj’th symbol c(M)∣jc(M)|_j. The non-conflicting requirement enforced in qVerify prevents any qShare in SS from undetectably flipping that value. Hence, the codeword c(M′)c(M') verified inside qVerify has c(M′)∣j=c(M)∣jc(M')|_j = c(M)|_j, i.e., the correct c(M)c(M) value for such jj symbol.

This leaves the set EE of ‘holes’, namely, symbols of c(M)c(M) which are not authenticated by any qShare in S′S' and may be undetectably flipped by the remaining qShares in SS. However, if ∣E∣≤e|E| \le e, the code’s distance, then no other codeword can match c(M)c(M) in m^−e\hat{m} - e symbols. We obtain that qVerify succeeds iff c(M′)=c(M)c(M') = c(M) and the lemma follows.

Lemma 4. Let 2f+12f+1 honest parties generate qShares over MM. Let the adversary pick a subset S′S' of these qShares containing at least f+1f+1 distinct ones. Denote by EE the set of symbols in c(M)c(M) which are not authenticated by S′S' (holes). Then except with negligible probability, ∣E∣≤m^/3|E| \le\hat{m}/3.

Proof. The proof is given in the probabilistic analysis below.

Theorem 5 (Weak-ff-Unforgeability). Let qVerify(pp,VK,M′,σ′)=1qVerify(\mathrm{pp}, \mathrm{VK}, M', \sigma') = 1. Suppose that honest parties have been queried to qShareSign a statement MM (if at all). Then except with negligible probability, M=M′M = M'.

Proof. According to Proposition 2, σ′\sigma' contains a set SS of 2f+12f+1 qShares σi\sigma_i that pass individual QUASI-OTS verification over symbols of c(M′)c(M'). At most ff of them are corrupt, so there exists a subset S′⊂SS' \subset S containing at least f+1f+1 qShares by honest parties which have been queried to qShareSign a statement MM. Denote by EE the set of c(M)c(M) symbols which are not authenticated by any qShare in S′S'. By Proposition 4, we have that ∣E∣≤m^/3|E| \le\hat{m}/3, except with negligible probability. We obtain that σ′\sigma' contains SS and S′S' satisfying the conditions of Proposition 3, and M′=MM' = M as claimed.

Determining dd

Given are parameters m=32m = 32, the number of 8-bit symbols in an input statement; κ\kappa, a security parameter; nn, ff, the environment.

The threat against a worst-case (fully adaptive) adversary is as follows: honest parties choose their mappings [d]→[m^][d] \to[\hat{m}] uniformly at random and publish them along with their public QUASI-OTS keys.

The adaptive adversary may select ff parties to corrupt after seeing the honest parties’ mappings. In both adversarial models, after the 2f+12f+1 honest parties have authenticated a statement MM, the adversary can select any subset S′S' of f+1f+1 honest parties out of the 2f+12f+1 honest qShares and supplement them into a qAttest using the ff corrupt parties under its control. The adversary wins if the fraction of the symbols in c(M)c(M) that S′S' leaves unauthenticated exceeds m=m^/3m=\hat{m}/3, allowing the adversary to undetectably flip one or more symbols.

We determine a lower bound on dd to guarantee that the adversary wins with probability <2−128<2^{-128}. Abstractly, this game consists of a set of 3f+13f+1 honest throws {πi}i=1..(3f+1)\{\pi_i\}_{i=1..(3f+1)}, representing the mappings πi\pi_i selected by honest parties, where every πi\pi_i contains dd balls. Each throw places dd balls into m^\hat{m} bins uniformly at random, such that no two balls in a throw can land in the same bin. For each subset S′S' of f+1f+1 out of the 3f+13f+1 throws, denote E(S′)E(S') the total number of bins left empty by the throws in S′S'. The game’s outcome is the maximum empties over all selections of sets S′S' out of the 3f+13f+1 honest throws: eactual:=max⁡{E(S′)∣∣S′∣=f+1}e_{actual}:=\max\{E(S')\mid|S'|=f+1\}. We seek the minimal dd as a function of mm, nn, ff, such that w.h.p eactual≤m^/3e_{actual}\leq\hat{m}/3.

Consider a subset TT of m^/3\hat{m}/3 bins; we estimate the probability that there exists a subset of f+1f+1 throws that entirely avoid TT. The probability that πi\pi_i avoids the set TT entirely is (m^−(m^/3)d)⋅(m^d)−1\binom{\hat{m}-(\hat{m}/3)}{d}\cdot\binom{\hat{m}}{d}^{-1}. We can bound this probability from above by assuming the selection of dd bins is fully independent (i.e., allow repetitions):

(m^−(m^/3)d)⋅(m^d)−1≤(m^−(m^/3)m^)d=(23)d=q\binom{\hat{m}-(\hat{m}/3)}{d}\cdot\binom{\hat{m}}{d}^{-1}\leq\left(\frac{\hat{m}-(\hat{m}/3)}{\hat{m}}\right)^d=\left(\frac{2}{3}\right)^d=q

Crucially, we require d>2d>2, hence q<1/3q<1/3.

Since the set of 3f+13f+1 throws are independent, this experiment forms a Bernoulli trial with 3f+13f+1 repetitions, each with success probability qq. The probability of f+1f+1 successes is Pr⁡[Bin⁡(3f+1,q)≥f+1]\Pr[\operatorname{Bin}(3f+1,q)\geq f+1].

The preceding argument applies to a fixed set of bins. Taking a union bound over all subsets of m^/3\hat{m}/3 bins bounds the probability that the maximal number of holes left by any subset S′S' exceeds m^/3\hat{m}/3 (namely eactual≥m^/3e_{actual}\geq\hat{m}/3) as follows:

Pr⁡[eactual>m^/3]≤(m^m^/3)Pr⁡[Bin⁡(3f+1,q)≥f+1].\Pr[e_{actual}>\hat{m}/3]\leq\binom{\hat{m}}{\hat{m}/3}\Pr[\operatorname{Bin}(3f+1,q)\geq f+1].

Since q<1/3q<1/3, applying a Chernoff bound yields:

Pr⁡[Bin⁡(3f+1,q)≥f+1]≤Pr⁡[Bin⁡(3f+1,q)≥(3f+1)/3]≤exp⁡(−(3f+1)⋅DKL(13∥q))\Pr[\operatorname{Bin}(3f+1,q)\geq f+1]\leq\Pr[\operatorname{Bin}(3f+1,q)\geq(3f+1)/3]\leq\exp\left(-(3f+1)\cdot D_{\mathrm{KL}}\left(\frac{1}{3}\middle\|q\right)\right)

where DKLD_{\mathrm{KL}} is KL-divergence with parameters a=13a=\frac{1}{3} and qq, where DKL(13∥q)=−13ln⁡(274q(1−q)2)D_{\mathrm{KL}}\left(\frac{1}{3}\middle\|q\right)=-\frac{1}{3}\ln\left(\frac{27}{4}q(1-q)^2\right) which leads to:

Pr⁡[Bin⁡(3f+1,q)≥f+1]≤(274q(1−q)2)(3f+1)/3.\Pr[\operatorname{Bin}(3f+1,q)\geq f+1]\leq\left(\frac{27}{4}q(1-q)^2\right)^{(3f+1)/3}.

For m^=3m\hat{m}=3m, Stirling’s approximation gives (3mm)≈(27/4)m3/(4πm)\binom{3m}{m}\approx(27/4)^m\sqrt{3/(4\pi m)}. We use the upper bound (3mm)≤(27/4)m\binom{3m}{m}\leq(27/4)^m. Combining these bounds and substituting q=(2/3)dq=(2/3)^d to obtain:

Pr⁡[eactual>m^/3]≤(274)m+(3f+1)/3[(23)d(1−(23)d)2](3f+1)/3\Pr[e_{actual}>\hat{m}/3]\leq\left(\frac{27}{4}\right)^{m+(3f+1)/3}\left[\left(\frac{2}{3}\right)^d\left(1-\left(\frac{2}{3}\right)^d\right)^2\right]^{(3f+1)/3}

The probability above now depends on two parameters: dd, the number of symbols per throw, and 3f+13f+1, the number of overall parties. Given 3f+13f+1, we can determine an appropriate dd to achieve the desired security guarantees as d(3f+1)=m^ln⁡m^+αm^d(3f+1)=\hat{m}\ln\hat{m}+\alpha\hat{m}, so the probability of more than m^/3\hat{m}/3 holes will be negligible in α\alpha. This provides an explicit formula for dd in terms of both ff and mm; we will show concrete values for a fixed m=32m=32 to obtain the desired security level 1−2−1281-2^{-128} 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 ff corrupt parties before all parties reveal their πi\pi_i selections, we can offer to use d=2d=2 and the bound can be tightened to:

Pr⁡[eactual′>m^/3]≤(274)m[4(23)d(1−(23)d)](2f+1)/2.\Pr[e'_{\mathrm{actual}}>\hat{m}/3]\le\left(\frac{27}{4}\right)^m\left[4\left(\frac{2}{3}\right)^d\left(1-\left(\frac{2}{3}\right)^d\right)\right]^{(2f+1)/2}.

Validity (Correctness)

We establish the validity of QUASI under the same setting used in the Weak-ff-Unforgeability proof, with parameters (κ,n=3f+1,d)(\kappa,n=3f+1,d). We will show that honest parties will be able to produce the qAttest with unit probability.

Theorem 6 (Validity). qVerify(pp,VK,M,σ′)=1qVerify(\mathrm{pp},\mathrm{VK},M,\sigma')=1 for 2f+12f+1 honest parties producing qShares on MM.

Proof. 2f+12f+1 honest parties create a set of mutually non-conflicting qShares σ′\sigma' that pass individual QUASI-OTS signature verification over c(M)∣πi(1)⋯c(M)∣πi(d)c(M)|_{\pi_i(1)}\cdots c(M)|_{\pi_i(d)}. qVerify(pp,VK,M,σ′)=1qVerify(\mathrm{pp},\mathrm{VK},M,\sigma')=1 for any distribution of qShares, produced by them, including once that omit some of the symbols of c(M)c(M).

Concrete dd 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 2−1282^{-128}, 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 d>2d>2 is required for a fully adaptive adversary, and we maintain this requirement through our analysis (d=2d=2 is possible for semi-adaptive adversary, and analyzed below). However, we can show that choosing d=3d=3 or d=4d=4 is reasonable for a realistic number of participating parties:

Derivation for $d=3 Using the bound from § 4 with d=3d=3 and m=32m=32, we receive an upper bound on the probability that f+1f+1 parties collectively leave more than m^/3\hat{m}/3 ‘holes’ (eactual>m^/3e_{\mathrm{actual}}>\hat{m}/3) in the worst case:

Symbols dd23451021
Reduction m/dm/d×16\times16×10.7\times10.7×8\times8×6.4\times6.4×3.2\times3.2×1.5\times1.5
Fully adaptive
Parties nn–46,5882,950112620870
Corrupt parties ff–15,5299833756923
Semi-adaptive
Parties nn36,1842,47998857716964
Corrupt parties ff12,0618263291925621

caption: Concrete parameters and savings under fully adaptive and semi-adaptive adversary models

:::

Pr⁡[eactual>m^/3]≤(274)m⋅(722729)3f+13=22.754888m−0.00464(3f+1)\Pr[e_{actual} > \hat{m}/3] \le\left(\frac{27}{4}\right)^m \cdot\left(\frac{722}{729}\right)^{\frac{3f+1}{3}} = 2^{2.754888m-0.00464(3f+1)}

To ensure that this probability is at most 2−1282^{-128}, it suffices to have f≥15,529f \ge15,529.

Derivation for d=4d = 4. Using the same derivation with d=4d = 4 we receive:

Pr⁡[eactual>m^/3]≤(274)m⋅(1690019683)3f+13=22.754888m−0.07331(3f+1)\Pr[e_{actual} > \hat{m}/3] \le\left(\frac{27}{4}\right)^m \cdot\left(\frac{16900}{19683}\right)^{\frac{3f+1}{3}} = 2^{2.754888m-0.07331(3f+1)}

To ensure that this probability is at most 2−1282^{-128}, it suffices to have f≥983f \ge983, which is a significant improvement from d=3d = 3.

Semi-adaptive adversary Under weaker adversary assumption, we can enable the use of d=2d = 2 achieving the desired probability guarantees for f=12,061f = 12,061 while reducing the required bound for d=3d = 3 to only 826.

Generalized strategy

We can generalize the strategy to arbitrary qShare sizes dd while guaranteeing unforgeability with probability 1−2−1281 - 2^{-128}. 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 mm symbols. Notice that d=21d = 21 is the largest optimal qShare size for m=32m = 32, as for any larger value of dd, we can use deterministic construction in which every symbol is signed by 2f+12f + 1 parties.

Hence, the overall strategy is as follows. The deterministic construction provides a modest 1.5×1.5\times improvement for n≤70n \le70, while for any larger number nn, we can apply QUASI to achieve a substantially greater improvement reaching over 10×10\times.

Discussion

The construction and analysis leave substantial room to improve the constants. In particular, the union bound used to select dd 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 2−1282^{-128}, allowing more favorable parameters. Likewise, corruption thresholds other than n/3n/3 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 dd symbols selected from a codeword c(M)c(M), 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 A={0,…,2ω−1}\mathcal{A} = \{0,\ldots,2^\omega- 1\} be the symbol alphabet, let M=Am^\mathcal{M} = \mathcal{A}^{\hat{m}} be the codeword input space. Let J=(j1,…,jd)J = (j_1,\ldots,j_d) be a fixed ordered tuple of distinct positions in [m^][\hat{m}]. For a statement c(M)∈Mc(M) \in\mathcal{M}, define its selected word as:

c(M)∣J:=c(M)j1⋯c(M)jd∈Ad.c(M)|_J := c(M)_{j_1}\cdots c(M)_{j_d} \in\mathcal{A}^d.

Let ΠWOTS=(SetupW,KeyGenW,SignW,VerifyW)\Pi_{\mathrm{WOTS}} = (\mathrm{Setup}_{\mathrm{W}},\mathrm{KeyGen}_{\mathrm{W}},\mathrm{Sign}_{\mathrm{W}},\mathrm{Verify}_{\mathrm{W}}) be a one-time signature scheme for words in Ad\mathcal{A}^d.

WOTS encoding. For a word a=a1⋯ada = a_1\cdots a_d, WOTS appends the fixed-length base-2ω2^\omega encoding of the checksum C(a)=∑i=1d(2ω−1−ai)C(a) = \sum_{i=1}^{d}(2^\omega- 1 - a_i). The checksum requires t=⌈log⁡2(d(2ω−1))ω⌉+1t = \left\lceil\frac{\log_2(d(2^\omega-1))}{\omega}\right\rceil+ 1 symbols. We can then write the resulting encoding as E(a)=(a1,…,ad,c1,…,ct)=(e1,…,ed+t)E(a) = (a_1,\ldots,a_d,c_1,\ldots,c_t) = (e_1,\ldots,e_{d+t}), where c1,…,ctc_1,\ldots,c_t are base-2ω2^\omega checksum digits. Following the basic WOTS construction, the scheme samples an independent secret starting value xix_i for each encoded symbol. To create the public endpoint, the scheme constructs hash chains of length 2ω2^\omega with public endpoints yi=f2ω−1(xi)y_i = f^{2^\omega-1}(x_i). The signature will be defined as σi=fei(xi)\sigma_i = f^{e_i}(x_i). To verify the signature, it is sufficient to check:

∀i∈[d+t]:f2ω−1−ei(σi)=yi.\forall i \in[d+t] : \quad f^{2^\omega-1-e_i}(\sigma_i) = y_i.

Here, frf^r denotes rr successive hash applications of the hash function ff. 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 ΠQOTS=(Setup,KeyGen,Sign,Verify)\Pi_{\mathrm{QOTS}} = (\mathrm{Setup},\mathrm{KeyGen},\mathrm{Sign},\mathrm{Verify}) is defined as follows. In the terminology of QUASI, its authentication output is a qShareqShare.

  • Setup(1λ,m^,2ω,d)→pp\mathrm{Setup}(1^\lambda,\hat{m},2^\omega,d) \to\mathrm{pp}. Run ppWOTS←SetupWOTS(1λ)\mathrm{pp}_{\mathrm{WOTS}} \leftarrow\mathrm{Setup}_{\mathrm{WOTS}}(1^\lambda) for words in Ad\mathcal{A}^d. Output pp=(ppWOTS,m^,2ω,d)\mathrm{pp} = (\mathrm{pp}_{\mathrm{WOTS}},\hat{m},2^\omega,d).

  • KeyGen(pp,J)→(vk,sk)\mathrm{KeyGen}(\mathrm{pp},J) \to(\mathrm{vk},\mathrm{sk}). Check that JJ contains dd distinct positions in [m^][\hat{m}]. Generate (vkWOTS,skWOTS)←KeyGenWOTS(ppWOTS)(\mathrm{vk}_{\mathrm{WOTS}},\mathrm{sk}_{\mathrm{WOTS}}) \leftarrow\mathrm{KeyGen}_{\mathrm{WOTS}}(\mathrm{pp}_{\mathrm{WOTS}}). Output vk=(J,vkWOTS)\mathrm{vk} = (J,\mathrm{vk}_{\mathrm{WOTS}}) and sk=(J,skWOTS)\mathrm{sk} = (J,\mathrm{sk}_{\mathrm{WOTS}}). The assignment JJ is bound to the verification key.

  • Sign(pp,sk,c(M))→σ\mathrm{Sign}(\mathrm{pp},\mathrm{sk},c(M)) \to\sigma. Check that c(M)∈Mc(M) \in\mathcal{M} and output

σ←SignWOTS(ppWOTS,skWOTS,c(M)∣J).\sigma\leftarrow\mathrm{Sign}_{\mathrm{WOTS}}(\mathrm{pp}_{\mathrm{WOTS}},\mathrm{sk}_{\mathrm{WOTS}},c(M)|_J).
  • Verify(pp,vk,c(M),σ)→{0,1}\mathrm{Verify}(\mathrm{pp},\mathrm{vk},c(M),\sigma) \to\{0,1\}. Reject malformed inputs. Otherwise, output

VerifyWOTS(ppWOTS,vkWOTS,c(M)∣J,σ).\mathrm{Verify}_{\mathrm{WOTS}}(\mathrm{pp}_{\mathrm{WOTS}},\mathrm{vk}_{\mathrm{WOTS}},c(M)|_J,\sigma).

Correctness. For every valid JJ, every c(M)∈Mc(M) \in\mathcal{M}, and every honestly generated key pair, an honestly generated qShare verifies with probability 1. Indeed, signing and verification apply WOTS to the same word c(M)∣Jc(M)|_J. For the basic hash-chain construction, each component satisfies

f2ω−1−ei(fei(xi))=f2ω−1(xi)=yi.f^{2^\omega-1-e_i}\left(f^{e_i}(x_i)\right)=f^{2^\omega-1}(x_i)=y_i.

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 c(M)c(M). It wins by producing (c(M∗),σ∗)(c(M^*), \sigma^*) such that it passes verification Verify⁡(pp,vk,c(M∗),σ∗)=1\operatorname{Verify}(\mathrm{pp},\mathrm{vk},c(M^*),\sigma^*)=1 and c(M∗)∣J≠c(M)∣Jc(M^*)|_J \ne c(M)|_J. QOTS is one-time unforgeable on selected symbols if every probabilistic polynomial-time adversary wins with probability negligible in λ\lambda.

Security argument. Any successful QOTS forgery immediately yields a WOTS forgery. A reduction embeds its WOTS verification key in vk=(J,vkW)\mathrm{vk}=(J,\mathrm{vk}_W), answers the sole QOTS signing query by requesting a WOTS signature on c(M)∣Jc(M)|_J, and outputs (c(M∗)∣J,σ∗)(c(M^*)|_J,\sigma^*). 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 c(M)∣Jc(M)|_J. It therefore also verifies for statements that agree with c(M)c(M) at every position in JJ; 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. [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. [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. [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. [4]Abraham, I., and Stern, G. Information theoretic HotStuff. arXiv:2009.12828, 2020.arxiv.org/abs/2009.12828
  5. [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. [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. [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. [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. [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. [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. [11]Ethereum Foundation Post-Quantum Team. Post-quantum Ethereum. Project website and roadmap. Accessed November 3, 2026.
  12. [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. [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. [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. [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. [16]Lamport, L. Constructing digital signatures from a one way function. Tech. Rep. CSL-98, SRI International, Computer Science Laboratory, Oct. 1979.
  17. [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. [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. [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. [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. [21]Succinct Labs. Introducing Telepathy: The first decentralized and secure zkSNARK interoperability protocol for Ethereum. Blog post. Accessed November 5, 2026.
  22. [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. [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

Paper details

vlnc:W_spgz44x8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents