Appendix: Lattice problems

A quick primer to essential notions useful in post-quantum cryptography. While this aims to be precise, it cannot and will not be exhaustive; please check out the wealth of resources available to students of cryptography1.

SIS problem

(Inhomogenous) Short Integer Solutions problem 2

Given

  • \(A \overset{R}{\leftarrow}\mathbb{Z}_q^{n\times m}\), an \((n\times m)\) matrix with random entries in \(\mathbb{Z}_q\),
  • \(b \overset{R}{\leftarrow}\mathbb{Z}_q^{m}\), an \((m \times 1)\) vector with random entries in \(\mathbb{Z}_q\),

find \(z \in\mathbb{Z}^{m}\) such that \(Az=b\pmod{q}\) and \(z\in[-B,B]^m\).


Parameters

  • If \(n>m\), no solution exists.
  • If \((2B+1)^m \gg q^n\) i.e., \(m \gg (n \log q)/\log(2B + 1)\), a solution is likely to exist.

Equivalence: SIS

Inhomogeneous indicates that \(b\neq 0\). The SIS problem with \(b=0\) is of equivalent difficulty.

LWE problem

Learning With Errors problem 3

Let

  • \(s \overset{R}{\leftarrow}\mathbb{Z}_q^{n}\) a vector with random entries in \(\mathbb{Z}_q\) – a secret;
  • \(e \overset{R}{\leftarrow} [-B,B]^m\) with \(B \ll q/2\) – a small error.

Given

  • \(A \overset{R}{\leftarrow}\mathbb{Z}_q^{m\times n}\) an \(m\times n\) matrix with random entries in \(\mathbb{Z}_q\),
  • \(b = As+e \pmod{q}\),

find \(s\).


Parameters

  • If \(e=0\) (\(B=0\)), a solution is easy to find.
  • If \(B=(q-1)/2\), a solution is impossible to find; assume \(B<q/4\).
  • If \(m\gg n\), an unique solution is likely to exist.
    • However, if also \(B\ll\sqrt{n}\), a solution can be easy to find.

Equivalence: DLWE, ss-LWE

The difficulty of solving the LWE problem has been proved equivalent to:

  • the Decisional LWE (DLWE) problem: distinguish whether a given \(\tilde{b}\) is a solution to an LWE instance or a random vector in \(\mathbb{Z}_q^{m}\);
  • the short-secret LWE (ss-LWE) problem: same as LWE but with smaller coefficients in \(s\), more precisely \(s \overset{R}{\leftarrow}[-B,B]^m\) a vector with random entries in \([-B,B]^m\) rather than \(\mathbb{Z}_q\).

References

  1. Menezes, A. J. (2024). Cryptography 101. https://cryptography101.ca/. ↩︎

  2. Ajtai, M. (1996). Generating hard instances of lattice problems (extended abstract). STOC 96, 99–108. https://doi.org/10.1145/237814.237838 ↩︎

  3. Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. STOC 96, 84–93. https://doi.org/10.1145/1060590.1060603 ↩︎

Last updated on