University of California, Santa Barbara researchers have developed QUASI, a new protocol enabling groups to publicly verify pre-validated statements using a method distinct from current approaches. Designed for quorum-based systems, QUASI relies purely on hashing and error correction, offering a smaller per-party contribution than full hash-based signatures. Currently, aggregating 100 such signatures requires either a 100-fold increase in size and verification work or a hash-based SNARK, as planned by Ethereum; QUASI offers an alternative. The work builds on one-time hash-based authentication primitives like XMSS and SLH-DSA, relevant to ongoing post-quantum migration efforts.

QUASI Protocol: Post-Quantum Quorum Attestation for Valid Statements

The QUASI protocol, developed by researchers at University of California, Santa Barbara, establishes a method for groups to attest to the validity of pre-verified statements using minimal individual contributions. Unlike traditional signature schemes requiring substantial data per signer, QUASI focuses on generating a collective attestation from shares that do not individually function as valid signatures. The protocol’s design centers around a quorum of n = 3f + 1 parties, where up to f parties can be compromised without undermining the system’s security.

A quorum of at least 2f + 1 parties generates a joint quorum attestation, or qAttest, which explicitly identifies the contributing members, foregoing anonymity in favor of accountability. This qAttest is not designed to resemble a single signature; instead, it functions as a collection of individual or qShares, each of which is insufficient on its own to validate the statement.

The system’s security is guaranteed at a 1-2^(-128) level, a common benchmark for cryptographic robustness. QUASI’s operation begins with a setup phase generating public parameters, including a description of the statement space, an error-correcting code, and the definition of qShare and qAttest spaces. Each party then independently generates a verification key and a signing key. When attesting to a statement, each participating party produces a qShare based on their signing key and the statement itself.

The qShares from a sufficient quorum are then combined using a qCombine function, which outputs either a valid qAttest or a failure symbol. “Reject if, |S| < 2f + 1, or any supplied qShare is malformed,” the protocol specifies, emphasizing the importance of quorum size and data integrity. The resulting qAttest contains the set of signing parties and their corresponding qShares.

The protocol explicitly allows the qAttest to encode the signing set, meaning the identities of the contributors are revealed as part of the attestation process. This differs from traditional threshold-unforgeability, which often focuses on preventing forgery for statements not previously queried to honest parties.

The researchers note a distinction, stating, “It is worthy of noting how Weak-f-Unforgeability differs from traditional threshold-unforgeability: in the latter, we would allow the adversary to query honest parties on a set Q of statements, rather than a unique statement M; we would then require negligible forging success probability for all statements $M^{*}$ ∉Q, instead of $M^{*}$ ≠ M, not queried to any honest party.” The error-correcting code plays a large part in ensuring the reliability of the qAttest. 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. Although these protocols provide 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 combines the QUASI advantage with SNARK-based compression.

Lamport-OTS and WOTS Foundations for QUASI’s Hash-Based Authentication

The QUASI protocol uses established one-time hash-based authentication schemes, specifically Lamport-OTS and WOTS, to construct a system prioritizing compact, verifiable attestation over anonymity. These underlying primitives also form the basis of hash-based signature management schemes like XMSS and SLH-DSA, already considered for post-quantum migration strategies, demonstrating a clear lineage for the new protocol. Unlike schemes relying on BLS-style native aggregation, QUASI employs a different approach to reducing signature size and verification costs, a critical consideration given the challenges of scaling hash-based signatures.

The design deliberately avoids SNARK-based aggregation, a technique planned for implementation within Ethereum, and instead focuses on reducing the number of hash-chain values and preimages each party maintains. This reduction in computational load directly translates to savings in per-party contribution size, generation effort and verification effort, potentially exceeding 10x compared to naive collections of hash-based signatures.

The protocol achieves this efficiency by treating individual input symbols independently, a characteristic enabling the creation of quasi-signature shares, or qShares, which collectively form a publicly verifiable joint quorum attestation, or qAttest. The number of symbols each qShare needs to authenticate diminishes as the number of participating parties increases, reaching as few as two symbols per party. The system’s reliance on error-correcting codes further enhances its robustness and efficiency.

QUASI represents input as symbols over GF(2^8) and employs a code with 3x expansion, a technique that allows for the reconstruction of the original message even if some shares are lost or corrupted. Per-symbol authentication costs are inherited directly from the underlying method, such as WOTS, without modification; the savings stem from reducing the number of input symbols authenticated.

These reductions also benefit SNARK-based aggregation methods, as they directly reduce the input size and verification work within the proof itself. “We employ an underlying hash-based signature scheme for d-symbol authentication,” the researchers state, emphasizing the direct inheritance of security properties from well-studied primitives. The protocol’s construction relies on a standard signing interface for the underlying hash-based scheme, outputting public parameters specifying security levels, word spaces, and key spaces.

Verification involves confirming that each qShare authenticates the correct symbols at positions defined by the party’s published mapping, a process illustrated in a diagram within the paper. The researchers highlight that the system can detect errors, noting that an invalid qAttest will not have a codeword with a distance of one from the original message. QUASI’s security rests on a concept termed Weak-f-Unforgeability, which differs from traditional threshold-unforgeability.

qShare and qAttest: Core Components of Joint Attestation

A core principle of the QUASI protocol is the division of authentication responsibility, distributing the task of verifying a statement across multiple parties through components called qShares and qAttests. Each qShare represents a party’s contribution, and a sufficient collection of these shares, a quorum, forms a joint attestation, validating the original statement without requiring a single, monolithic signature. The protocol’s construction hinges on the creation of public parameters, generated before the attestation process begins, which define the statement space and incorporate an error-correcting code.

This code, denoted c(·), expands the input statement and is critical for resilience against malicious activity. The public parameters also establish the qShare space, $Σ_{s h}$ and the qAttest space, Σ, defining the structure and size of these components. The system first rejects any input where the number of participating parties falls below this threshold or if any supplied qShare is malformed.

The candidate qAttest is then formed as a simple collection of these valid qShares. This mapping dictates which symbols of the expanded statement, c(M), each party is responsible for verifying. The system then performs a decoding check to ensure that the combined qShares allow for the recovery of the original statement with minimal error. The illustration provided in the paper depicts how QUASI distributes symbol authentication across parties to attest to a pre-validated statement, showing a codeword c(M) and the mapping of each party to specific symbols.

The design of QUASI diverges from traditional signature aggregation methods by not requiring secrecy guarantees, meaning a qAttest may reveal the identities of its contributors. This is a deliberate choice, creating a hybrid approach that blends elements from different signature aggregation paradigms while not fully adhering to any single one.

Error Correction Codes Enable Reduced Per-Party Contributions

By representing a 256-bit statement digest as 32 symbols over GF(2^8) and employing an error-correcting code with a 3x expansion, QUASI significantly lowers computational demands. The core of this reduction lies in the distribution of authentication responsibilities. This probabilistic approach deliberately creates a trade-off between the size of each party’s contribution and the code’s resilience, fixing resilience at one-third and adjusting the number of authenticated symbols accordingly.

The researchers demonstrate that adversarial errors remain within the code’s correction capacity with a probability of 1-2^(-128) for appropriate choices of symbol allocation. The protocol’s construction begins with a check to ensure the system meets a minimum size requirement, specifically that the number of parties, n, must equal 3*f* + 1, where f represents the corruption threshold.

QUASI Application: External Attestation for IT Consensus Protocols

QUASI protocols establish a distinct approach to attestation by setting the number of authenticated symbols, d, per quasi-share to guarantee undetected symbol flipping occurs with a probability less than 2^-128, a level of security important for high-integrity systems. The researchers detail concrete parameter selections and resulting efficiency gains, demonstrating the practical implications of this design choice for resource-constrained environments.

This distinction is significant because it positions QUASI as a potentially more scalable solution for security, particularly in scenarios where minimizing computational overhead is paramount. The protocol achieves this through a reliance on hashing and error correction, creating a streamlined process for verifying pre-validated statements without the complexities of SNARK-based systems.

The work introduces a newly conceived class of attestation protocols, and provides a glossary of notations and terms used throughout the construction, including definitions for statement, encoded statement, symbol space and qShare map. This detailed glossary highlights the rigorous approach taken in defining the protocol and its components, ensuring clarity and precision in its implementation. The researchers emphasize that QUASI is not a signature aggregation scheme, but rather a protocol specifically designed for quorum-based systems to attest to pre-validated statements, a distinction that highlights its unique functionality and target applications.

👉 More information
🗞 QUASI: Post-Quantum Quorum Attestation of Pre-Validated Statements
✍️ Maksym Ioffe and Dahlia Malkhi (University of California, Santa Barbara)
🧠 ArXiv: http://arxiv.org/abs/2611.10403v1

More like this