Remark. This is an accessible companion piece to our deep-dive research post and lecture. For the full technical breakdown, check out the research post and watch the lecture.

With the recent publication of Google Quantum AI’s paper on quantum computing, discussions around the timeline for a Cryptographically Relevant Quantum Computer (CRQC) have intensified. While opinions on the timeline vary, the consensus in the cryptography community is clear: we need to start preparing and surveying quantum-secure algorithms now.

The first major task is to choose a post-quantum-secure digital signature scheme to replace the quantum-vulnerable elliptic curve cryptography we use today in Bitcoin. But upgrading from Schnorr and ECDSA isn't as simple as swapping out one algorithm for another. The community is currently tackling two massive questions: how we safely execute this transition, and which post-quantum (PQ) scheme we actually transition to. This post focuses entirely on the “which” part, breaking down one of the most promising PQ signature families.

Here is a look at the current post-quantum landscape, why Blockstream is heavily researching "lattice-based" cryptography, and how these signatures actually function.

The Post-Quantum Landscape

When it comes to post-quantum signatures, cryptographers generally look at four main sources of hard assumptions that quantum computers (presumably) cannot break.

1. Hash-based Cryptography. Security of such schemes rely on the assumption that hash functions are non-invertible. Such assumptions are considered to be the most stable among all cryptographic primitives we are using up to date.

Moreover, stateful schemes (such as SHRINCS) achieve remarkably compact signatures of size 324 bytes, but this compactness comes at the cost of careful state management. Conversely, avoiding this state management results in relatively large stateless signatures. Either way, both approaches suffer from algebraic inflexibility: i.e., building modifications such as effective multisignatures or threshold signatures seems currently unlikely.

Blockstream has already conducted an extensive research into this type of cryptography: see “Hash-based Signature Schemes for Bitcoin” by Mikhail Kudinov and Jonas Nick and SHRIMPS by Jonas Nick. Now we turn the consideration to lattice-based approaches that can resolve some of the aforementioned problems.

2. Lattice-based Cryptography. Security of such schemes are related to certain problems on the mathematical object called a lattice which has been used by mathematicians since the 18th century. You can visualize a lattice as an infinite grid of points, as shown in the figure below. Just as you can add two points on an elliptic curve to yield a third, you can add any two points on this grid to obtain another valid point on the lattice.

Then, one might ask different questions about this lattice: for instance, what is the minimal distance between two points on such a grid? Or, if you pick a point randomly on the plane, what is the closest point on the lattice to this point? Answering all these questions is assumed to be hard for a quantum computer for appropriate configuration of the lattice without knowing underlying details about the lattice geometry.

The main feature of lattices is an algebraic flexibility compared to hash-based schemes and smaller stateless signature sizes. We will come back to what we mean by that specifically in the next section.

3. Code-based Cryptography. Error-correcting codes (ECC) are another widely used mathematical tool in this space. For instance, you might already be familiar with them from their role in post-quantum proving systems like ZK-STARKs. However, current signature schemes based on ECC assumptions are impractical compared to hash-based and lattice-based counterparts in terms of resultant public key and signature sizes. Typically, these sizes easily exceed 10 KB, as is the case with the NIST candidate LESS.

4. Isogeny-based Cryptography. This type of cryptography yields the most compact public key and signature sizes among all prior candidates. For instance, SQISign achieves an impressive 213 bytes of cumulative public key and signature size (compared to, say, 96 bytes for Schnorr). However, the underlying math relies on quite advanced concepts of algebraic geometry. In cryptography, complexity is often the enemy of security since such heavy algebraic structure can mask subtle vulnerabilities. Before we plan about integrating such schemes into Bitcoin, these schemes will need significant time of battle-testing.

As can be seen, each of four aforementioned paradigms come with their own set of trade-offs regarding signature size, security robustness, and flexibility, which we depict in the Figure below.

To summarize, code-based signatures are currently too massive for Bitcoin's strict block space limits. Isogeny-based math is compact but extremely difficult to implement securely and still heavily debated. Hash-based signatures are incredibly secure and well-understood, but they are algebraically "rigid."

This leaves Lattice-based cryptography as arguably one of the most balanced and promising candidates for Bitcoin's long-term future.

Why Lattices? Algebraic Flexibility

To understand why lattices are so appealing for Bitcoin, we have to look at what makes current Bitcoin’s signatures (Schnorr and ECDSA) so effective.

Current Bitcoin security relies on the Discrete Logarithm (DL) problem. A massive benefit of the DL approach is that it possesses a nice mathematical structure. For instance, if you combine two secrets, their public counterparts combine predictably: [x+y]G=[x]G+[y]G. This algebraic homomorphic property is exactly what allows Bitcoin developers to build advanced protocols like multisignatures (see MuSig2 by Jonas Nick, Tim Ruffing, and Yannick Seurin), threshold signatures, HD key derivation or adaptor signatures.

Hash functions (such as SHA256 or BLAKE), on the other hand, act like random blenders. If you have a hash function H, adding inputs together destroys any relation to the outputs: say, H(x+y) does not equal H(x)+H(y). While this lack of structure is what makes hash functions secure, it also makes it incredibly difficult to build advanced protocols on top of them.

Lattices, however, give us back that mathematical structure. Instead of multiplying points on an elliptic curve, lattice cryptography involves multiplying grids of numbers (matrices) by lists of numbers (vectors). If you have a public matrix A and two secrets x and y, one has A(x+y)=Ax+Ay (which looks exactly like (x+y)G=xG+yG used in the DL setting).

There is one important catch: in lattices, we typically operate with short secrets. When you combine lattice equations (say, compute x+y), the size of the underlying “aggregated” secret increases. But as long as we manage the size of that error properly, the structural property remains valid. This means lattices potentially open the door for advanced modifications like post-quantum multisignatures, zero-knowledge proofs, and confidential assets.

How Lattice Signatures Work: Schnorr with Vectors

If you understand how Schnorr signatures work in Bitcoin today, you are 50% of the way to understanding some of lattice signatures such as Dilithium. The most prominent lattice signature designs use a technique that we informally call "Schnorr, but with vectors."

In a classical Schnorr signature, the signing process with a secret key x looks like this:

1. Generate a random number r.
2. Create a "commitment" to that number.
3. Hash the commitment and data to get a random challenge e.
4. Mask your secret key using that challenge to produce the final response: z=r+xe.

In a lattice-based signature, we do the exact same steps, just using matrices and vectors. The equation looks similar: for instance, many early studies in lattice-based signatures use equation z=r+Se, where S is a secret matrix, e is the challenge vector, and r is a randomness vector).

Rejection Sampling*

There is a large security problem here. To make lattice equations hard for quantum computers to solve, the numbers in the vectors z and r must be kept small (a problem known as the Short Integer Solution).

But when we calculate z=r+Se, it creates a statistical dependence between the signature z and the underlying secret S (which was not the case in Schnorr since r and e could be arbitrary). If an attacker looks at enough of your signatures, they will notice this statistical shift and potentially compromise the secret key.

As a simplified example, consider the figure below. Since r can be thought of as a small noise, z is distributed around the center Se with some noise (marked by a solid blue line). If one gets enough samples from this distribution, by averaging them one obtains the approximate center of this distribution, leaking a significant amount of information for an adversary.

To fix this, lattice-based cryptography employs a clever trick called Fiat-Shamir with aborts (also known as rejection sampling).

The idea is surprisingly simple: After the signer generates the signature z, they check to see if the addition of the secret key shifted the value too much. If the signature looks "biased" and risks leaking the key (as in the Figure above), they simply throw it away and try again with a new random number. This process is repeated several times until the resultant signature perfectly masks the secret key (shown by the dashed line in the Figure above).

Remark. In practice the center Se is itself the random distribution. However, this in principle does not change the point: the shift of the distribution leaks some information about the underlying secret S which we must eliminate (given that doing so turns out to be rather straightforward).

Next Steps

Lattice-based cryptography is a deep and promising direction of post-quantum cryptography, allowing far more than just replacing digital signatures. It provides the mathematical foundation we need to keep Bitcoin both quantum-secure and potentially upgradable to more effective aggregation and threshold schemes.

To dive into the deeper mechanics, including the math behind Discrete Gaussians, the Shortest Vector Problem, and rejection sampling, be sure to read the full research post, and watch the full presentation here: