DI Management Home > Cryptography > A simple lattice-based encryption scheme

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 2024, NIST published a Federal Information Processing Standards Publication [FIPS 203] Module-Lattice-based Key-Encapsulation Mechanism Standard for the ML-KEM algorithm based on CRYSTALS-Kyber.

The security is related to the computational difficulty of solving certain systems of noisy linear equations, specifically the so-called Module 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 private key $sk = \mathbf{s} \leftarrow \mathbb{Z}^n_q$, a vector of $n$ random integers in the range $[0,q-1]$,

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?

Recall 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 = 500
and 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 = 7
and $\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

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 9 September 2025