Lattice-based Cryptography: Lattices

Posted on

I am currently doing an internship at UPC Barcelona on the topic of lattice-based cryptography, ZK proofs, voting protocols. The goal of this series is to gather my thoughts under one place to organize ideas. It is not really meant to be read by some audience, so chances are if you stumble on this it won’t be very good learning material.

This post recalls usual definitions when working with lattices and ZK-proofs. References are the following:

Prerequisites

We denote matrices with upper-case letters, vectors with lower-case letters. Sampling an element \(x\) from some distribution \(\mathcal D\) is denoted as \(x \xleftarrow{\$} \mathcal{D}\). Sampling an element \(x\) uniformly in set \(A\) is also denoted \(x \xleftarrow{\$} A\) or \(x \xleftarrow{\$} \mathcal{U}(A)\).

We denote the quotient ring of integers modulo \(q\) as \(\ZZ_q = \ZZ / q\ZZ\).

Lattices

An integer lattice is an additive subgroup of \(\ZZ^n\). Every lattice \(Λ\) is generated by a basis \(B = \{b_1, \dots, b_m\} \in \ZZ^{k \times m}\) of linearly independent vectors. \(m\) is called the dimension of the lattice. When \(m = n\), the lattice is called a full-rank lattice.

We define the minimum distance of a lattice \(L\) as the length of the shortest nonzero lattice vector:

\[\lambda_1(L) := \min_{v \in L \setminus \{0\}}{\lVert v \rVert}\]

Likewise, we can define the \(i\)-th successive minimum \(\lambda_i(L)\) as the smallest \(r\) such that \(L\) has \(i\) linearly independent vectors of norm at most \(r\).

For any matrix \(A \in \ZZ^{n \times m}\), we can define the orthogonal lattice:

\[\Lambda^\bot = \mathcal{L}^\bot(A) = \{ x \in \ZZ^m \mid Ax = 0 \mod q \}\]

Ring Lattices

Polynomial Rings

Consider the polynomial ring \(\mathcal{R}_q = \ZZ_q /\langle x^n + 1\rangle\) for some prime \(q\). Elements in the ring are polynomials of degree at most \(n - 1\), with coefficients in \([-\frac{q - 1}{2}, \frac{q - 1}{2}]\). All operations on ring elements are done module \(q\).

For any \(K \mid n\), we construct a subring of \(\mathcal{R}_q\) as \(\mathcal{R}_q^{(K)} = \{a \in \mathcal{R}_q \mid a = \sum_{i = 0}^{K - 1}{a_i x^{in/K}}\}\)

Lattices over Rings

We can define lattices over \(\mathcal{R}_q\) similarly to lattices over \(\mathbb{Z}_q\). Given \(A^\intercal \in \mathcal{R}_q^m\), we can construct the \(m\)-dimensional lattice \(\mathcal{L}^\bot(A)\) as

\[\Lambda^\bot = \{V \in (\mathbb{Z}[x]/\langle x^n + 1\rangle)^m \mid AV = 0\mod q\} \subseteq \mathcal{R}_q^m\]

Now if we map a polynomial to the vector of its coefficients, \(\Lambda^\bot\) can be seen as a \(nm\)-dimensional integer lattice over \(\mathbb{Z}\).

Computational Problems

Shortest Vector Problem (SVP)

Given an arbitrary basis \(V\) of some lattice \(L = L(B)\), find \(v \in L\) such that \(\lVert v \rVert = \lambda_1(L)\).

Short Integer Solution (\(SIS_\beta\))

Given a random matrix \(A\in \mathbb{Z}_q^{n \times m}\), find a nonzero integer vector \(z \in \mathbb{Z}^m\) such that \(\lVert z \rVert \leq \beta\) and

\[Az = \sum_i{a_i \cdot z_i} = 0 \in \mathbb{Z}_q^n\]

Dual Regev Encryption Scheme

  • KeyGen:

    Fix random matrix \(A \in \ZZ^{n \times m}\) for \(m \geq 2n\log q\). Let \(f_A : e \mapsto Ae \mod q\). Choose an error vector \(e \xleftarrow{\$} D_{\ZZ^m, r}\), and compute its syndrome \(u = f_A(e)\).

    Secret key: \(e\).
    Public key: \((A, u)\).

  • Encrypt:

    To encrypt a bit \(b \in \{0, 1\}\), pick \(s \in \ZZ_q^n\), \(x \leftarrow \mathcal{X}\), \(y \xleftarrow{\$} \mathcal{X}^m\), and output:

    \[\begin{aligned} \begin{aligned} C &= (c_0, c_1) \\ &= (u^\intercal\cdot s + x + b \cdot \left\lfloor \frac{q}{2} \right\rfloor, A^\intercal \cdot s + y) \end{aligned} \end{aligned}\]

  • Decript:

    To decrypt \(C = (c_0, c_1)\):

    • Compute \(b = c_0 - e^\intercal \cdot c_1 \in \ZZ^q\)
    • If \(b \mod q\) is closer to \(\left\lfloor \frac{1}{2} \right\rfloor\) than to \(0\), output \(1\), else output \(0\).