Skip to main content

One post tagged with "lattic"

View All Tags

· 4 min read

Lattices are used as a fundamental tool for cryptanalysis of public key cryptosystems. There are hard computational problems on lattices that have been used as a building block for public key cryptosystems (e.g., the Goldreich-Goldwasser-Halevi (GGH) cryptosystem, the NTRU cryptosystem, the Ajtai-Dwork cryptosystem, and the LWE cryptosystem);

Lattice​

A lattice is a subset of the vector space Rm. We write all vectors as rows; be warned that many books and papers write lattice vectors as columns. We denote by kvk the Euclidean norm of a vector v ∈ Rm; though some statements also hold for other norms.

Definition: Let b1,...,bn{b_1 , . . . , b_n} be a linearly independent set of (row) vectors in RmR_m (m ≥ n). The lattice generated by b1,...,bn{b_1 , . . . , b_n} is the set of integer linear combinations of the bi.

L=∑i=1nlibi:li∈Z{L = \sum_{i=1}^n {l_ib_i : l_i \in \Z}}

The vectors b1, . . . , bn are called a lattice basis.The lattice rank is n and the lattice dimension is m. If n = m then L is said to be a full rank lattice.

A basis matrix B of a lattice L is an n x m matrix formed by taking the rows to be basis vectors bi{b_i}. Thus Bi,j{B_{i,j}} is the j-th entry of the row bi{b_i} and L={xB:x∈Zn}{\textcolor{aqua}{L = \lbrace xB : x ∈ Z^n \rbrace}}

By assumption the rows of a basis matrix are always linearly independent.

Lattice Reduction​

Lattices can also be used to build cryptographic protocols, whose security is based on two fundamental "hard" problems:

The Shortest Vector Problem (SVP): find the shortest non-zero vector in a lattice L. In other words, find the non-zero vector within v ∈ L such that ||v|| is minimised.

The Closest Vector Problem (CVP): Given a vector w ∈ Rm that is not in L, find the vector v ∈ L that is the closest to w, i.e. find the vector v ∈ L such that ||v - w|| is minimised.

Gauss developed his algorithm to find an optimal basis for a two-dimensional lattice given an arbitrary basis. Moreover, the output v1 of the algorithm is a shortest nonzero vector in L, and so solves the SVP.

tip

For higher dimensions, there's a basis lattice reduction algorithm called the Lenstra-Lenstra-Lov´asz (LLL) algorithm, named after Lenstra, Lenstra and Lovász. If you play CTFs regularly, you'll already know about it. The LLL algorithm runs in polynomial time. For now though, lets stay in two dimensions.You can use this algorithm using sage library python.

L = matrix(ZZ, [[1, 1,3], [1, 2,-3], [1, 3,1]])
X = L.LLL()
# X will give is the reduced matrix

Gauss's algorithm roughly works by subtracting multiples of one basis vector from the other until it's no longer possible to make them any smaller. As this works in two-dimensions, it's nice to visualise. Here's a description of the algorithm from "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman:

Algorithm for Gaussian Lattice Reduction

Loop
   (a) If ||v2|| < ||v1||, swap v1, v2
   (b) Compute m = ⌊ v1∙v2 / v1∙v1 ⌉
   (c) If m = 0, return v1, v2
   (d) v2 = v2 - m*v1
Continue Loop

Note the similarity to Euclid's GCD algorithm with the "swap" and "reduction" steps, and that we have round the float, as on a lattice we may only use integer coefficients for our basis vectors.

lattices contain hard problems which can form trapdoor functions for cryptosystems. We also find that in cryptanalysis, lattices can break cryptographic protocols which seem at first to be unrelated to lattices.

You can read more about lattices in book Book .