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

## Section 1: Introduction

> [!NOTE]
> **Acknowledgements.** This blog post is based in part on research conducted during my time at [Blockstream Research](https://x.com/blksresearch). I am grateful for the support and the opportunity to work on these topics.
> Additional thanks to Jonas Nick for a careful review of this blog and very helpful suggestions and to Mykyta Redko for noticing several substantial mistakes in the explanations.

With the publication of [recent paper](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) by Google Quantum AI, there was a hectic discussion (frankly, in some places turning into panic) around timeline of appearence of the first Cryptographically Relevant Quantum Computer (CRQC). Opinions of course largely vary, but one point that everyone seems to agree on: we need to put on rails quantum-secure algorithms as soon as possible.

This, of course, includes a multitude of currently existing protocols; in particular, in Bitcoin (and in the blockchain field in general) the first natural step is to construct the post-quantum (PQ) secure digital signature scheme. However, even this first step is highly debatable: we have a batch of potential PQ schemes, but they are _(a)_ significantly worse than discrete log (DL) constructions (at least by a factor of $16\times$), _(b)_ underlying security assumptions were commonly less studied than pre-quantum counterparts.

As of now, two primary candidates for PQ signatures are _hash-based_ and _lattice-based_ constructions. For hash-based cryptography, Blockstream has already conducted very fruitful analysis and research: see, for example, ["Hash-based Signature Schemes for Bitcoin"](https://eprint.iacr.org/2025/2203) survey by Jonas Nick and Mikhail Kudinov or [SHRIMPS](https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355) by Jonas Nick. Now is the turn for lattice-based constructions!

> [!IMPORTANT]
> We note that there are also code-based constructions, but they have tremendous sizes of either public key or a signature: for instance, a notable (prior) NIST candidate [LESS](https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-2/spec-files/less-spec-round2-web.pdf) has public keys of sizes starting from 13.9KB. That said, for now they do not seem like a viable option for Bitcoin.

### Topic of this blog

As announced above, we are going to consider basic ideas behind lattice-based signature schemes. In particular, after this blog, one will get a solid grasp of a key technique called _Fiat-Shamir with aborts_ (aka _rejection sampling_) which is used in Dilithium or, for instance, many lattice-based proving systems (cf. see [lattice-based product proofs](https://eprint.iacr.org/2020/517.pdf)). Surprisingly, this technique greatly resembles the classical Schnorr signature construction based on discrete logarithm assumption. Along the way we provide a basic toolkit for understanding lattice-based schemes that will hopefully make introduction to this field of Cryptography easier.

More specifically, in this blog we will understand the Lyubashevsky's construction from his famous paper ["Lattice Signatures Without Trapdoors"](https://eprint.iacr.org/2011/537.pdf), which is arguably one of the most influential papers in the whole lattice-based cryptography.

## Brief introduction to Lattices

### Lattices

Let us introduce the main object of interest. We define the $m$-rank lattice $\Lambda \subseteq \mathbb{R}^d$ as all integer linear combinations of some fixed set of linear independent vectors $\mathbf{b}_1,\dots,\mathbf{b}_m$ in $\mathbb{R}^d$ (where $m\leq d$). That is,
\begin{equation*}
\Lambda \triangleq \left\{ \sum_{i=1}^m \lambda_i\mathbf{b}_i: \lambda_1,\dots,\lambda_m \in \mathbb{Z} \right\}.
\end{equation*}

As a concrete example to better visualize this object, consider the two-dimensional ($m=d=2$) lattice below.

<div style="text-align:center">
<img src="https://hackmd.io/_uploads/BybTTV82Wg.png" alt="Lattice example" style="width:65%;">
</div>

_**Figure 1.** Example of a rank-2 lattice spanned by vectors $\mathbf{b}_1=(3,1)$ and $\mathbf{b}_2=(2,3)$. Resultant lattice $\Lambda$ is a set of blue points._

When I first saw the definition, I could not but wonder "what useful can we even extract from this highly straightforward definition?" However, before cryptographers noticed that lattices are a source of a large number of computationally hard problems, lattices had been first proven to be useful in Mathematics, where they have been used going back to at least to the 18th century. In fact, lattices naturally arised in many areas such as number theory or sphere packings (with both being one way or another relevant to lattice and code-based cryptography).

> [!NOTE]
> Sometimes I encounter misconception that "lattices are too immature compared to hash-based cryptography." However, lattices have been used and studied long before hash functions were even invented :grimacing: (the latter dates back to ~1950).
> Yet, lattices do have a much richer algebraic structure than hashes. While this enables many advanced cryptographic protocols (e.g., multisignatures or SNARKs), we still need to be highly cautious with regards to security.

### Lattice Problems in Cryptography

**Lattice-based cryptography** resolves around assumptions that can be reduced to solving some hard problems over lattices $\Lambda$. In turn, these problems are currently believed to be hard even for quantum computers. Currently there is a large set of such assumptions: _e.g._, Shortest Vector Problem ($\mathsf{SVP}$), Closest Vector Problem ($\mathsf{CVP}$), Bounded Distance Decoding ($\mathsf{BDD}$), Lattice Isomorphism Problem ($\mathsf{LIP}$), Decisional Shortest Vector Problem ($\mathsf{GapSVP}$) among others.

In this blog we will require only a single among these assumptions.

**(approximate) Shortest Vector Problem ($\gamma$-SVP).** The goal is to find a "very short" vector on $\Lambda$. One can (rather easily) show that $\Lambda$ contains the _shortest_ vector (_i.e._, exists $\mathbf{u} \in \Lambda$ such that $\|\mathbf{u}\|=\min_{\mathbf{v} \in \Lambda}\|\mathbf{v}\|$, whose length we denote by $\lambda_1(\Lambda)$), but finding such a vector is considered a hard problem even for quantum computers. We call such a problem $\mathsf{SVP}$.
However, building practical protocols based on "raw" $\mathsf{SVP}$ above is nearly impossible. We soften the requirements for this problem: suppose we accept vectors of norm below $\gamma\lambda_1(\Lambda)$ for some factor $\gamma>1$. Turns out that such a modified problem remains hard even for relatively large factors: say, for $\gamma=\mathsf{poly}(\sqrt{d})$. We call this modified problem $\gamma$-SVP.

This problem is illustrated below.


_**Figure 2.** Illustration of $\gamma$-$\mathsf{SVP}$. Consider the lattice $\Lambda'$ spanned by $\mathbf{b}_1=(3,8)$ and $\mathbf{b}_2=(4,6)$ (which is by the way the sublattice of a lattice $\Lambda$ previously defined in Figure 1). Its two shortest vectors are $\mathbf{u}=(-1,2)$ and $-\mathbf{u}$ each of length $\lambda_1(\Lambda')=\sqrt{5}$. The approximate version $\gamma$-$\mathsf{SVP}$ for $\gamma \approx 2.61$ consists in finding vectors of length below $\sqrt{34}$ (marked in purple in the Figure). For instance, $\mathbf{u}'=(2,-4)$ of length $\sqrt{20}$ is the solution to approximate $\mathsf{SVP}$, but not for a standard $\mathsf{SVP}$._

### Short Integer Solution

While building cryptographic systems directly based on lattice assumptions is possible (say, _Hawk_ does exactly that), typically we use another assumptions that have reductions to lattice assumptions. Two most notable examples are _Short Integer Solution (SIS)_ and _Learning with Errors (LWE)_. For this introductory blog, we are going to focus on the first of two.

Consider the linear equation $\mathbf{Ax}=0$ where $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$. Solving this equation is easy (_e.g._, simply by Gaussian elimination). However, assume that we require solution $\mathbf{x} \in \mathbb{Z}^m$ to be "short": i.e., $\|\mathbf{x}\|_{\infty} < \beta$ (where $\|\mathbf{x}\|_{\infty} := \min_{i \in [m]}|x_i|$ denotes the $\ell^{\infty}$-norm) for some $\beta \ll q$. We call the instance of such a problem $\mathsf{SIS}_{q,n,m,\beta}$ and for suitable choice of $q,n,m,\beta$, it is exponentially hard even for quantum computers.

_Exercise 1._ Show that the solution to $\mathsf{SIS}_{q,n,m,\beta}$ exists if $m>\frac{n\log q}{\log(1+\beta)}$.

Additionally, further denote the set of "short" vectors by $S_{\eta}$, where
\begin{equation*}
S_{\eta} := \{\mathbf{x} \in \mathbb{Z}^n: \|\mathbf{x}\|_{\infty} \leq \eta\}.
\end{equation*}

#### Inhomogeneous SIS

One important tweak of this assumption is considering the non-homogeneous version of the same equation: $\mathbf{Ax}=\mathbf{t}$. Such modification already allows to consider the decisional assumption instead of a search one. Specifically, we introduce the _inhomogeneous short integer solution_ ($\mathsf{ISIS}$) that states that it is computationally hard to distinguish the following two distributions $D_0$ and $D_1$:
- $D_0$: pick a random sample from $\mathbb{Z}_q^{n \times m} \times \mathbb{Z}_q^n$;
- $D_1$: sample $A \gets_R \mathbb{Z}_q^{n \times m}$, sample a short $\mathbf{s} \in \mathbb{Z}^m$ (such that $\|\mathbf{s}\|_{\infty} < \delta$), compute $\mathbf{t} \gets \mathbf{As}$, and output the tuple $(\mathbf{A}, \mathbf{t})$.

One can show that $\mathsf{ISIS}$ is equivalent to $\mathsf{SIS}$ for suitable relation between underlying $\beta$ and $\delta$. This assumption allows us to build the key generation as follows:
- the _secret key_ is the matrix $\mathbf{S} \in S_{\eta}^{m \times k}$ consisting of short elements.
- the _public key_ is $\mathbf{T} := \mathbf{AS}$ for random $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$.

_Exercise 2._ Show that the problem of recovering the secret key from the public key is equivalent to solving $\mathsf{ISIS}$ (assuming $k=\mathsf{poly}(n)$).

#### Relation to Lattices

Here one might wonder: where are the lattices? One possible explanation that can be fitted into this blog is the following: for the $\mathsf{SIS}_{q,n,m,\beta}$ instance with matrix $\mathbf{A}$, define the following lattice:
\begin{equation*}
\Lambda_A^{\perp} = \{\mathbf{z} \in \mathbb{Z}^m: \mathbf{Az} = 0 \; (\text{mod} \; q)\}.
\end{equation*}

_Observation:_ solving $\mathsf{SIS}_{q,n,m,\beta}$ is equivalent to solving $\gamma$-$\mathsf{SVP}$ for appropriate $\gamma$. This is quite straightforward from the very definition of $\Lambda_A^{\perp}$: any vector on this lattice is the solution to $\mathbf{A}\mathbf{x}=0$; if we were able to solve $\mathsf{SVP}$ on this lattice, we essentially find the short solution to this equation, which is exactly what $\mathsf{SIS}$ requires.

## Section 2: Fiat-Shamir with Aborts

### Motivation

We have just observed that lattice-based assumptions allow us to construct the one-way map $\mathbf{S} \mapsto \mathbf{AS}$ for a public matrix $\mathbf{A}$ and a "short" matrix $\mathbf{S}$. This should somewhat resemble how for a cyclic group $\mathbb{G}=\langle a \rangle$, the map $s \mapsto a^s$ is one-way, given discrete log assumption holds. This motivates us to ask ourselves the following question:

> _Can we "recreate" the Schnorr signature protocol, but instead of group multiplication map $s \mapsto a^s$, use the map $\mathbf{S} \mapsto \mathbf{A}\mathbf{S}$?_

The answer turns out to be yes! However, this is not that simple as it seems; thus the suffix "with aborts." In the rest of this section, we will take a look on how to make this idea work.

### Schnorr Signature Scheme

Of course, we need to recap how Schnorr signatures work. Recall that describing the signature scheme means specifying three procedures:
- $\mathsf{KeyGen}(1^{\lambda}) \to (\mathsf{pk}, \mathsf{sk})$: generates the keypair;
- $\mathsf{Sign}(\mathsf{sk},\mu) \to \mathsf{sig}$: signs the message $\mu$ using secret key $\mathsf{sk}$, thereby producing the signature $\mathsf{sig}$;
- $\mathsf{Verify}(\mathsf{pk},\mu,\mathsf{sig}) \to \{0,1\}$: verifies the signature $\mathsf{sig}$ over message $\mu$ based on the public key $\mathsf{pk}$.

Schnorr signature is arguably the most elegant, effective, and simple way of building the signature scheme based on discrete logarithm assumption, which is currently heavily employed in Bitcoin. However, one should first rather start with the _Schnorr identification protocol_. Specifically, assume the group $\mathbb{G}$ of order $q$ is generated by $g \in \mathbb{G}$; then, to prove that the signer knows the secret key $\alpha$ corresponding to the public key $h \in \mathbb{G}$ (such that $g^{\alpha}=h$), he participates in the interactive protocol depicted below:

<div style="text-align:center">
<img src="https://hackmd.io/_uploads/SJIX9C9h-g.png" alt="Lattice example" style="width:70%;">
</div>

_**Figure 3**. Schnorr identification protocol over keypair $(\alpha,h)$ (with $h=g^{\alpha}$)._

The _Fiat-Shamir heuristic_ allows signer to avoid interaction with the verifier by deriving $e$ deterministically using the hash function $\mathsf{H}: \mathbb{G}^2 \to \mathbb{Z}_q$. Specifically, the signer computes the challenge $e$ as $e \gets \mathsf{H}(h,a)$; the "proof" in such case is $(e,z)$. Finally, to build the _signature scheme_, one simply incorporates message $\mu$ in the derivation of the challenge $e$. Specifically, $\mathsf{Sign}(h,\mu)$ works as follows:
- Construct the commitment $g^r$ to some random masking scalar $r \gets_R \mathbb{Z}_q$, just as before;
- Compute the challenge as $e \gets \mathsf{H}(\mu,a)$;
- Compute the scalar $z=r+\alpha e$ that masks the underlying secret $\alpha$; output $(e,z)$ as a signature.

Finally, the verifier can check the signature $(h,\mu,\sigma)$ by $e=_?\mathsf{H}(\mu, g^zh^{-e})$.

### Attempt #1: "Lattice" Schnorr Signature

Since we already discovered that $\mathbf{S} \mapsto \mathbf{AS}$ looks like a pre-quantum counterpart $\alpha \mapsto g^{\alpha}$, let us try to simply slap this one-way map to a Schnorr identification protocol in _Figure 4_ above. The natural first attempt would be something along these lines (where we pick dimensionalities of $\mathbf{r}$, $\mathbf{a}$, and $\mathbf{e}$ for matrix multiplications to make sense):

<div style="text-align:center">
<img src="https://hackmd.io/_uploads/H1pVfJsnbx.png" alt="Lattice example" style="width:70%;">
</div>

_**Figure 4**. Attempt #1 of a "lattice" Schnorr identification protocol over keypair $(\mathbf{S},\mathbf{T})$ (with $\mathbf{T}=\mathbf{AS}$ where $\mathbf{T} \in \mathbb{Z}_q^{n \times k}$, $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, and $\mathbf{S} \in \mathbb{Z}_q^{m \times k}$)._

First, is the scheme even correct? Let us plug everything into the verification equation:
\begin{equation*}
\mathbf{Az} = \mathbf{A}(\mathbf{S}\mathbf{e}+\mathbf{r}) = (\mathbf{AS})\mathbf{e}+(\mathbf{A}\mathbf{r}) = \mathbf{Te}+\mathbf{a}.
\end{equation*}

Thus, the scheme is correct. Is it sound? Completely not. One can find multitude of reasons why this scheme fails. For instance:

1. Given $\mathbf{a} \in \mathbb{Z}_q$, it is easy to find $\mathbf{r}$ for commitment equation $\mathbf{a}=\mathbf{Ar}$ to hold. Indeed, this is just a matter of solving the linear equation over $\mathbb{Z}_q$.
2. Even assuming the commitment $\mathbf{a}$ were binding, finding $\mathbf{z}$ that would satisfy the equation $\mathbf{Az}=\mathbf{Te}+\mathbf{a}$ is possible _even without the secret key $\mathbf{S}$_. Again, just solve the linear equation after finding any $\mathbf{e}$.

Seems like we are screwed at this point.

### Attempt #2: Making everything small

Notice that _Attempt #1_ was insecure since we could easily forge $\mathbf{z}$ and easily recover $\mathbf{r}$ from $\mathbf{a}$. This was possible because they are _arbitrary_ solutions to corresponding systems of linear equations. As we have seen in the SIS assumption, if we made both $\mathbf{z}$ and $\mathbf{r}$ "short", we would have hope to fix soundness of this protocol. So let us try doing exactly that. We will sample randomness $\mathbf{r}$ from some _short_ distribution $\chi^m$ (imagine some distribution $\chi$ over $\mathbb{Z}_q$ where the $\ell^{\infty}$-norm of a sampled value is bounded above by some small $\varepsilon \in \mathbb{Z}_{>0}$). Making $\mathbf{z}$ (which is $\mathbf{r}+\mathbf{Se}$) short is trickier: while $\mathbf{r}$ is now short, we need to ensure $\mathbf{Se}$ is short as well. Consequently, as $\mathbf{S}$ is already small, we need to ensure that $\mathbf{e}$ is both short _and_ the set of possible values of $\mathbf{e}$ is large enough. Specifically, we will sample it from the set $B_{\kappa}$ where:
\begin{equation*}
B_{\kappa} := \{\mathbf{x} \in \mathbb{Z}_q^k: x_i \in \{0,\pm 1\} \; \text{and number of non-zero $x_i$'s is $\kappa$}\}.
\end{equation*}

Frankly speaking, this set came out of nowhere (as many things in lattice-based cryptography). The reasoning why this set is used is roughly the following:

- we want the challenge set to be large enough; this is the case for this set (see _Exercise 3_ below);
- we want elements of this challenge set to be small; clearly this is the case since for each $\mathbf{e} \in B_{\kappa}$ we have $\|\mathbf{e}\|_{\infty}=1$;
- desirably, we want implementation of hashing to $B_{\kappa}$ to be as simple as possible: it is the case since the element of $B_{\kappa}$ can be viewed as a ternary string.

_Exercise 3._ Show two properties of the challenge set $B_{\kappa}$: _(a)_ $\#B_{\kappa}=2^{\kappa}\binom{k}{\kappa}$ (_i.e._, this set is fairly large), _(b)_ for arbitrary $\mathbf{S} \in S_{\eta}^{m \times k}$, one has $\|\mathbf{Se}\|_{2} \leq \eta\kappa\sqrt{m}$, where $\|\cdot\|_2$ denotes the standard Euclidean norm (_i.e._, we have a nice bound for the norm of $\mathbf{Se}$ involved in the computation of $\mathbf{z}$).

Now, since both $\mathbf{e}$ and $\mathbf{r}$ are short, $\mathbf{z}$ is also short. Thus, to prevent adversary from sending large $\mathbf{e}$ and $\mathbf{r}$, we check that $\|\mathbf{z}\|_2$ is small enough (_i.e._, below some threshold $\tau$; one might think of something like $\tau:=\max_{\mathbf{e} \in B_{\kappa}}\|\mathbf{Se}\|_2 + \mathbb{E}_{\mathbf{r} \sim \chi^m}[\|\mathbf{r}\|_2]$, but it is irrelevant for the current level of discussion).

With these modifications in mind, our second attempt is as follows:

<div style="text-align:center">
<img src="https://hackmd.io/_uploads/BJIIRkihWg.png" alt="Lattice example" style="width:70%;">
</div>

_**Figure 5**. Attempt #2 of a "lattice" Schnorr identification protocol over keypair $(\mathbf{S},\mathbf{T})$ (with $\mathbf{T}=\mathbf{AS}$ where $\mathbf{T} \in \mathbb{Z}_q^{n \times k}$, $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, and $\mathbf{S} \in \mathbb{Z}_q^{m \times k}$)._

Is the scheme correct? Yes, for the same reasons as in Attempt #1.

Is it sound? Well, let us check the "trivial" attacks:
- Can we find short $\mathbf{r}$ such that $\mathbf{Ar}=\mathbf{a}$? This amounts to solving ISIS, thus it seems infeasible;
- Can we find short $\mathbf{z}$ such that $\mathbf{Az}=\mathbf{Te}+\mathbf{a}$? (_i.e._, without knowing $\mathbf{S}$) Again, that's the instance of the ISIS problem, which is hard to solve.

So... Can we conclude that the scheme is sound now?..

Nope! :face_with_diagonal_mouth:

However, the reason now is much more subtle and can be better spotted during the security proof. Here is the simple explanation: recall that the whole idea of computing $\mathbf{z}$ in such a way is to "blind" the underlying secret $\mathbf{S}$. However, can we claim that $\mathbf{z}$ and $\mathbf{S}$ are independent? Not really.

> [!NOTE]
> For those who recall the Schnorr security proof, the following explanation might be more satisfactory: recall that the EUF-CMA proof consists in (a) simulating the honest signer, (b) using forking lemma to extract the underlying secret. In _Figure 5_, it is completely unclear how to do (a): specifically, where to sample $\mathbf{z}$ from. Even if we knew the distribution of $\mathbf{z}$, it might depend on $\mathbf{S}$, which would make simulation problematic.

For this reason, we need to somehow make $\mathbf{z}$ and $\mathbf{S}$ independent. But how? Turns out that the following idea will work:

> Upon generating the candidate pair $(\mathbf{e},\mathbf{z})$, check whether obtained $\mathbf{z}$ is "good enough". If not, throw it away and repeat the signing procedure.

This is exactly why the underlying paradigm is called "rejection sampling" or Fiat-Shamir _with aborts_: we abort the execution of the signing procedure if we are not satisfied with the generated values. But what it means for $\mathbf{z}$ to be "good enough"? For this, we will pick a concrete distribution $\chi$ that will yield us some nice properties, and see when statistical distance between $\mathbf{z}$ and $\mathbf{S}$ is negligible.

### Discrete Gaussian Distribution

If you thought that the choice of the challenge space $B_{\kappa}$ was random, here is what was really _completely_ random to me when I started learning lattice-based signatures. Introduce the **Gaussian distribution $D_{\sigma,\mathbf{v},\Lambda}^m$** over lattice $\Lambda \subseteq \mathbb{R}^m$ with width parameter $\sigma \in \mathbb{R}_{>0}$ and center $\mathbf{v} \in \mathbb{R}^m$ as follows:
\begin{equation*}
D_{\mathbf{v},\sigma,\Lambda}^m(\mathbf{z}) := \rho_{\mathbf{v},\sigma}^m(\mathbf{z})/\rho_{\mathbf{v},\sigma}^m(\Lambda) \; \text{where} \; \rho_{\mathbf{v},\sigma}^m(\mathbf{z}) := \exp(-\|\mathbf{z}-\mathbf{v}\|_2^2/2\sigma^2).
\end{equation*}

Here, we abuse notation to denote $\rho_{\sigma}^m(\Omega)=\sum_{\mathbf{w} \in \Omega}\rho_{\sigma}^m(\mathbf{w})$ for a discrete set $\Omega \subseteq \mathbb{R}^m$. We omit $\Lambda$ and $\mathbf{v}$ in the index when $\Lambda=\mathbb{Z}^m$ and $\mathbf{v}=0$, respectively.

I believe this definition needs some unpacking. The key idea here is that we assign the probability at each point $\mathbf{z}$ of lattice $\Lambda$ to be proportional to $\exp(-\|\mathbf{z}-\mathbf{v}\|_2^2/2\sigma^2)$. To turn this into a valid probability distribution, we need to divide all these probabilities by a normalization constant $\sum_{\mathbf{w} \in \Lambda}\exp(-\|\mathbf{w}-\mathbf{v}\|_2^2/2\sigma^2)$.

In principle, the name _discrete_ Gaussian is given exactly because the distribution greatly resembles continuous counterpart (where we had the density $e^{-\|\mathbf{z}-\mathbf{v}\|^2/2\sigma^2}/\int_{\mathbb{R}^m}e^{-\|\mathbf{z}-\mathbf{v}\|^2/2\sigma^2}\text{d}\mathbf{z}$; in the continuous case, the integral in the denominator happens to be nicely computable). Moreover, if one takes a look at how such distribution is shaped, one will instantly recognize the standard multivariate Gaussian distribution:


_**Figure 6**. 2D discrete Gaussian distribution. Figure taken from the paper ["Lattice Signatures and Bimodal Gaussians"](https://eprint.iacr.org/2013/383.pdf) by Ducas, Durmus, Lepoint, and Lyubashevsky._

#### Why discrete Gaussians?

I believe the answer to the question "why pick this particular distribution" is similar to why we use continuous Gaussians in statistics. This is a natural choice in a sense that it behaves nicely under many operations (e.g., under Fourier transform, convolutions; sum of discrete Gaussians is statistically close to a single discrete Gaussian etc.)

However, in the case of our problem (making $\mathbf{z}$ and $\mathbf{S}$ independent), we will need the following two properties of discrete Gaussians.

**Property (A)** (_samples from $D_{\sigma}^m$ are short with overwhelming probability_). For any $\beta>1$, one has:
\begin{equation*}
\text{Pr}[\|\mathbf{z}\|_2>\beta\sigma\sqrt{m} \; | \; \mathbf{z} \gets_R D_{\sigma}^m] < \beta^me^{m(1-\beta^2)/2}.
\end{equation*}

**Property (B)** (_ratio of centered and uncentered Gaussian is almost always bounded._) For any $\mathbf{v} \in \mathbb{Z}^m$, if $\sigma=\alpha\|\mathbf{v}\|$, one has:
\begin{equation*}
\text{Pr}[D_{\sigma}^m(\mathbf{z})/D_{\mathbf{v},\sigma}^m(\mathbf{z}) < e^{12/\alpha+1/(2\alpha^2)} \; | \; \mathbf{z} \gets_R D_{\sigma}^m] > 1 - 2^{-100}.
\end{equation*}

Proofs of both facts are purely mechanical. See, e.g., [original Lyubashevsky's paper](https://eprint.iacr.org/2011/537.pdf), Section 4. We will further denote the "magical" constant $e^{12/\alpha+1/(2\alpha^2)}$ by $M_{\alpha}$.

_Exercise 4._ Assuming $\alpha>1$, what is the possible range of $M_{\alpha}$?

While I believe _Property (A)_ is intuitive (we will use it for $\beta$ slightly exceeding $1.0$), one might wonder why do we need _Property (B)_. We will discover this in the very next subsection.

### Rejection sampling

Let us now set $\chi^m := D_{\sigma}^m$ in _Figure 6_. How is $\mathbf{z}$ specifically distributed? Since $\mathbf{z}=\mathbf{Se}+\mathbf{r}$ and $\mathbf{r} \sim D_{\sigma}^m$ is the centered discrete Gaussian, $\mathbf{z}$ is the "biased" Gaussian $D_{\mathbf{Se},\sigma}^m$ with a small offset vector $\mathbf{Se}$.

This is exactly the problem: distribution of $\mathbf{z}$ depends on the small bias $\mathbf{Se}$; thus, by observing multiple $\mathbf{z}$'s with the same $\mathbf{S}$, an adversary can potentially obtain information about $\mathbf{S}$.

If only we could get rid of this offset... The following lemma will come to a rescue:

**Lemma.** Let $f$ and $g$ be two probability distributions with support $\Omega$ that satisfy $f(z) \leq Mg(z)$ for all $z \in \Omega$ and some fixed constant $M \in \mathbb{R}_{\geq 1}$. Then, the following distribution (call it $\widetilde{f}$) is the same as distribution $f$:
1. Sample $z \gets_R g$.
2. Output $z$ with probability $f(z)/Mg(z)$, otherwise go to step 1.

Roughly the idea of the lemma is that if $f$ is our "target distribution" while $g$ is the "real distribution", then if we have a nice inequality between $f$ and $g$ pointwise, we can simulate the distribution of $f$ by discarding samples from $g$ with some probability that depends on the sampled value.

This process has a nice visualization given below (similarly to _Figure 7_, taken from the BLISS paper, which features amazing illustrations). Assume $f$ and $g$ satisfy inequality from the lemma so that $Mg$ is above $f$. Then, rejection sampling consists of first picking the point under $Mg$, and further accepting it is below $f$.


_**Figure 7**. Rejection sampling procedure illustration. Figure taken from the paper ["Lattice Signatures and Bimodal Gaussians"](https://eprint.iacr.org/2013/383.pdf) by Ducas, Durmus, Lepoint, and Lyubashevsky._

Does this lemma remind you of anything? The key trick is to apply this lemma as follows:
1. Our "target" distribution $f$ is the unbiased discrete Gaussian $D_{\sigma}^m$;
2. Our "real" distribution $g$ is the biased Gaussian $D_{\mathbf{Se},\sigma}^m$.

Can we apply this lemma? Here is where the _Property (B)_ of discrete Gaussian comes into play: we have a magical constant $M_{\alpha}$ such that $D_{\sigma}^m(\mathbf{z}) \leq M_{\alpha}D_{\mathbf{Se},\sigma}^m$ holds with overwhelming probability! (moreover, one can easily determine $\alpha$ from the fact that $\|\mathbf{Se}\|_2 \leq \eta\kappa\sqrt{m}$: see _Exercise 3_).

> [!WARNING]
> To be fully careful, the lemma must be adjusted so that inequality $f(z) \leq Mg(z)$ happens with overwhelming probability $1-\varepsilon$. One can then show that in such case distribution $\widetilde{f}$ will be at statistical distance $\varepsilon/M$ from the distribution $f$.

### Attempt #3: Lyubashevsky Signature

Finally, to fix scheme in _Figure 2_, we simply accept $(\mathbf{e},\mathbf{z})$ with probability $D_{\sigma}^m(\mathbf{z})/M_{\alpha}D_{\mathbf{Se},\sigma}(\mathbf{z})$. That fixes the whole scheme. See illustration below.


_**Figure 8**. Fixed lattice-based Schnorr protocol (essentially the original scheme from the Lyubashevsky's paper)._

#### Security proof sketch*

> [!NOTE]
> The following is completely optional to read.

Recall that to prove that the signature scheme is secure, we need to _(a)_ simulate an honest signer and _(b)_ use forking lemma to extract the solution to the instance of some hard problem.

Step _(a)_ is a simple application of rejection sampling lemma: instead of sampling $\mathbf{r} \gets_R D_{\sigma}^m$, computing challenge $\mathbf{e} \gets \mathsf{H}(A\mathbf{r}, \mu) \in B_{\kappa}$, and outputing the candidate $(\mathbf{e}, \mathbf{z}:=\mathbf{Se}+\mathbf{r})$, we are going to first sample $\mathbf{z} \gets_R D_{\sigma}^m$ and $\mathbf{e} \gets_R B_{\kappa}$ and reprogram the random oracle as $\mathsf{H}(\mathbf{Az}-\mathbf{Te},\mu) \gets \mathbf{e}$.

Step _(b)_ assuming the adversary outputs a valid signature $(\mathbf{z},\mathbf{e})$ with non-negligible probability $\delta$, by Forking lemma he outputs another valid signature $(\mathbf{z}^*,\mathbf{e}^*)$ with probability $\propto \delta^2$. Moreover, the underlying randomness is the same, _i.e._,
\begin{equation*}
\mathbf{Az} - \mathbf{Te} = \mathbf{Az}^*-\mathbf{Te}^*.
\end{equation*}

By using the fact $\mathbf{T}=\mathbf{AS}$, we obtain
\begin{equation*}
\mathbf{A}((\mathbf{z}-\mathbf{z}^*)+\mathbf{S}(\mathbf{e}^*-\mathbf{e})) = 0,
\end{equation*}

where $(\mathbf{z}-\mathbf{z}^*)+\mathbf{S}(\mathbf{e}^*-\mathbf{e})$ is a short solution to $\mathbf{Ax}=0$. Thus, we have constructed the reduction from breaking the signature to solving an appropriate SIS instance.

#### Performance

Frankly speaking, the scheme above is highly ineffective. Original paper proposes parameters where signatures are of size 19.9KB while public keys are of size 128KB. Nonetheless, the ideas presented above can be largely optimized. In particular:
- Instead of using $\mathbb{Z}_q$, almost all papers use ring $\mathcal{R}_q := \mathbb{Z}_q[X]/(X^d+1)$ for $d$ being a power-of-two. Reasons why this ring is more effective are outside the scope of this blog.
- One can choose different distributions from discrete Gaussian. For instance, the [BLISS signature scheme](https://eprint.iacr.org/2013/383.pdf) proposed to use bimodal Gaussian distribution and almost directly reuse construction above. Resultant signatures are of size 5.6KB while public keys are of size 7KB. Unfortunately, the scheme turned out to be insecure against [side-channel attacks](https://eprint.iacr.org/2017/505.pdf).
If one changes discrete Gaussian to a uniform distribution, one obtains [Dilithium](https://eprint.iacr.org/2017/633.pdf). However, expectedly, the idea of rejection sampling significantly differs (and in a way simplifies).

## Next steps

In this blog we considered one key paradigm of lattice-based signatures: Fiat-Shamir with Aborts. While it covers numerous constructions (and used in the majority of papers implicitly), there is one more paradigm called _Hash-and-sign_ that is needed for understanding [_Falcon_](https://falcon-sign.info/falcon.pdf) or [_Hawk_](https://eprint.iacr.org/2022/1155.pdf). Such schemes exploit geometry of lattices directly: one first hashes the message $\mu$ to the point in $\mathbb{Z}^{2n}$, and then uses some secret geometric characterization of the lattice to transform this point (in case of _Hawk_ secret key is the short basis $\mathbf{B}$ of some specific lattice while public key is the quadratic form $\mathbf{B}^{\top}\mathbf{B}$; in case of _Falcon_ the public key is the lattice basis while the secret key is the basis for orthogonal lattice).

This direction continues to attract a lot of attention in both academia and industry, and for good reason. We are actively exploring these ideas further, and will return to them in future posts and materials at Blockstream.