9  Lattice-based cryptography

An is defined as a set of points of the form \(\sum_i k_iv_i\) for a fixed set of vectors \(v_i\) and arbitrary integer coefficients \(k_i\). Lattice problems (e.g. the shortest vector problem) are presumed to be hard for quantum computers. A common computational problem is (LWE), which is related to various lattice problems.

As a warmup problem, consider two communicating agents, Alice and Bob, and fix some prime \(q\). Alice then proceeds as follows:

Given \(A\) and \(b\), can Bob obtain \(s\)? Define the \(m\times n\) matrix \(A\) whose rows are the \(a^{(i)}\). Since \(b\) and \(s\) are vectors with \(m\) and \(n\) components respectively, we can rewrite Alice’s procedure as calculating \(b:= As \bmod q\). The problem above can then be solved by Gaussian elimination if \(m \gg n\) and if \(q\) is prime, so \(s\) does not stay secret.

Instead, we will study a noisy variation of it. Now, for each message that Alice sends to Bob, we will add a number \(e^{(i)}\leftarrow\chi\), where \(\chi\) is some distribution on \(\mathbb{Z}_q\) that returns small numbers. Alice’s procedure has become \(As + e = b \mod q\). Thus Bob needs to solve this equation for \(s\) knowing only \(A\) and \(b\) (not \(e\)). Gaussian elimination cannot solve this problem. This problem is believed to be hard even for quantum computers (for suitable choices of \(n\), \(m\), \(\chi\)).

We will define several variants of the LWE problem:

Definition 9.1 (Computational-LWE or Search-LWE)  

We call search-LWE (\(t, \epsilon\))-hard if for all \(t\)-timeadversary \(A\): \[\Pr[s'=s: s\leftarrow A(n,m,q,\chi,A,b)]\leq\epsilon \]

Definition 9.2 (Decisional-LWE or LWE)  

  • Parameters: \(n\), \(m\), \(q>0\) integers. \(\chi\) a probability distribution on \(\mathbb{Z}_q\)

  • Game 1: pick \(A \xleftarrow{\$}\mathbb{Z}_q^{m\times n}\), \(s\xleftarrow{\$}\mathbb{Z}_q^n\), \(e \leftarrow \chi^m\), and compute \(b := As+e \bmod q\)

  • Game 2: pick \(A \xleftarrow{\$}\mathbb{Z}_q^{m\times n}\), \(b\xleftarrow{\$}\mathbb{Z}_q^m\)

Given \(A\), \(b\), guess which option was chosen.

We call decisional-LWE (\(t, \epsilon\))-hard if for all \(t\)-timeadversary \(A\): \[\begin{equation} \begin{split} | & \Pr[b'=1: s\leftarrow A(n,m,q,\chi,A,b)\textrm{ in Game 1}] \\ - & \Pr[b'=1: s\leftarrow A(n,m,q,\chi,A,b)\textrm{ in Game 2}]| \leq\epsilon \\ \end{split} \end{equation}\]

Note that both definitions are parametrized by an arbitrary distribution \(\chi\). Intuitively, this should be a distribution of “small” numbers mod \(q\). Small means close to 0. That is, if we define \(|a|:=\min\{a \bmod q, q-(a \bmod q)\}\) for \(a\in\mathbb{Z}_q\), we want \(|a|\) to be small. We do not include this condition explicitly in the definition of LWE (a non-small \(\chi\) will simply be a valid but bad parameter choice).

A third variant is the following, where we also pick the secret \(s\) to consist of small values:

Definition 9.3 (Decisional small-secret LWE or ss-LWE)  

  • Parameters: \(n\), \(m\), \(q>0\) integers. \(\chi\) a probability distribution on \(\mathbb{Z}_q\)

  • Game 1: pick \(A \xleftarrow{\$}\mathbb{Z}_q^{m\times n}\), \(s\leftarrow\chi^n\), \(e \leftarrow \chi^m\), and compute \(b := As+e \bmod q\)

  • Game 2: pick \(A \xleftarrow{\$}\mathbb{Z}_q^{m\times n}\), \(b\xleftarrow{\$}\mathbb{Z}_q^m\)

Given \(A\), \(b\), guess which option was chosen.

Note: it can be shown that if LWE is hard, then ss-LWE is hard.

With those definitions, we are ready to define the Lyubashevsky-Peikert-Regev (LPR) scheme. This is a PKE scheme that encrypts single-bit messages. It is based on ss-LWE with \(n=m\) and prime \(q\).

Definition 9.4 (LPR scheme)  

KeyGen:

Enc(\(pk,m\)):

Dec(\(sk,(c_1, c_2))\)):

Correctness: assuming \(\chi\) is chosen such that \[\Pr[|r\cdot e+e''+e'\cdot s|\leq q/4]\geq1-\epsilon,\hfill(\star)\] the LPR encryption is \(\epsilon\)-correct, i.e. \(\Pr[\textrm{Dec}(sk, \textrm{Enc}(pk,m))=m:pk,sk\leftarrow\textrm{KeyGen()}]\geq\epsilon\) for all \(m\). So the precise notion of \(\chi\) being “small” is (\(\star\)).

We see this as follows: \(u = c_2-c_1\cdot s = m\lceil \frac{q}{2}\rfloor+\tilde{e}\) with \(\tilde{e}=r\cdot e+e''+e'\cdot s\), \(|\tilde{e}|\leq\frac{q}{4}\) with probability \(\geq 1-\epsilon\), and in this case \(|u|<\frac{q}{4}\) when \(m=0\) and \(|u|>\frac{q}{4}\) when \(m=1\).

If ss-LWE is hard for the parameters used in the LPR encryption, then LPR is IND-CPA secure. Since the message space for LPR consists of a single bit, we can reformulate the IND-CPA definition as follows to make it a bit simpler:

Definition 9.5 (IND-CPA for \(\mathcal{M}=\{0,1\}\)) For all \(t\)-time adversaries \(A\): \[\begin{equation} \begin{split} | & \Pr[b=1: pk,sk\leftarrow \textrm{KeyGen}, c \leftarrow\textrm{Enc}(pk, \color{red}\text{0}\color{black}), b\leftarrow A(pk, c)]-\\ & \Pr[b=1: pk,sk\leftarrow \textrm{KeyGen}, c \leftarrow\textrm{Enc}(pk, \color{red}\text{1}\color{black}), b\leftarrow A(pk, c)]|\\ & \leq\epsilon \\ \end{split} \end{equation}\]

From that, we have the following theorem:

: If ss-LWE is \((t,\delta)\) hard, then LPR is \((t', \epsilon)\)-IND-CPA secure for \(\epsilon:=4\delta\).

: The proof will proceed by defining a sequence of games (see Chapter 7 for an introduction to this proof style). Fix a \(t\)-time adversary \(\textit{Adv}\):

(Note the parameter \(m\), so we are defining four games Game \(1_0\), \(1_1\), \(2_0\), \(2_1\)). We have that for each \(m\in\{0,1\}\), \(p_m:=\Pr[b'=1:\textrm{Game }1_m]=\Pr[b'=1:\textrm{Game }2_m]\), since we are just inlining the algorithm’s definition. Moving on, we have:

If ss-LWE is \((t,\delta)\) hard, then \(\lvert\Pr[b'=1:\textrm{Game }2_m]-\Pr[b'=1:\textrm{Game }3_m]\rvert\leq\delta\). With some additional subproofs, one can show that \(\lvert\Pr[b'=1:\textrm{Game }3_m]-\Pr[b'=1:\textrm{Game }4_m]\rvert\leq\delta\). Finally, we define:

Since \(\Pr[\textrm{Game }4_m]=\Pr[\textrm{Game }5_m]\), then \(|p_m - \Pr[\textrm{Game }5_m]|\leq2\delta\), and consequently, \(|p_0-p_1|\leq4\delta\).