Author: Blocksteam Team
Source: https://blog.blockstream.com/schnorr-but-with-vectors-lattice-based-signatures-explained/
Note : This article is an introduction to our in-depth research and courses. For a comprehensive technical explanation, please read our research reports and watch our courses .
With the publication of Google's paper on quantum AI , which discusses quantum computing, discussions surrounding the timeline for the advent of a cryptographically significant quantum computer (CRQC) have intensified. While predictions for its release vary, the consensus within the cryptography community is clear: we should begin preparing and investigating quantum-safe cryptographic algorithms now.
The primary task is to select a quantum-safe electronic signature scheme to replace the quantum-fragile elliptic curve cryptography we use today in Bitcoin. However, surpassing Schnorr and ECDSA is not as simple as switching to another algorithm. The Bitcoin community is currently focused on two main issues: how to securely perform the migration; and which post-quantum (PQ) scheme to migrate to. This article focuses only on the latter issue, hoping to identify the most promising family of post-quantum signatures.
The following are our observations on the current post-quantum field. These observations also answer why Blockstream focuses on "lattice-based" cryptography and how these signature schemes work.
Post-quantum era
Regarding post-quantum signatures, cryptographers typically focus on four (supposedly) difficult assumptions that are hard to break with quantum computers.
1. Hash function-based cryptography . The security of this type of scheme relies on the assumption that the hash function cannot be reversed. Of all the cryptographic primitives we use today, these assumptions are considered the most stable.
Furthermore, stateful schemes (such as SHRINCS ) achieve very compact signatures, only 324 bytes; however, this compactness comes at the cost of meticulous state management. Conversely, avoiding this burden of state management results in stateless signatures with relatively large final signature references. Both suffer from algebraic inflexibility: that is, developing variants such as efficient multi-signatures and threshold signatures currently appears impossible.
Blockstream has produced a comprehensive study of this type of cryptography, as seen in " A Study of Hash Function-Based Signature Schemes for Bitcoin " (by Mikhail Kudinov and Jonas Nick) and " SHRIMPS " (by Jonas Nick). Now, we turn to consider lattice-based methods, which can address some of the problems mentioned earlier.
2. Lattice-based cryptography . The security of such schemes relates to a specific problem involving a mathematical object called a " lattice ." This object has been studied by mathematicians since the 18th century. You can imagine a lattice as a matrix of countless points, as shown in the image below. Just as adding two points on an elliptic curve produces a third point (on the same elliptic curve), adding two points on this lattice yields another valid point on the same lattice.
So, you can ask some questions about this lattice, such as: What is the shortest distance between two points on this lattice? Or, if you randomly pick a point on the plane, what is the nearest lattice point to that point? For a properly configured lattice, quantum computers—without knowing the underlying geometric details of the lattice—are considered to have difficulty answering all these questions.
Compared to hash function-based schemes and smaller stateless signatures, the main characteristic of lattices is their algebraic flexibility. We will explain this in more detail in the next chapter.
3. Encoding-Based Cryptography . Error-correcting codes (ECC) are another widely used mathematical tool in this field. You may have heard of them, for example, because they have their own applications in post-quantum proof systems such as ZK-STARKs. However, current signature schemes based on the ECC assumption are impractical (compared to hash function-based and lattice-based competitors) because the resulting public key and signature are too large. Generally, these objects easily exceed 10 KB in size; the NIST candidate scheme LESS is a case in point.
4. Homologous Cryptography . This type of cryptography can produce public keys and signatures that are smaller than the aforementioned candidate schemes. For example, SQISign 's public key and signature total size of 213 bytes (for comparison, the Schnorr signature scheme is 96 bytes), which is impressive. However, the mathematics behind it relies on very new concepts of algebraic geometry. In cryptography, complexity is often the enemy of security because these cumbersome set structures can mask tiny vulnerabilities. These schemes will require significant stress testing before we can integrate them into Bitcoin.
As you can see, each of the four paradigms mentioned above has its own trade-offs: signature size, security and robustness, and flexibility, which can be summarized in the following diagram.
In summary, current code-based signatures are too cumbersome for Bitcoin's strict block space constraints. Mathematics based on common origins is compact but extremely difficult to implement securely and remains highly controversial. Hash function-based signatures are very secure and well-understood, but they are algebraically "rigid."
Looking at the long-term future of Bitcoin, lattice-based cryptography has emerged as one of the most balanced and promising candidates.
Why use lattice signatures? Algebraic flexibility.
To understand why lattice cryptography is attractive to Bitcoin, we need to look at the factors that make current Bitcoin signature schemes (Schnorr and ECDSA) so efficient.
Currently, the security of signature schemes on Bitcoin relies on the Discrete Logarithm (DL) problem. A significant advantage of the DL method is its well-structured mathematical framework. For example, combining two private keys also allows for predictable combinations of their public keys:
[x + y].G = [x].G + [y].GThis geometric homomorphic property is precisely why Bitcoin developers were able to develop advanced protocols such as multi-signature (e.g., MuSig2 , from Onas Nick, Tim Ruffing, and Yannick Seurin), threshold signatures, hierarchical deterministic derivation, and "adapter signatures".
Hash functions (such as SHA256 and BLAKE) are the opposite; they act like random mixers. If you have a hash function H , adding two inputs together will not yield any relationship between their hash function outputs: H(x+y) will not equal H(x)+H(y) . While this lack of structure is precisely what makes hash functions secure, it also makes it extremely difficult to develop high-level protocols on top of them.
However, lattice cryptography also provides us with this mathematical structure. Instead of multiplying a scalar by a point on an elliptic curve, lattice cryptography multiplies a grid of numbers (matrices) by a column of numbers (vectors). If you have a public matrix A and two secret values x and y , then A(x+y) = Ax + Ay (just like (x+y)G=xG+yG in the context of discrete logarithms).
Here's an important point to note: in lattice cryptography, we typically use short secret values. When we combine lattice equations (e.g., calculating x+y ), the length of the "aggregated" secret value increases. However, as long as we properly control the magnitude of these errors, the aforementioned structured properties still hold. This means that lattices hold promise for enabling advanced protocol improvements, such as post-quantum multisignatures, zero-knowledge proofs, and confidential assets.
How lattice signatures work: Schnorr with vectors
If you can understand Schnorr signatures on Bitcoin, you've got a 50% grasp of lattice signatures, such as Dilithium . This most mainstream lattice signature design uses a technique we jokingly call the "Schnorr scheme with vectors."
In traditional Schnorr signatures, the signing process using private key x is as follows:
- Select a random number
r - Create a "commitment" for this number.
- Hash the promise and the data to be signed to derive a random challenge value
e - Use this challenge value to mask your private key, producing the final response value
z = r + xe
In lattice-based signature schemes, we run the exact same steps, only using matrices and vectors. The equations look similar: for example, many early studies on lattice signatures used the equation z = r + Se , where S is a secret matrix, e is a challenge vector, and r is a random vector.
Reject sampling*
There is a significant security issue here. To make lattice equations difficult for quantum computers to solve, the numbers in vectors z and r must be small (this is the so-called " short integer solution " problem).
However, when we calculate z = r + Se , it creates a statistical dependence between the signature z and the secret value S behind it (this is not the case with Schnorr signatures, because r and e can be arbitrary). If an attacker can collect enough of your signatures, they will notice the statistical bias and may be able to reveal your private key.
To address this problem, lattice cryptography employs a clever technique called the " Fiat-Shamir transformation with rejection " (also known as "rejection sampling").
The idea is quite simple: after the signer generates the signature z , they first check if adding the private key causes a significant shift in this value. If the signature appears "biased" and potentially reveals the private key (as shown in the diagram above), they discard the signature and try again with a new random number (generating a signature). This process is repeated multiple times until the final signature perfectly masks the private key (as shown by the dotted line in the diagram above).
A reminder . In practice, the middle Se is itself a random distribution. However, in principle, there is no difference: the offset of the distribution will reveal some information about the underlying secret value S , so we must eliminate the offset (which is also because it can be proven that this is very simple to do).
Next step
Lattice-based cryptography is a profound topic and a promising direction in post-quantum cryptography, going far beyond simply replacing current digital signature schemes. It provides the mathematical foundation to ensure the quantum security of Bitcoin, while also holding the promise of upgrades to more efficient aggregation and threshold schemes.
For a more in-depth explanation, including the mathematics behind the "Discrete Gaussian function," the shortest vector problem, and rejection sampling, please read the full version of our research report and watch the full video demonstration .
(over)
