Lattice-based cryptography

Basic Lattice Cryptography (opens new window) by Vadim Lyubashevsky is an excellent introduction to lattice-based cryptography. Below are the notes I took while reading the first part.

Some notation first: $\lceil x \rceil$ means rounding up, $\lfloor x \rfloor$ means rounding down, $\lfloor x \rceil$ means the nearest integer,

All operations in what follows are performed in the ring $\mathbb{Z}_q$, with the usual addition and multiplication of integers modulo $q$. For a set $S$, we write $a \leftarrow S$ to mean that $a$ is chosen uniformly at random from the set $S$. For any positive integer $\beta$, we will define the set

$[\beta] = \{-\beta, ..., -1, 0, 1,...,\beta \}$

A motivating example

Let’s pretend that for positive integers $q$, $n >> m$, and $\beta << q$, the following two distributions are computationally indistinguishable:

$(\mathbf{A}, \mathbf{A}\mathbf{s}), \mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{s} \leftarrow [\beta]^m$

$(\mathbf{A}, \mathbf{u}), \mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{u} \leftarrow \mathbb{Z}_q^n$

This indistinguishability assumption is clearly false because one can use Gauss elimination to invert $\mathbf{A}$ (or an $m \times m$ submatrix of $\mathbf{A}$) and check whether there is indeed an $\mathbf{s} \in [\beta]^m$ such that $\mathbf{A}\mathbf{s} = \mathbf{u}$.

We will see later that a slightly modified version of this assumption forms the foundation of lattice-based cryptography.

We will now use this (false) assumption to construct a simple CPA-secure public key encryption scheme that is very similar to the discrete logarithm-based El Gamal encryption scheme:

$sk: \mathbf{s} \leftarrow [\beta]^m, pk: (\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{t} = \mathbf{A} \mathbf{s})$

To encrypt a message $\mu \in \mathbb{Z}_q$, the encryptor picks a random $\mathbf{r} \leftarrow [\beta]^m$ and outputs:

$(\mathbf{u}^T = \mathbf{r}^T \mathbf{A}, v = \mathbf{r}^T \mathbf{t} + \mu)$

To decrypt, one simply computes

$\mu = v - \mathbf{u}^T \mathbf{s}$

The LWE problem

The following adjustment to the assumption from the previous section is needed to make it plausibly valid and still allow us to construct a cryptosystem following the same outline. A simple version of the Learning with Errors Problem (LWE), on which a lot of lattice-based cryptography rests is given next.

Definition: For positive integers $m$, $n$, $q$, and $\beta < q$, the $LWE_{n,m,q,\beta}$ problem asks to distinguish between the following two distributions:

$(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e}), \mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{s} \leftarrow [\beta]^m, \mathbf{e} \leftarrow [\beta]^n$

$(\mathbf{A}, \mathbf{u}), \mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{u} \leftarrow \mathbb{Z}_q^n$

The crucial part that makes $LWE_{n,m,q,\beta}$ hard is the presence of the additional “error” vector $\mathbf{e}$ which makes the Gaussian elimination attack inapplicable. The problem becomes harder as $m$ and $\beta / q$ grow. The parameter $n$ is not known to have a large impact on the hardness of the problem except in extreme cases.

In the original definition of LWE, a rounded Gaussian distribution was used, but it was later shown that other distributions, such as uniform or binomial (used in Kyber), can also be used.

To account for the different distributions that one could use, we can define the LWE problem relative to the distribution of the secrets $\psi$ as:

Definition: For positive integers $m$, $n$, $q$, and $\beta < q$, the $LWE_{n,m,q,\beta}$ problem asks to distinguish between the following two distributions:

$(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e}), \mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{s} \leftarrow \psi^m, \mathbf{e} \leftarrow \psi^n$

$(\mathbf{A}, \mathbf{u}), \mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{u} \leftarrow \mathbb{Z}_q^n$

The hardness of the problem depends on the parameters $m$, $n$, $q$, and $\beta$. What’s interesting is that you can make it even too hard - having for example $n < m$ and $\beta$ large enough, then the distribution $(\mathbf{A}, \mathbf{A} \mathbf{s} + \mathbf{e})$ could be statistically close to $(\mathbf{A}, \mathbf{u})$, which would make it impossible to build an encryption scheme based on just this assumption. On the other hand, if we set $m = 1$, then the problem becomes too easy because it’s not difficult to figure out whether $\mathbf{A} \mathbf{s} + \mathbf{e}$ is close to a multiple of $\mathbf{A}$.

Also, $\mathbf{s}$ can be chosen from $\mathbb{Z}_q^m$, but it can be shown the LWE problem would be equally hard. For efficiency, $\mathbf{s}$ is usually choosen from a smaller set.

An LWE-Based Encryption Scheme

Finally, let’s fix the (broken) scheme from above. This scheme is due to Oded Regev and his famous paper from 2009.

The key generation is as follows:

$sk: \mathbf{s} \leftarrow [\beta]^m, pk: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m \times m}, \mathbf{t} = \mathbf{A} \mathbf{s} + \mathbf{e_1}), \mathbf{e_1} \in [\beta]^m$

The scheme is able to encrypt only one bit at a time, so $\mu \in \{0, 1\}$. To encrypt a message $\mu \in \mathbb{Z}_q$, the encryptor picks a random $\mathbf{r}, \mathbf{e_2} \leftarrow [\beta]^m, e_3 \leftarrow [\beta]$ and outputs:

$(\mathbf{u}^T = \mathbf{r}^T \mathbf{A} + \mathbf{e_2}^T, v = \mathbf{r}^T \mathbf{t} + e_3 + \lceil \frac{q}{2} \rfloor \mu)$

Note that $\lceil \frac{q}{2} \rfloor$ is the closest integer to $\frac{q}{2}$ (there is no computation in $\mathbb{Z}_q$ here).

To decrypt:

$v - \mathbf{u}^T \mathbf{s} = \mathbf{r}^T \mathbf{e_1} + e_3 + \lceil \frac{q}{2} \rfloor \mu - \mathbf{e_2}^T s$

The decryption is then $0$ if this value is closer to $0$ and it is $1$ if this value is closer to $\frac{q}{2}$.

Note that this would work as long as $\mathbf{r}^T \mathbf{e_1} + e_3 - \mathbf{e_2}^T s < \frac{q}{4}$. That means we need to choose parameters such that $2m\beta^2 + \beta$ is smaller than $\frac{q}{4}$.

Public key and ciphertext size trade-offs

Instead of storing the entire $\mathbf{A}$ (which would require $m^2 log(q)$ bits), we can use a cryptographic PRF and 256-bit seed $\rho$. The other part of the public key, $\mathbf{t}$, depends on the secret key and cannot be compressed in a similar way. Thus, the total size of the public key is $256 + m \cdot log(q)$ bits.

The ciphertext can be represented using $(m + 1) log(q)$ bits. Concrete secure parameter settings will require taking $m \approx 700$ and $q \approx 2^{13}$, making it somewhat inefficient for the encryption of just one plaintext bit to be so large.

There is a generalization of the LWE encryption scheme that allows for various trade-offs between the public key and ciphertext sizes. We modify the sceme above as follows.

$sk: \mathbf{S} \leftarrow [\beta]^{m \times l}, pk: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m \times m}, \mathbf{T} = \mathbf{A} \mathbf{S} + \mathbf{E_1}), \mathbf{E_1} \in [\beta]^m$

Now we can encrypt $N = kl$ bits, which we arrange in the matrix $\mathbf{M} \in \{0, 1\}^{k \times l}$. To encrypt $\mathbf{M}$, the encryptor picks a random $\mathbf{R}, \mathbf{E_2} \leftarrow [\beta]^{m \times k}, \mathbf{E_3} \leftarrow [\beta]^{k \times l}$ and outputs:

$(\mathbf{U}^T = \mathbf{R}^T \mathbf{A} + \mathbf{E_2}^T, \mathbf{V} = \mathbf{R}^T \mathbf{T} + \mathbf{E_3} + \lceil \frac{q}{2} \rfloor \mathbf{M})$

The decryption works as in the previous scheme, but we need to round up $N$ elements. We can see that by using different $k, l$, we obtain a trade-off between the public key and ciphertext sizes.

Optimizations

The ciphertext part $\mathbf{V}$ contributes $N \cdot log(q)$ bits to the total ciphertext size. Instead of the encryptor publishing all $log(q)$ bits of each coefficient of $V$ as part of the ciphertext, the encryptor can transmit only $\kappa$ bits per coefficient. This is possible but introduces a further error to the decryption equation.

We choose a set $S \subset \mathbb{Z}_q$ with $2^{\kappa}$ elements. We want for $S$ elements to be "nicely" distributed in $\mathbb{Z}_q$. For example:

$S = \{\lceil i \frac{q}{2^{\kappa}} \rfloor; 0 \leq i < 2^{\kappa} \}$

Then instead of using an element $v$ from $\mathbb{Z}_q$, we use its closest element from $S$, denoting it by $HIGH_S(v)$. We denote $LOW_S(v) = v - HIGH_S(v)$. Instead of transmitting $\mathbf{V} \in \mathbb{Z}_q^{k \times l}$ as part of the ciphertext, one could transmit $\mathbf{V}' = HIGH_S(\mathbf{V})$.

Note that there exists $\mathbf{E}'$ such that $\mathbf{V} = \mathbf{V}' + \mathbf{E}'$.

If the ciphertext $(\mathbf{U}, \mathbf{V}')$ is created in this fashion, then the decryption $\mathbf{V}' - \mathbf{U} \mathbf{S}$ produces $\mathbf{V}' - \mathbf{U}\mathbf{S} = \mathbf{R}\mathbf{E_1} + \mathbf{E_3} - \mathbf{E}' + \frac{q}{2} \mathbf{M} - \mathbf{E_2} \mathbf{S}$ where the only difference from the above is the presence of the $\mathbf{E}'$ term. However, if this term is small (and we chose $S$ such that the elements of $\mathbf{E}'$ are small), it can be considered just as an additional error, and the decryption process still works.

Modulus switching

Definition: For an element $x \in \mathbb{Z}_q$ and some positive integer $p$, we define a mapping from $\mathbb{Z}_q$ to $\mathbb{Z}_p$ as

$[x]_{q \rightarrow p} = \lceil \frac{x p}{q} \rfloor \in \mathbb{Z}_p$

We can relate the modulus switching and the compression to the set $S$ as described above as:

1. $p = 2^{\kappa}$
2. $S = \{ \lceil x \rfloor_{p \rightarrow q}; x \in \mathbb{Z}_p \}$
3. $HIGH_S(x) = \lceil \lceil x \rfloor_{q \rightarrow p} \rfloor_{p \rightarrow q}$
4. $LOW_S(x) = x - HIGH_S(x)$

It can be shown that if one first compresses an element in $\mathbb{Z}_q$ into an element in $\mathbb{Z}_p$ (where $p < q$) and then decompresses back to $\mathbb{Z}_q$, the result won’t be too far from the original element, so $LOW_S(x)$ is small. To reduced the size of the ciphertext, we use $\lceil x \rfloor_{q \rightarrow p}$ instead of $x$.

Learning with rounding

It turns out that when the compression is used, we can omit adding the error because it’s already added by the compression/decompression step. Therefore, instead of using $t = \mathbf{A}\mathbf{s} + \mathbf{e}$, we can simply use $t = \mathbf{A}\mathbf{s}$ because the probability that $HIGH_S(\mathbf{A}\mathbf{s} + \mathbf{e}) = \mathbf{A}\mathbf{s}$ is high.

The advantage of making the LWR assumption is that it allows for smaller parameters because it does not add the error $\mathbf{e}$.

Encrypting more bits per slot

The encryption scheme above packed the $N$-bit message into a matrix $M \in \{0,1\}^{k \times l}$. However, it could also be packed into a matrix $M \in \{ 0,1,...,2b-1 \}^{(\frac{k}{\sqrt b})\times(\frac{k}{\sqrt b})}$.

For decryption to work, the encryption needs to be modified to use $\frac{q}{2^b} M$ instead of $\frac{q}{2} M$. The parameters need to be adjusted such that the error is smaller than $\frac{q}{2^{b+1}}$ rather than $\frac{q}{4}$.

Non-interactive key exchange

What follows is a protocol for two parties to agree on a single bit $b_1$. To agree on a shared key of more bits, the techniques described above can be employed.

There is a public random matrix $A \in \mathbb{Z}^{m\times m}$ that is trusted by everyone to have been honestly generated. The first party chooses $s_1, e_1 \leftarrow [\beta]^m$, and the second party chooses $s_2, e_2 \leftarrow [\beta]^m$. The first party computes

$u_1^T = s_1^T A + e_1^T$

and sends it to the second party. The second party computes

$u_2 = A s_2 + e_2$

and sends it to the first party.

The first party computes

$s_1^T u_2 = s_1^T A s_2 + s_1^T e_2$

If this value is closer to $\frac{q}{2}$, it sets $b_1 = 1$. If it is closer to $0$, it sets $b_1 = 0$.

The second party computes

$u_1^T s_2 = s_1^T A s_2 + e_1^T s_2$

If this value is closer to $\frac{q}{2}$, it sets $b_2 = 1$. If it is closer to $0$, it sets $b_2 = 0$.

If the error terms are small enough, it holds $b_1 = b_2$, and the two parties agreed on a shared bit.