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