# Schnorr, But with Vectors – Lattice-based Signatures Explained

Source URL: https://blog.blockstream.com/schnorr-but-with-vectors-lattice-based-signatures-explained
Updated: 2026-11-19T20:10:23.000Z
Author: Blockstream Team
Published: May 18, 2026
Category: Blockstream Research

---

_**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_](https://hackmd.io/@ZamDimon/rk3uMfpjbx) _and watch the_ [_lecture_](https://www.youtube.com/watch?v=AMepMAqwY-M)_._

With the recent publication of [_Google Quantum AI’s paper_](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) 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](https://blog.blockstream.com/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups)) 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_](https://eprint.iacr.org/2025/2203.pdf)” by Mikhail Kudinov and Jonas Nick and [_SHRIMPS_](https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355) 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.

![An illustration of a lattice (the set of blue points).](https://storage.googleapis.com/dxp-staging-assets/blog/body/schnorr-but-with-vectors-lattice-based-signatures-explained/data-src-image-b29a007c-62a7-46f1-8665-65041df79fd5.png)

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](https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-2/spec-files/less-spec-round2-web.pdf).

**4\. Isogeny-based Cryptography.** This type of cryptography yields the most compact public key and signature sizes among all prior candidates. For instance, [SQISign](https://sqisign.org/) 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.

![High-level comparison between various PQ candidates.](https://storage.googleapis.com/dxp-staging-assets/blog/body/schnorr-but-with-vectors-lattice-based-signatures-explained/data-src-image-0dea39be-b934-47fd-b9b4-0fc2c274cc71.png)

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](https://eprint.iacr.org/2020/1261) 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_](https://eprint.iacr.org/2017/633.pdf). 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.

![High-level explanation of a rejection sampling procedure. The “naive” protocol produces the signature shown by the solid line, whose geometry leaks information about the distribution’s shift. Rejection sampling ensures that this offset is absent from the resultant output distribution.](https://storage.googleapis.com/dxp-staging-assets/blog/body/schnorr-but-with-vectors-lattice-based-signatures-explained/data-src-image-9bc12f69-2561-45af-ba3f-863f621dabf6.png)

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](https://hackmd.io/@ZamDimon/rk3uMfpjbx), and watch the full presentation here:

## Blog Categories

- [All Posts](https://blog.blockstream.com/)
- [Blockstream Finance](https://blog.blockstream.com/blockstream-finance)
- [Company](https://blog.blockstream.com/company)
- [Lightning Network](https://blog.blockstream.com/lightning-network)
- [Blockstream Mining](https://blog.blockstream.com/blockstream-mining)
- [Blockstream Explorer](https://blog.blockstream.com/blockstream-explorer)
- [Blockstream Satellite](https://blog.blockstream.com/blockstream-satellite)
- [Liquid Network](https://blog.blockstream.com/liquid-network)
- [Blockstream Jade](https://blog.blockstream.com/blockstream-jade)
- [Blockstream AMP](https://blog.blockstream.com/blockstream-amp)
- [Blockstream App](https://blog.blockstream.com/blockstream-app)
- [Blockstream Research](https://blog.blockstream.com/blockstream-research)
- [Cryptocurrency Data Feed](https://blog.blockstream.com/cryptocurrency-data-feed)
- [Elements](https://blog.blockstream.com/elements)
- [Layer-2 Roundup](https://blog.blockstream.com/layer-2-roundup)
- [Quarterly Report](https://blog.blockstream.com/quarterly-report)
- [Layer-2 Report](https://blog.blockstream.com/layer-2-report)
- [Simplicity Language](https://blog.blockstream.com/simplicity-language)
- [Quarterly Update](https://blog.blockstream.com/quarterly-update)
- [Quantum](https://blog.blockstream.com/quantum)
- [Enterprise](https://blog.blockstream.com/enterprise)
- [Insights](https://blog.blockstream.com/insights)
- [Simplicity](https://blog.blockstream.com/simplicity)
- [Developer](https://blog.blockstream.com/developer)
- [Security](https://blog.blockstream.com/security)
- [Jade](https://blog.blockstream.com/jade)
- [Liquid](https://blog.blockstream.com/liquid)
- [Lightning](https://blog.blockstream.com/lightning)
- [Research](https://blog.blockstream.com/research)
- [Core Lightning](https://blog.blockstream.com/core-lightning)
