Lattice Gadget Trapdoors

Lattice Trapdoors

At the core of lattice-based cryptography is the Ajtai function $$ f_{\boldsymbol{A}}({x}) = \boldsymbol{A}{x} \bmod q, $$ where $\boldsymbol{A} \in \mathbb{Z}_q^{n \times m}$ is a publically sampled "fat" matrix. The function is easy to compute, but inverting it —namely, finding a short preimage ${x}$ given $\boldsymbol{A}$ and ${y} = f_{\boldsymbol{A}}({x})$—is as hard as certain worst-case lattice problems.

A lattice trapdoor is a piece of secret information that allows efficient inversion of this function. More formally, a trapdoor for the function $f_{\boldsymbol{A}}$ is some auxiliary information $\boldsymbol{T}$ such that, given ${y} = f_{\boldsymbol{A}}({x})$, one can efficiently find a small ${x}$ satisfying $\boldsymbol{A}{x} \equiv{y} \pmod q$.

There are two main types of lattice trapdoors in the literature: short basis trapdoors and gadget trapdoors.

Type I: Short Basis trapdoors

The first class of trapdoors, dating back to [GGH96], consists of a short basis $\boldsymbol{S}$ for a given lattice $\mathcal{L}(\boldsymbol{A}) = \left\{ {x} \in \mathbb{Z}^m:\boldsymbol{A} \equiv \boldsymbol{0} \pmod q \right\}$ such that $\boldsymbol{A}\boldsymbol{S} \equiv \boldsymbol{0} \pmod q$. Possessing such a basis allows one to efficiently sample short preimages and, more generally, to invert the Ajtai function. Short basis trapdoors are conceptually natural and is generalizable to any type of lattice. We refer the reader to Peikert’s textbook (Section 5.4.1) for more details.

Type II: Gadget trapdoors

The second class of trapdoors, known as gadget trapdoors, was introduced by [MP12]. The central idea is to reduce the inversion problem for an arbitrary public matrix $\boldsymbol{A}$ to the inversion of a highly structured gadget matrix, for which efficient algorithms are known.

In contrast to short basis trapdoors, gadget trapdoors are inherently tied to $q$-ary lattices of the form $$ \Lambda_q^{\perp}(\boldsymbol{A}) = \left\{ \boldsymbol{x} \in \mathbb{Z}^m \;\middle|\; \boldsymbol{A}\boldsymbol{x} \equiv \boldsymbol{0} \pmod q \right\}. $$ Despite this restriction, gadget trapdoors admit significantly more efficient constructions and are much simpler to implement in practice.

For these reasons, gadget trapdoors have become the dominant approach in modern lattice-based cryptography. We now take a closer look at their structure and the intuition behind why they work.

[MP12] Exact Gadget Trapdoors

Recall our goal is to invert the Ajtai function $$ f_{\boldsymbol{A}}({x}) = \boldsymbol{A}{x} \bmod q $$ for any arbitrary matrix $\boldsymbol{A}$. The key idea in [MP12] is to reduce this problem to inverting a highly structured gadget matrix $ \boldsymbol{G}$ where such inversion is easy by way of a trapdoor $\boldsymbol{T}$. More specifically, our trapdoor $\boldsymbol{T}$ for $\boldsymbol{A}$ will have the follow property: $$\boldsymbol{A} \cdot \boldsymbol{T} = \boldsymbol{G} \pmod q$$

But first, what is a gadget matrix?

1. Gadget Matrix

First, we define the basic building block of our gadget matrix: the gadget vector $$ \boldsymbol{g} = (1, 2, 4, \dots, 2^{k-1}) \in \mathbb{Z}_q^k, $$ where $k = \lceil \log_2 q \rceil$. The gadget vector has the useful property that any element $x \in \mathbb{Z}_q$ can be represented as a linear combination of the entries in $\boldsymbol{g}$ with coefficients in $\{0, 1\}$. In other words, there exists a binary vector $\boldsymbol{x} \in \{0, 1\}^k$ such that $$ x = \boldsymbol{g} \cdot \boldsymbol{x} \bmod q.$$ This property allows us to easily solve SIS with respect to the gadget vector by finding its binary representation $\boldsymbol{x}$.

The gadget matrix is then defined as the tensor product $$ \boldsymbol{G} = \boldsymbol{g} \otimes \boldsymbol{I}_n = \begin{pmatrix} \boldsymbol{g} & & & \\ & \boldsymbol{g} & & \\ & & \ddots & \\ & & & \boldsymbol{g} \end{pmatrix}$$ where $\boldsymbol{I}_n$ is the $n \times n$ identity matrix. So, we have $$ \boldsymbol{G} = \begin{pmatrix} 1 & 2 & \cdots & 2^{k-1} & 0 & 0 & \cdots & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & 1 & 2 & \cdots & 2^{k-1} & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & \cdots & 1 & 2 & \cdots & 2^{k-1} \end{pmatrix} \in \mathbb{Z}_q^{n \times nk}, $$ Crucially, the gadget matrix inherits the same useful property as the gadget vector: any vector $\boldsymbol{y} \in \mathbb{Z}_q^n$ can be represented as $$ \boldsymbol{y} = \boldsymbol{G} \cdot \boldsymbol{x} \bmod q $$ for some binary vector $\boldsymbol{x} \in \{0, 1\}^{nk}$.

Next, we explore how a trapdoor for any arbitrary matrix can be constructed.

2. Trapdoor Generation

Next we need to construct a public matrix $\boldsymbol{A}$ along with a trapdoor $\boldsymbol{T}$ such that $$ \boldsymbol{A} \cdot \boldsymbol{T} = \boldsymbol{G} \pmod q. $$ To do so, we first sample a random public matrix $\boldsymbol{A}' \in \mathbb{Z}_q^{n \times m'}$ and a random secret matrix $\boldsymbol{R} \in \mathbb{Z}_q^{m' \times nk}$. We need our secret matrix $\boldsymbol{R}$ to satisfy two conditions:

• (1) $\boldsymbol{R}$ should be short (i.e., have small entries (e.g., from $\{-1, 0, 1\}$). )
• (2) $\boldsymbol{A}' \boldsymbol{R}$ needs to be indistinguishable from uniformly random to ensure security.

We can then define our trapdoor as $$ \boldsymbol{T} = \begin{pmatrix} \boldsymbol{R} \\ \boldsymbol{I} \end{pmatrix} \in \mathbb{Z}_q^{m \times nk} $$ Finally, we construct our public matrix as $$ \boldsymbol{A} = \left( \boldsymbol{A}' \;|\; \boldsymbol{G} - \boldsymbol{A}' \cdot \boldsymbol{R} \right) \in \mathbb{Z}_q^{n \times m}. $$ where $m = m' + nk$. It is easy to see that this construction satisfies the desired property. $$ \boldsymbol{A} \cdot \boldsymbol{T} = \boldsymbol{A}' \cdot \boldsymbol{R} + \left( \boldsymbol{G} - \boldsymbol{A}' \cdot \boldsymbol{R} \right) = \boldsymbol{G} \pmod q. $$

Next, let's see how we can use the trapdoor $\boldsymbol{T}$ to translate any arbitrary inversion problem for $\boldsymbol{A}$ to an inversion problem for the gadget matrix $\boldsymbol{G}$!

3. Trapdoor PreImage Sampling

Given a target $u \in \mathbb{Z}_q^n$, we can compute a short preimage $\boldsymbol{x} \in \mathbb{Z}_q^{nk}$ such that $\boldsymbol{A} \cdot \boldsymbol{x} = u \pmod q$ using the trapdoor $\boldsymbol{T}$ as follows:

• Step 1: Compute Gadget Inversion $f^{-1}_\boldsymbol{G}(u)$ : Since $\boldsymbol{G}$ is a gadget matrix, this step is easy: we can simply compute the binary representation of each coordinate of $u$ to obtain the corresponding entries in $\boldsymbol{x}'$. (we denote the above decomposition as $\boldsymbol{G}^{-1}(u) = x'$ ): $$ \boldsymbol{G} \cdot \boldsymbol{x}' = u \bmod q. $$
• $\cdot$ Remark 1: Note that $\boldsymbol{x}'$ is a short since it is binary
• $\cdot$ Remark 2: The function $\boldsymbol{G}^{-1}(u)$ can be further randomized by instead sampling $\boldsymbol{x}'$ from the discrete Gaussian distribution over the set of all preimages of $u$ under $\boldsymbol{G}$
• (ie. $\Lambda_{q,u}^\perp (\boldsymbol{G}) = \{ \boldsymbol{x}' \in \mathbb{Z}^{nk} : \boldsymbol{G} \cdot \boldsymbol{x}' = u \bmod q \}$). $$ \boldsymbol{x'} \sim \mathcal{D}_{\Lambda_{q,u}^\perp (\boldsymbol{G}), s} $$ for some parameter $s$.
• Step 2: Compute the Preimage $\boldsymbol{x}$ via Trapdoor : Then, we compute the final preimage $\boldsymbol{x}$ by combining the intermediate preimage $x'$ with the trapdoor information: $$ \boldsymbol{x} = \boldsymbol{T} \cdot \boldsymbol{x}' $$
• It is important to note that if $x'$ is a short preimage of $f^{-1}_{\boldsymbol{G}}(u)$, then $\boldsymbol{x}$ is a short preimage of $f^{-1}_{\boldsymbol{A}}(u)$.
• To see why, note that if $$f_{\boldsymbol{G}}(\boldsymbol{x}') = \boldsymbol{G} \cdot \boldsymbol{x}' = u \bmod q,$$ then we have $$ f_{\boldsymbol{A}}(\boldsymbol{x}) = \boldsymbol{A} \cdot \boldsymbol{x} = \boldsymbol{A} \cdot ( \boldsymbol{T} \cdot \boldsymbol{x}' ) = \boldsymbol{G} \cdot \boldsymbol{x}' = u \bmod q. $$

We have thus showed how to use gadget trapdoors to efficiently invert the Ajtai function for any arbitrary public matrix $\boldsymbol{A}$.

However!

Notice that our preimage $\boldsymbol{x}$ is highly dependent on the trapdoor $\boldsymbol{T}$, and might leak information about our Trapdoor. Especially in applications like digital signatures, where the security requires that preimages be simulated without knowledge of the trapdoor for any uniform targets, this leakage can be catastrophic.

Fix: Convolution Technique

To address this issue, [Pei10] introduced the technique of adding an appropriately distributed perturbation $\boldsymbol{p}$ to our preimage $\boldsymbol{x}$ to hide the structure of the trapdoor. We thus modify our preimage sampling algorithm as follows:

• Step 0: Sample gaussian perturbation :
• $\boldsymbol{p} \leftarrow_\$ \mathcal{D}_{\mathbb{Z}^m, \sqrt{\Sigma}_p}$.
• Step 1: Adjust target $u$ to account for perturbation :
• $u' = u - \boldsymbol{A} \cdot \boldsymbol{p} \bmod q$.
• Step 2: Compute Gadget Inversion $f^{-1}_\boldsymbol{G}(\color{var(--accent)}{u'})$ :
• $\boldsymbol{x'} \sim \mathcal{D}_{\Lambda_{q,\color{var(--accent)}{u'}}^\perp(\boldsymbol{G}), r}$
• Step 3: Compute the Preimage $\boldsymbol{x}$ via Trapdoor :
• $\boldsymbol{x} = \boldsymbol{T} \cdot \boldsymbol{x'} + \boldsymbol{p}$

By sampling $\boldsymbol{p}$ from an appropriately chosen distribution— specifically, by setting \[ \Sigma_p = s^2 \boldsymbol{I} - r\,\boldsymbol{T}\boldsymbol{T}^T, \] we can invoke the convolution lemma of [Pei10], which states that the covariances of discrete Gaussian distributions add under convolution. In this setting, the parameters are chosen so that the added noise precisely compensates for the geometric structure induced by the trapdoor. As a result, the final preimage $\boldsymbol{x}$ is distributed according to $\mathcal{D}_{\mathbb{Z}^m, s}$.

Takeaways

In this post, we first reviewed the notion of lattice trapdoors. We then focused on the exact gadget trapdoor construction of [MP12], introducing the gadget vector and gadget matrix, explaining how a suitable trapdoor enables efficient preimage sampling, and showing how the convolution technique of [Pei10] eliminates leakage by ensuring that the final preimage distribution is statistically indistinguishable from a discrete Gaussian independent of the trapdoor.

From an applications perspective, it is important to note that in the MP12 construction, the public matrix $\boldsymbol{A} \in \mathbb{Z}_q^{n \times (nk + m')}$ has width $m' + nk$. In digital signature schemes, this width directly impacts the size of public keys and signatures, making matrix size a critical efficiency bottleneck. On the other hand, we require $m$ (the width of our public matrix $\boldsymbol{A}'$) to be $\approx nlog_q $ to ensure $\boldsymbol{A}'\boldsymbol{R}$ is statistically close to uniform by left over lemma. This tradeoff between security and efficiency motivates the quest for more compact gadget trapdoor constructions.

In the next post, we will examine how to construct more compact gadget trapdoors that significantly reduce the width of the public matrix while preserving efficient inversion and security. These compact constructions, culminating in the work of [YJW’23], lead to substantially smaller signature sizes and play a central role in lattice-based hash-and-sign signature schemes.