How Bitcoin Can Resist Quantum Computers: A Comparison of Three Major Lattice-Based Signature Schemes

Original author: Blockstream Team

Original translation: Saoirse, Foresight News

Blockstream Research has published a comprehensive research report on lattice-based signatures for Bitcoin. This article summarizes the research content, key findings, and related recommendations. The full report is available here.

Digital signatures are the core mechanism for authorizing transactions in Bitcoin, and the Schnorr and ECDSA signatures that currently fulfill this role have extremely low costs. In 1994, Shor proved that a sufficiently powerful quantum computer could break both types of signatures. While there is still widespread debate over when such machines will be built, we need a viable post-quantum signature deployment plan in place before the problem actually arrives.

Lattice-based signature schemes are a leading candidate to replace existing signatures. Lattice cryptography has over a century of research history, and its cryptographic applications have been developed for nearly three decades. In the post-quantum cryptography landscape, lattice-based signatures offer several advantages: the combined size of public key and signature can be as low as under 1.6 kilobytes, and their algebraic structure holds future promise for supporting multisignatures, threshold signatures, and succinct proofs.

This report examines three schemes: Dilithium, Falcon, and Hawk. For readers unfamiliar with lattice cryptography, we explain the design rationale of each scheme, provide a complete walkthrough of the algorithms, and analyze them across dimensions such as security, performance, and practical deployment (e.g., wallet key derivation). Among the three, which schemes can actually be deployed on the Bitcoin blockchain?

Evaluation Criteria

Bitcoin has its own constraints when selecting signature schemes, and this evaluation is centered on four core criteria:

• On-chain cost: One of the most important metrics is the combined size of the public key and signature. When an output is spent, both the public key and signature are recorded on-chain, and full nodes must download and store every byte. Verification overhead is equally critical: every signature must be verified by nodes across the entire network, and slow verification places a burden on the whole network.
• Implementation complexity: Whether a scheme can be implemented securely is paramount. If the design requires floating-point arithmetic or delicate Gaussian sampling, implementation errors or side-channel attacks such as timing analysis could leak keys. Implementation complexity is a factor that cannot be ignored for a smooth migration.
• Deployment risk: Real-world obstacles arise during actual Bitcoin integration: hash function selection at the consensus layer (most candidates use SHAKE, while Bitcoin uses SHA‑256), cross-platform reproducibility of signature outputs, and whether the signing program fits within the memory constraints of hardware wallets.
• Future potential: The vast majority of Bitcoin wallets use BIP‑32 hierarchical deterministic mechanisms: from a single master public key, an unlimited number of child public keys can be derived without touching the private key. None of the currently standardized post-quantum signature schemes natively support this feature, so we investigate the cost of adding this capability and also examine various non-standard scheme variants that may offer greater benefits.

What Security Level Should Be Chosen?

Before comparing sizes, the target security level must first be determined — a choice that is not as straightforward as it appears. NIST divides security levels into categories 1 through 5; higher levels offer stronger security, but correspondingly larger keys and signatures.

We believe Bitcoin should adopt at least a Category 3 security standard. Bitcoin outputs may remain unspent for decades, and if advances in cryptanalysis reduce the actual security level of a scheme, assets would be locked behind weakened keys and exposed to risk over the long term. Lattice assumptions have already withstood nearly three decades of public cryptanalysis — a longer track record than the research foundation behind elliptic curves at the time Bitcoin adopted them. However, the complex algebraic structure of lattices still leaves many potential avenues for future attacks, and we should not stake the entire security bet of the distant future on them.

Major mainstream products have made the same judgment. Apple's iMessage PQ3 protocol discards Category 1 lattice parameters entirely, using Category 3 and Category 5 parameters throughout; Cloudflare uses ML‑KEM‑768 (Category 3) in its post-quantum TLS deployment, stating that while Category 1 appears secure today, security margin must be reserved for decades of future cryptanalysis. Bitcoin's security time horizon is even longer than both of these.

Increasing the security level comes at a cost. For example, moving Dilithium from Category 2 to Category 3 increases the total size by approximately 1.5 kilobytes. The report compares parameter sets across all security levels, allowing readers to weigh the trade-offs themselves. The fate of Hawk demonstrates that conservative security considerations are far from theoretical.

Detailed Analysis of Candidate Schemes

Dilithium: The Simplicity-First Scheme

Dilithium, standardized by NIST as ML‑DSA in FIPS 204, transplants the commitment-challenge-response paradigm of Schnorr signatures onto module lattice arithmetic.

Its defining feature is simplicity. All of Dilithium's operations are integer arithmetic: ring operations, matrix-vector multiplication, hashing, and rounding — no floating-point operations, and no discrete Gaussian sampling required. This makes it easier to write secure, constant-time implementations. It is also the most widely deployed candidate, already integrated into OpenSSL, BoringSSL, AWS‑LC, and Apple CryptoKit.

The cost is size. At Category 3 security, ML‑DSA‑65 has a 1952-byte public key and a 3309-byte signature, totaling 5261 bytes — approximately 55 times the size of Bitcoin's native public key plus signature, making it the largest of the three schemes at the same security level.

Dilithium's most valuable aspect for Bitcoin: it is the only one of the three that comes close to enabling BIP‑32-style key derivation. The re-randomizable key construction DilithiumRK can generate child keys from parent keys using only public information. The report analyzes three variants, including our proposed DilithiumRKS, where derivation logic is entirely contained within wallet software and the chain only needs standard verifiers to process ordinary ML‑DSA signatures. However, none of the three are yet production-ready: two variants require verifier modifications, and DilithiumRKS itself lacks a complete unforgeability proof; all schemes rely on a network-wide shared matrix, which, while formally secure under the Module‑LWE assumption, binds the security of all keys to a single instance. We believe that Dilithium-based public key derivation is currently only a proof of concept and cannot be deployed in practice.

Falcon: The Compact Scheme

Falcon, selected by NIST and standardized as FN‑DSA, is the most compact of the three. At Category 1 security, Falcon‑512's public key plus signature totals 1563 bytes; at Category 5 security, Falcon‑1024 totals 3073 bytes. Falcon‑1024, with a higher security margin, is even smaller than Category 3 Dilithium.

Falcon takes a different approach from Dilithium: a hash-and-sign scheme based on NTRU lattices. The signer's private key is a short basis of a lattice; the message is hashed and mapped to a point in space, and the signer uses the short basis to find a lattice vector close to that point. The point and the nearby vector together form the signature; verification only checks that the vector belongs to the lattice and is sufficiently close. The implementation challenge lies in finding the vector without leaking information about the basis. Early schemes like GGH and NTRUSign simply rounded to the nearest lattice point, leaking geometric information with every signature. Falcon employs the GPV framework, sampling nearby vectors from a Gaussian distribution, which provably makes the sampled output independent of the basis, eliminating the leak risk — but dramatically increasing the difficulty of implementing the sampler.

The sampler is Falcon's engineering weak point. It operates in the complex Fourier domain and requires floating-point computation. Different processors, compilers, and compilation optimization options all produce inconsistent floating-point outputs. This is not just a compatibility issue — it is a security concern: the GPV security proof requires that for the same digest, the signer never outputs two different short vectors; once signatures become deterministic, platform-induced floating-point rounding differences break this condition. Workable solutions exist: deterministic Falcon can replace hardware floating-point with integer emulation, producing identical signatures across all platforms. The cost is approximately a 15× slowdown in signing speed and a 2× slowdown in key generation.

Importantly, verification is unaffected: Falcon verification uses all-integer operations with deterministic results, and it is also the fastest verifier among the candidates. This asymmetry is very Bitcoin-friendly: signatures are generated once by the wallet when spending a transaction, while every signature is verified by all full nodes across the network. A 15× slowdown in signing is a low-frequency cost, and trading it for cross-platform reproducibility and integer arithmetic is, in our view, a reasonable trade-off. The floating-point issue is therefore an engineering obstacle that can be solved, not a fatal flaw.

Two caveats: Due to structural constraints, Falcon has no Category 3 parameters — only Category 1 or Category 5 are available. Based on security margin considerations, we recommend Falcon‑1024. Second, signing consumes significant memory: the sampler for the 1024 parameter set relies on a precomputed tree occupying approximately 90 kilobytes of memory. Hardware wallets can dynamically rebuild the tree branch by branch, compressing memory usage to 16 kilobytes, but at the cost of doubling signing time. Slower signing on hardware devices is a practical cost, but it remains acceptable.

Hawk: The Failed Scheme

Hawk aimed to combine the strengths of the other two schemes: Hawk‑512 signatures are only 555 bytes — even smaller than Falcon; the signing side is all-integer arithmetic with a minimum memory footprint of just 6 kilobytes. It was also the only lattice-based candidate remaining in the third round of NIST's additional signature competition, and the report devotes substantial space to presenting it.

The cost lies in its security assumptions. Rather than relying on the NTRU and SIS problems that have weathered decades of cryptanalysis, it depends on the lattice isomorphism problem and the one-more-SVP assumption — both of which have relatively shorter research histories.

Just before the report was finalized, Anthropic's Straznickas and Weis discovered a structural flaw in Hawk's lattice construction: the SVP problem dimension that actually needs to be solved for key recovery is only half of what the designers envisioned. The key recovery security bits for the candidate parameter sets were significantly weakened. The researchers completed a full end-to-end key recovery attack against the challenge parameters HAWK‑256; even under attack, the officially proposed HAWK‑512 and HAWK‑1024 remain practically unbreakable. The Hawk team confirmed the validity of the attack and withdrew the scheme from the NIST process; the team stated that if the vulnerability were fixed by doubling the parameters, Hawk's signature size advantage — its proudest feature — would completely disappear.

The report retains the Hawk chapters because the attack targets the algebraic properties of a specific number field, not the entire design paradigm. Whether a redesign can circumvent the vulnerability remains an open question. The Hawk incident also vividly confirms our rationale for maintaining conservative security margins: a scheme can have excellent size, impressive speed, and have progressed through multiple rounds of the standardization process — and a single paper can dramatically reduce its estimated security level.

Comparison Table of Schemes

All schemes in the table above (including SPHINCS+) are stateless signatures: the signer does not need to record past signatures. Stateful hash-based signatures like XMSS can achieve smaller signature sizes, but require maintaining signing state; see the dedicated report on hash-based signatures for a comparison.

Remaining Obstacles to Deployment

Falcon lacks a usable key derivation scheme. The only publicly available BIP‑32-style Falcon derivation scheme re-randomizes the private key basis, dramatically inflating the signature norm bound and expanding the on-chain signature to approximately 23.7 kilobytes. Moreover, the scheme's parameters do not meet its own security conditions, and fixing this issue would cause the size to balloon further. The absence of a viable Falcon public key derivation implementation is also the most valuable open problem identified in the report.

The Falcon standard is not yet finalized. Although NIST has selected Falcon, the FN‑DSA draft has not yet been officially released. Standardization will bring audited implementations, test vectors, and hardware-level support. Widespread adoption would reduce the risk and difficulty of integrating into Bitcoin's consensus layer. We recommend waiting for the official FN‑DSA release; until then, Falcon remains in flux.

Falcon‑WS variant: This variant relaxes internal parameters and compensates through rejection sampling, compressing the total size to 1114 bytes at Category 1 and 2387 bytes at Category 5 — a further reduction compared to the original Falcon. This direction has research value, but it will not be included in the official standard and requires more cryptanalytic validation. Existing research has found a flaw in the strong unforgeability proof of its derived variants (ordinary unforgeability is unaffected).

Will better schemes emerge in the future? Beyond the aforementioned schemes, the Fiat-Shamir family traces its origins back to BLISS in 2013, and the latest result from Gärtner presented at CRYPTO 2025 achieves paper-level sizes comparable to Falcon based on well-established assumptions. The fundamental obstacle to engineering deployment for this family lies in implementation security: BLISS was broken via side-channel attacks due to non-constant-time Gaussian sampling; subsequent schemes have not fully resolved this issue, and the latest result also indicates that protecting the sampling step is even more difficult. Until this problem is solved, such schemes hold only theoretical appeal and are unsuitable for deployment.

Lattice-based and hash-based signatures are complementary. Lattice-based signatures can serve as components in hybrid schemes. For example, in SHRINCS, the stateless recovery path currently uses SPHINCS+ signatures of several kilobytes; replacing them with Falcon (or Falcon‑WS) signatures offers smaller size and faster verification, dramatically reducing the overhead of the low-frequency recovery path without affecting the everyday usage path.

Research Conclusions

The ranking of lattice-based candidates is clear: Hawk withdrew from the competition after the attack by the Anthropic team; Dilithium has the lowest implementation difficulty and is the only scheme with an existing research foundation for key derivation, but its size is unfavorable for Bitcoin's on-chain overhead; Falcon combines compact size, fast verification, and mature security assumptions — and its primary shortcoming, floating-point operations on the signing side, already has a viable engineering solution. If we had to choose a lattice-based signature scheme for Bitcoin today, we would select Falcon‑1024.

For the present, our view aligns with the hash-based signature report: the conservative short-term path remains hash-based signatures, which have the most mature security assumptions and the lowest risk, making them suitable as a transitional solution. Once FN‑DSA is formally finalized — with a stable specification, audited codebase, and hardware wallet support — Falcon will offer significant improvements over pure hash-based signatures; a hybrid deployment is also possible, allowing the two signature families to complement each other.