Lattices

This section was made using A Gentle Tutorial for Lattice-Based Cryptanalysis and the Cryptohack lattice section.

Lattices definition

Lattice

Given linarly independent vectors $v_1, v_2, \dots, v_n \in \mathbb{R}^m$ , the lattice generated by $b_1, b_2, \dots, b_n$ is the set of all integer linear combinations of $b_1, b_2, \dots, b_n$ :

L = \lbrace x_1b_1 + x_2b_2 + \dots + x_nb_n : x_i \in \mathbb{Z} \rbrace

Lattice based problems

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

Lattice-based problems
Finding small roots of polynomials
Knapsack problem
Hidden number problem
Extended HNP

Finding small roots of polynomials

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

Small roots problem

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 $\vert x \vert < B$ . This means solving:

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:

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

Implementation
See this python script for a quick implementation of this. If you need to be more precise, use this github repository
- small_roots.py

Subset sum problem

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

Subset sum problem

Given a set of integers $S = \lbrace s_1, s_2, \dots, s_n \rbrace$ and a target integer $t$ , find a subset $S' \subseteq S$ such that

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

Hidden number problem

Hidden number problem

Given a a prime $p$ and a secret integer $\alpha \in \mathbb{Z}_p$ , the hidden number problem is to find $x$ $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: $\vert \beta_i \vert < B$ with $B$ a bound on the size of the $\beta_i$ .

This problem can be solved using the LLL algorithm on:

\left(\begin{array}{cc} 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.

Use this python script for a quick implementation of this. If you need to be more precise, use this github repository