Three months ago, Localhost Research, Benedikt Bünz, and Dan Boneh announced a partnership dedicated to advancing Bitcoin-focused post-quantum cryptographic primitives. In this blog post, we’re sharing an early version of a scheme we’ve been working on.

This particular contribution is authored by Dan, Benedikt, Justin, Yavor Litchev, and Kamilla Nazirkhanova.

While the paper is still a work in progress, we’re sharing the central concepts so the community can begin engaging with the ideas. The full paper, which includes all the details and security proofs, will be posted on the IACR ePrint server shortly.

---

Hash-based signature schemes (HBSS) offer conservative protections from a cryptographically relevant quantum computer (CRQC), as they rely only on the assumptions of their underlying hash function. Given that the Bitcoin protocol already assumes that SHA-256 has the necessary security properties, this makes HBSS an attractive area of research. However, the rigid structure of HBSS limits their ability to support certain classes of functionality out of the box.

One such area where HBSS have historically lacked flexibility is in advanced modes of thresholdization. Thresholdization is vital to our ecosystem; it underpins many cold-storage deployments, institutional custody protocols, corporate treasury management processes, escrow schemes, and countless other use cases.

While it is possible to trivially thresholdize a set of signatures by concatenating t non-threshold signatures from t of n signing parties, the signature length and verification time are linear in the threshold t. In the context of an already large single hash-based signature artifact, this presents a significant challenge to a resource-constrained blockchain environment. One can replace the t signatures with a succinct proof that proves knowledge of the t signatures, but this requires on-chain succinct-proof verification.

From our perspective, a sufficiently advanced thresholdized HBSS supports the following properties:

1. A standard signature artifact: A signature artifact that is byte-for-byte identical to an ordinary single-signer signature and requires no additional verification logic.¹

2. A hidden threshold and participant count: Neither the public key nor the signature reveals the number of participants n or the threshold t. This property follows when both artifacts have the same format and representation as their ordinary single-signer counterparts and contain no threshold-specific metadata.

3. A large participant count and threshold: A large number of parties n and a large threshold t.

4. Efficient key and participant rotation: An efficient protocol for rotating keys among participants and for adding and removing parties from the threshold without changing the public key.

5. Efficient distributed key generation: An efficient distributed key generation protocol (DKG).

Today, we are excited to announce PRAWNS,² an HBSS that is constructed via a threshold pseudorandom function (PRF). PRAWNS preserves the first four properties described above by producing a regular, non-threshold, Winternitz-style one-time signature.³ It is additionally compatible with HBSS such as XMSS, LMS, and FORS, and is thus adaptable to both stateful and stateless HBSS.

Background

To see how PRAWNS works, it helps to picture what a Winternitz one-time signature (WOTS) actually is: a rectangle of hash values. Each column is a hash chain. Start from a random secret value at the bottom—the chain start—and then apply a hash function over and over to climb to the top. There are a few dozen such chains side by side, and hashing all the chain tops together gives you the public key. See Chapter 14.3 of the Cryptography book for more detail.

To sign a message, the signer runs the message through an encoding function that picks one position in each chain—a “cut” through the rectangle—and reveals the value sitting at each of those positions. The verifier hashes each revealed value the rest of the way up its chain and checks that the tops match the public key. This is secure as long as no message’s cut sits entirely above another’s and, crucially, as long as the key signs only one message.

The two-quorums problem

In the threshold context, the “only one message” rule presents a problem.

Suppose one quorum of t parties signs a message and a completely different quorum of t parties signs a second message. In this example, there was no explicit misbehavior—each honest party signed exactly once. However, two signatures now exist under the same one-time public key. An attacker can mix and match revealed values from the two cuts to forge a signature on a message of their choosing.

To prevent this, we must guarantee that no two quorums can be disjoint. With up to f corrupt parties, security requires t > (n + f) / 2 so that any two quorums share at least one honest party who refuses to sign twice. We believe this bound is inherent for any threshold one-time signature.

Share-pooling attack

The core building block of PRAWNS is a threshold PRF: a keyed function whose outputs look random to anyone without the key. Here, the master secret is only ever the PRF key itself, held in shares. Every chain-start secret is defined as the PRF’s output at that chain’s position, and the rest of the rectangle is published encrypted, with each cell one-time-padded by the PRF’s output at its coordinates.

When naively applied to a thresholdized HBSS, threshold PRFs are insufficiently protective. In the two-quorums problem described above, the bounded-threshold constraint only prevents two complete signatures on different messages from existing. Another attack exists when utilizing threshold PRFs: during signing, parties emit shares; these shares can be collected by a malicious signing party even if a quorum is not reached. If an attacker can pool a sufficient number of leftover shares from different messages, they can forge a signature.

To eliminate this risk, we introduce the concept of a context-aware threshold PRF. A context-aware threshold PRF cryptographically binds each party’s evaluation share to a chosen context,⁴ and shares produced under different contexts cannot be combined. Under this regime, an attacker pooling leftover shares is unable to leverage them to their advantage.

PRAWNS thus requires a context-aware threshold PRF. We provide two constructions.

Lattice- and hash-based threshold PRFs

For settings with a large number of participants n and a large signing threshold t, we present a lattice-based construction using the key-homomorphic PRF of Boneh, Lewi, Montgomery, and Raghunathan.⁵ Context awareness is layered into this construction by giving each participant a Shamir secret share of zero, which they hash with the message to create a mask for their contribution.

When a quorum signs the same message, the masks cancel as the contributions are combined. If contributions for different messages are mixed, the masks do not cancel, and the result is useless. We stress that the final signature is a standard, non-threshold, hash-based signature. The blockchain is unaware of lattices or thresholdization.

For smaller committees, a purely hash-based construction is available. For a (2)-of-(3) threshold, generate three PRF keys and define the master output as the XOR of all three PRF outputs. Give each participant two keys, arranged so that any two participants collectively hold all three, while a single participant is always missing one.⁶

To add context awareness, the participants use shared keys to generate message-dependent masks that cancel when a quorum signs the same message but remain when contributions from different messages are combined.

PRAWNS

With the described primitives available, the full PRAWNS scheme assembles as described above: key generation derives every chain start from the threshold PRF, hashes the starts forward to form the WOTS rectangle, and publishes the rectangle with each cell masked by a PRF output. This masked rectangle is the combiner’s public key.

For message signing, each party identifies the corresponding cut through the rectangle and provides context-dependent PRF shares for those positions. From shares produced by any t parties for the same message, the combiner reconstructs the PRF outputs, unmasks the selected cells, and returns them as a standard Winternitz signature.

Conclusion

When thinking about the Post-Quantum Problem (PQP), it’s important to remember that we are on a long journey. Each new addition to the field brings us one step closer to a corpus of materials that may one day support our community in its response to a quantum-capable attacker.

PRAWNS, while powerful, is just one step in that journey. We acknowledge that PRAWNS does not address the DKG problem. However, we do intend to make PRAWNS more efficient, research the DKG problem, and investigate many other pressing topics in this problem space.

Of the various components that support the PRAWNS architecture, we hope the community takes away its dualistic nature: the signature exposed to the world relies only on hashes, while a Learning With Rounding assumption scales the quorum on the client side. This kind of design moves us toward a post-quantum future defined not by scarcity and compromise, but by a diverse set of primitives we can compose into powerful protocols.

Thank you for reading this preview blog post. Stay tuned for the full paper.