# A simple lattice-based encryption scheme

This page looks at a simple lattice-based public-key encryption scheme that shows the connection between scheme security and lattice problems. It is a useful introduction for people interested in understanding the basics of lattice-based cryptography. We expand on the theory with a simple example, and provide some sample Python code.

Introduction | Background | The scheme | How does this work? | Why does this work? | Discrete Gaussian distribution | Example | Download Python code | References | Rate this page | Contact us

## Introduction

This simple public key encryption (PKE) scheme encrypts a single-bit message $m \in\{0,1\}$. The scheme was introduced by Regev [Regev, 2005] and is based on the learning with errors (LWE) problem. It is a fundamental building block in several lattice-based homomorphic encryption schemes, including ML-KEM/Kyber.

It is assumed you understand matrices and vectors and operations on them carried out modulo some integer $q \gt 1$ (i.e. over $\mathbb{Z}_q$) (see Python matrix tools over Zq), and you understand the basic concepts of public key encryption (PKE): $(\mathsf{Gen}$, $\mathsf{Enc}$, $\mathsf{Dec})$. For an explanation of PKE, see chapter 10 of [KATZ].

## Background

In June 2022, as part of its
post-quantum cryptography standardization project
NIST announced it had selected the CRYSTALS-Kyber algorithm [KYBER] for general encryption.
In August 2023, NIST published a draft Federal Information Processing Standards Publication [FIPS 203]
Module-Lattice-based Key-Encapsulation Mechanism Standard for the **ML-KEM** algorithm based on CRYSTALS-Kyber.
The standard will become effective immediately upon final publication (expected April 2024).

The security is related to the computational difficulty of solving certain systems of noisy linear equations, specifically the so-calledModule Learning With Errors (MLWE) problem. At present, ML-KEM is believed to be secure even against adversaries who possess a quantum computer. [FIPS 203]

The scheme on this page is simpler than that used in Kyber. This only encrypts a single bit of information and uses a simpler matrix-based approach using a ring of integers $\mathbb{Z}_q$ based on learning with errors (LWE).

## Notation

Matrices are denoted as a boldface capital letter: $\mathbf{A}$, and vectors as boldface lowercase: $\mathbf{b}, \mathbf{r}, \mathbf{u}$. Scalars are denoted as plain values: $v, m$. When working with matrices, all vectors are considered as column vectors. The expression $\mathbf{A}\mathbf{b}$ denotes the matrix $\mathbf{A}$ multiplied by the column vector $\mathbf{b}$. The expression $\mathbf{a}^T \mathbf{b}$ is equivalent to $\mathbf{a}\cdot\mathbf{b}$, the dot product of the vectors $\mathbf{a}$ and $\mathbf{b}$, sometimes written as $\langle \mathbf{a}, \mathbf{b} \rangle$.

All scalars and elements of matrices and vectors are in $\mathbb{Z}_q$ and all computations are carried out modulo $q$.

$\mathbf{a} \leftarrow \mathbb{Z}^n_q$ means create a vector $\mathbf{a}$ of length $n$ with each element selected at random from a uniform distribution over $\mathbb{Z}_q$, the integers in the range $[0,q-1]$

$\mathbf{A} \leftarrow \mathbb{Z}^{N\times n}_q$ means create a matrix $\mathbf{A}$ of $N$ rows and $n$ columns with each element selected at random from a uniform distribution over $\mathbb{Z}_q$.

$\mathbf{e} \leftarrow \chi^N$, create a noise vector $\mathbf{e}$ of length $N$ selected from a discrete Gaussian distribution $\chi$ over $\mathbb{Z}_q$.

$\mathbf{r} \leftarrow \{0,1\}^N$, create a random binary vector $\mathbf{r}$ of length $N$.

## The scheme

### Parameters

The parameters n, q, N, $\chi$ correspond to the security parameter (vector dimension), the modulus, the number of LWE samples, and the noise distribution over $\mathbb{Z}_q$, respectively.

### Key Generation

$(pk, sk) \leftarrow \mathsf{Gen}(1^n)$

Sample a random matrix $\mathbf{A} \leftarrow \mathbb{Z}^{N\times n}_q$, (an $N \times n$ matrix of integers selected randomly from $\mathbb{Z}_q$) and a random noise vector $\mathbf{e} \leftarrow \chi^N$.

Compute \[ \mathbf{b} = \mathbf{As} + \mathbf{e} \]

The public key $pk$ is the pair $(\mathbf{A}, \mathbf{b})$.

Output the key pair $(pk, sk) = ((\mathbf{A}, \mathbf{b}),\, \mathbf{s})$. $sk$ is to be kept private by its owner.

### Encryption

$c \leftarrow \mathsf{Enc}_{pk}(m)$

Encrypt the single-bit message $m \in \{0,1\}$ as follows

Sample a random binary vector $\mathbf{r} \leftarrow \{0,1\}^N$

Compute \[ \mathbf{u} = \mathbf{A}^T\mathbf{r}, \quad v = \mathbf{b}^T\mathbf{r} + \left\lfloor \frac{q}{2}\right\rfloor m \]

Output the ciphertext $c = (\mathbf{u}, v)$.

### Decryption

$m := \mathsf{Dec}_{sk}(c)$

Decrypt the ciphertext $c =(\mathbf{u}, v)$ using the secret key $\mathbf{s}$ as follows

\[ v' = \mathbf{s}^T \mathbf{u} \\ d = v - v' \] \[ m = \left\lceil \frac{2d}{q} \right\rfloor \bmod 2 \]

where $\left\lceil x \right\rfloor$ denotes rounding $x$ to the nearest integer with ties being rounded up (note $x$ is *not* reduced modulo $q$).

Output the message $m$. (There is no detection of failure $\perp$)

## How does this work?

Remember the rules for transposed matrices \[ (AB)^T = B^T A^T ,\quad (A + B)^T = A^T + B^T \]

We have \[ \mathbf{b} = \mathbf{As} + \mathbf{e}, \quad \mathbf{u} = \mathbf{A}^T \mathbf{r} \\ v = \mathbf{b}^T\mathbf{r} + \left\lfloor \frac{q}{2}\right\rfloor m , \;\text{ and } v' = \mathbf{s}^T \mathbf{u} \]

Hence \[ \begin{align*} d &= v - v' = \mathbf{b}^T\mathbf{r} + \left\lfloor \frac{q}{2}\right\rfloor m - \mathbf{s}^T \mathbf{u} \\ &= ( \mathbf{s}^T \mathbf{A}^T + \mathbf{e}^T)\, \mathbf{r} + \left\lfloor \frac{q}{2}\right\rfloor m - \mathbf{s}^T \mathbf{A}^T \mathbf{r} \\ &= \mathbf{e}^T \mathbf{r} + \left\lfloor \frac{q}{2}\right\rfloor m \end{align*} \]

Now $\mathbf{e}$ is sampled from a discrete Gaussian distribution with width $\sigma$ and so $|\mathbf{e}^T \mathbf{r}|$ is guaranteed to be less than $\lfloor \frac{q}{2} \rfloor / 2$ with overwhelming odds (provided that $ \sigma \ll q /4$). So, working modulo $q$, we would expect $\mathbf{e}^T \mathbf{r}$ to be in the range $\big[ 0, \big\lfloor\frac{q}{4}\big\rfloor \big)$ or $\big( \big\lfloor\frac{3q}{4}\big\rfloor, q \big)$

Hence \[ \frac{2d}{q} \in \left\{ \begin{array}{l} \left[0, \frac{1}{2} \right) \cup \left[1\frac{1}{2}, 2\right) \text{ if } m = 0 \\ \left[\frac{1}{2}, 1\frac{1}{2}\right) \text{ if } m = 1 \end{array} \right. \] If you round these fractions and then reduce modulo 2, you get the required result either $m = 0$ or $m=1$.

## Why does this work?

If the public key was simply $(\mathbf{A}, \mathbf{b} = \mathbf{As})$ without the error (noise) vector $\mathbf{e}$, then anyone can find the secret key $\mathbf{s}$ by solving the linear equation $\mathbf{As} = \mathbf{b}$ using Gaussian elimination. It is the presence of the noise vector $\mathbf{e}$ that makes the recovery of $\mathbf{s}$ difficult. The problem of recovering $\mathbf{s}$ from noisy equations $\mathbf{As} + \mathbf{e} = \mathbf{b}$ is known as Learning With Errors (LWE). There is no known efficient algorithm to solve this at present, even using a quantum computer (if one existed).

In fact, if an efficient polynomial algorithm existed to solve this noisy linear equation problem, then it can be shown that the hardest known problems in lattice theory [Lattice Problem] - the shortest vector problem (GapSVP) and the shortest independent vectors problem (SIVP) - can also be solved, and these are known "hard" problems.

Furthermore, it can also be shown that if an algorithm exists to distinguish between a ciphertext $c$ containing the message $m=0$ and a ciphertext containing $m=1$, then the GapSVP and SIVP problems can also be solved.

## Discrete Gaussian distribution

For more information on selecting random integers from a discrete Gaussian distribution, see our page Discrete Gaussian distribution.

## Example

[Li et al, 2022 p.9] give an example of this scheme using Sage (they use a more complicated method using partitioned matrices, but the end result is the same). They use the parameters:

q = 655360001 n = 1000 N = 500and the $\chi$ distribution is selected using

`DiscreteGaussianDistributionIntegerSampler`

provided in [SAGE-REF]
using $\sigma=1.0$.
Surprisingly, the scheme works with quite small parameters (obviously not in a secure manner, but it makes it easier to understand the calculations). In our example calculations below we use

q = 31 n = 4 N = 7and $\chi$ is the discrete Gaussian distribution with $\sigma = 1.0$.

### KeyGen

In our "toy" example, we sample \[ \mathbf{s} \leftarrow \mathbb{Z}^n_q = \begin{bmatrix} 23 & 8 & 25 & 6 \\ \end{bmatrix}^T \] and $\mathbf{A}$ and $\mathbf{e}$ as follows: \[ \mathbf{A} \leftarrow \mathbb{Z}^{N\times n}_q = \begin{bmatrix} 23 & 30 & 26 & 21 \\ 17 & 9 & 24 & 13 \\ 11 & 19 & 26 & 19 \\ 22 & 7 & 29 & 6 \\ 21 & 21 & 13 & 14 \\ 14 & 28 & 20 & 26 \\ 16 & 26 & 21 & 20 \end{bmatrix} \quad \mathbf{e} \leftarrow \chi^N = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 30 \\ 1 \end{bmatrix} \]We compute (all modulo $q$) \[ \mathbf{b} = \mathbf{A} \mathbf{s} + \mathbf{e} = \begin{bmatrix} 23 & 30 & 26 & 21 \\ 17 & 9 & 24 & 13 \\ 11 & 19 & 26 & 19 \\ 22 & 7 & 29 & 6 \\ 21 & 21 & 13 & 14 \\ 14 & 28 & 20 & 26 \\ 16 & 26 & 21 & 20 \end{bmatrix} \begin{bmatrix} 23 \\ 8 \\ 25 \\ 6 \end{bmatrix} + \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 30 \\ 1 \end{bmatrix} = \begin{bmatrix} 27 \\ 25 \\ 22 \\ 21 \\ 7 \\ 23 \\ 13 \end{bmatrix} \]

### Encryption

To encrypt the message $m = 1$ we sample a random binary vector $\mathbf{r} = [0, 1, 0, 1, 1, 0, 0]^T$ and compute \[ \mathbf{u} = \mathbf{A}^T\mathbf{r} = \begin{bmatrix} 23 & 17 & 11 & 22 & 21 & 14 & 16 \\ 30 & 9 & 19 & 7 & 21 & 28 & 26 \\ 26 & 24 & 26 & 29 & 13 & 20 & 21 \\ 21 & 13 & 19 & 6 & 14 & 26 & 20 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 29 \\ 6 \\ 4 \\ 2 \end{bmatrix} \] and \[ v = \mathbf{b}^T\mathbf{r} + \left\lfloor \frac{q}{2}\right\rfloor m \\ =\begin{bmatrix} 27 & 25 & 22 & 21 & 7 & 23 & 13 \\ \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} + \left\lfloor \frac{31}{2}\right\rfloor \times 1 \\ = 22 + 15 \equiv 6 \pmod{31} \] The ciphertext is $(\mathbf{u}, v) = \big([29,6,4,2]^T, 6\big)$

### Decryption

Compute \[ v' = \mathbf{s}^T\mathbf{u} =\begin{bmatrix} 23 & 8 & 25 & 6 \\ \end{bmatrix} \begin{bmatrix} 29 \\ 6 \\ 4 \\ 2 \end{bmatrix} = 21 \\ d = v - v' = 6 - 21 \equiv 16 \pmod{31} \\ \left\lceil \frac{2d}{q} \right\rfloor = \left\lceil \frac{2\times 16}{31} \right\rfloor = 1 \] Hence \[ m = \left\lceil \frac{2d}{q} \right\rfloor \bmod{2} = 1, \quad\text{ as expected} \]

## Download Python code

lattice-lwe-simple.py | Example simple LWE PKE scheme | |

lattice-lwe-simple-fixed.py | Example simple LWE PKE scheme with fixed values as shown above | |

discrete_gaussian_zq.py | See Discrete Gaussian distribution | |

matrixzq.py | See Python matrix tools over Zq | |

lattice-lwe-simple.zip | All of the above zipped |

Example: generate a key pair (pk, sk).

import matrixzq as mq import discrete_gaussian_zq as dgz # Parameters q = 31 # Modulus n = 4 # Security parameter N = 7 # Sample size mq.set_modulus(q) # Gen: (pk, sk) <-- Gen(1^n) # ------------------------------------------- print("Gen:") # Private key: sample a private key s <-- Z_q^n s = mq.new_vector([mq.random_element() for i in range(n)]) print("s =", mq.sprint_vector(s)) # Public key: sample a random matrix A <-- Z_q^{N x n} A = mq.new_matrix([[mq.random_element() for i in range(n)] for j in range(N)]) print(f"A:\n{mq.sprint_matrix(A)}") # Random noise vector e <-- \chi^N dgi = dgz.Dgi(q, sigma=1.0) e = mq.new_vector([dgi.D() for x in range(N)]) print("e =", mq.sprint_vector(e)) # Compute b = As + e b = mq.multiply(A, s) b = mq.add(b, e) print("b =", mq.sprint_vector(b)) # (pk, sk) = ((A, b), s)

Gen: s = [30, 5, 12, 10] A: [24, 2, 12, 15] [20, 20, 15, 28] [13, 4, 15, 10] [3, 7, 18, 5] [1, 7, 27, 16] [22, 0, 1, 17] [9, 22, 2, 28] e = [29, 0, 0, 30, 30, 0, 30] b = [30, 13, 8, 18, 21, 5, 1]

## References

**[FIPS203]**National Institute of Standards and Technology, Module-Lattice-based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication (FIPS) NIST FIPS 203 ipd, August 2023. (https://doi.org/10.6028/NIST.FIPS.203.ipd).**[KATZ]**Katz, J. and Y. Lindell. Introduction to modern cryptography: principles and protocols. Chapman & Hall/CRC, 2008.**[KYBER]**Peter Schwabe. CRYSTALS Cryptographic Suite for Algebraic Lattices, last updated 23 December 2020, (https://pq-crystals.org/kyber/)**[Lattice Problem]**Wikipedia. Lattice Problem. Retrieved 2024-02-11 from https://en.wikipedia.org/wiki/Lattice_problem.**[Li et al, 2022]**Yang Li and Kee Siong Ng and Michael Purcell, A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption, arXiv:2208.08125 [cs.CR], September 2022. (https://doi.org/10.48550/arXiv.2208.08125).**[Regev, 2005]**O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In H. N. Gabow and R. Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 84–93. ACM, 2005. Republished with additions as [Regev, 2009] and [Regev, 2024].**[Regev, 2009]**O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009. (https://cims.nyu.edu/~regev/papers/qcrypto.pdf).**[Regev, 2024]**O. Regev. On lattices, learning with errors, random linear codes, and cryptography. arXiv:2401.03703v1 [cs.CR] 8 Jan 2024, (https://arxiv.org/pdf/2401.03703.pdf).**[SAGE-REF]**Sage 10.2 Reference Manual, Discrete Gaussian Samplers over the Integers, DiscreteGaussianDistributionIntegerSampler. Accessed 2024-02-13.

## Rate this page

## Contact us

To comment on this page or to contact us, please send us a message.

*This page first published 25 February 2024. Last updated 26 February 2024*