Lattices

Most of what you’ll find here is already better explained and more detailed in this document, which is a gold mine of information.

I would also highly recommend reading this incredible and well-written blog post, which easily and clearly explains how to solve problems with lattices and how they work. It provides a good intuition.

Lattices definition

Given linearly independent vectors \(b_1, b_2, \dots, b_n \in \mathbb{R}^n\), the lattice generated by \(b_1, b_2, \dots, b_n\) is the set of all integer linear combinations of those vectors:

\[ \mathcal{L} = \{x_1b_1 + x_2b_2 + \dots + x_nb_n : x_i \in \mathbb{Z}\} \]

We therefore say that the set \(B = \{b_1, b_2, \dots, b_n\}\) is a basis of the lattice \(\mathcal{L}\).

Lattice problems

Shortest vector problem

Let \(\lambda(\mathcal{L})\) denote the length of the shortest non-zero vector in the lattice \(\mathcal{L}\), such that

\[ \lambda(L) = \min_{v \in \mathcal{L} \setminus \{\mathbf{0}\}} \ v\|_N \]

The shortest vector problem (SVP) is the problem of finding a non-zero vector \(v\) in a lattice \(\mathcal{L}\), as measured by \(N\), such that

\[ \|v\|_N = \lambda(\mathcal{L}) \]

given a basis \(B\) of the lattice \(\mathcal{L}\) and an associated norm \(N\).

Closest vector problem

The closest vector problem (CVP) is a generalization of the shortest vector problem.

It is the problem of finding a lattice vector \(v\) such that \(\|v - t\| = \min_{w \in \mathcal{L}} \|w - t\|\), given a target vector \(t\) and a basis \(B\) of a lattice \(\mathcal{L}\).

Lattice-based problems

Many cryptography problems can be reduced to lattice-based problems. These problems can then be seen as a lattice problem, usually SVP or CVP, which can then be solved using the LLL algorithm.

Here are a few of them:

Finding small roots of polynomials
Subset Sum Problem
Hidden Number Problem (HNP)
Extended HNP

Finding small roots of polynomials

Finding small roots of polynomials modulo a composite integer can be solved using Coppersmith’s method.

Given an integer \(N\) and a monic polynomial \(f(x)\) of degree \(d\) with coefficients in \(\mathbb{Z}_N\), find all \(x \in \mathbb{Z}_N\) such that \(f(x) \equiv 0 \mod N\) and \(|x| < B\), with \(B\) a bound on the size of the \(x\).

This means solving for \(x\) the equation:

\[ f(x) = x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0 \equiv 0 \mod N \]

This problem can be solved using the LLL algorithm on the basis

\[ \left(\begin{array}{ccccc} N & & & & \\ & BN & & & \\ & & B^2N & & \\ & & & \ddots & \\ & & & & B^{d-1}N \\ a_0 & a_1 & a_2 & \dots & a_{d-1} & B^d \end{array}\right) \]

Subset Sum Problem

The subset sum problem is a special case of the knapsack problem.

Given a set of integers \(S = \{s_1, s_2, \dots, s_n\}\) and a target integer \(t\), find a subset \(S' \subseteq S\) such that

\[ \sum_{s_i \in S'} s_i = t \]

This is a NP-Hard problem to solve, except in two cases:

The density of the set \(S\) is low enough that we can use the LLL algorithm.
The set \(S\) is a Superincreasing sequence

Hidden number problem

Given a prime \(p\) and a secret integer \(\alpha \in \mathbb{Z}_p\), the hidden number problem is to find \(x\) given \(m\) pairs of integers \((t_i, a_i)\) for \(i = 1, 2, \dots, m\) such that

\[\beta_i - t_i \alpha + a_i \equiv 0 \mod p\]

where \(\beta_i\) are unknown small integers: \(|\beta_i| < B\) with \(B\) a bound on the size of the \(\beta_i\).

This problem can be solved using the LLL algorithm on the basis

\[ \left(\begin{array}{ccccc} p & & & & \\ & p & & & \\ & & \ddots & & \\ & & & p & \\ t_1 & t_2 & \dots & t_m & B/p \\ a_1 & a_2 & \dots & a_m & & B/p \end{array}\right) \]

which will have \((\beta_1, \beta_2, \dots, \beta_m, \alpha B / p, -B)\) as a short vector.

Extended HNP

The Extended Hidden Number Problem is, as its name suggests, an extension of the original Hidden Number Problem. It can be used to perform cryptanalysis of signature schemes given partially revealed secret information.

Resources

GitHub

Last updated on May 10, 2026

DLP Mod Arithmetic