Overview

Suppose we have a single unknown

k

-dimensional vector

S

as a secret key, many publicly known

k

-dimensional vectors

A^{⟨ i ⟩}

And suppose we have a large set of the following dot products

S \cdot A^{⟨ i ⟩}

S \cdot A^{⟨ 0 ⟩} = s_{0} \cdot a_{0, 0} + s_{1} \cdot a_{0, 1} + \dots + s_{k - 1} \cdot a_{0, k - 1} = b_{0}

S \cdot A^{⟨ 1 ⟩} = s_{0} \cdot a_{1, 0} + s_{1} \cdot a_{1, 1} + \dots + s_{k - 1} \cdot a_{1, k - 1} = b_{1}

S \cdot A^{⟨ 2 ⟩} = s_{0} \cdot a_{2, 0} + s_{1} \cdot a_{2, 1} + \dots + s_{k - 1} \cdot a_{2, k - 1} = b_{2}

Suppose that all

(A^{⟨ i ⟩}, b_{i})

tuples are publicly known. An attacker only needs

k

such tuples to derive the secret vector

S

. Specifically, as there are

k

unknown variables (i.e.,

s_{0}, s_{1}, \dots, s_{k - 1}

), the attacker can solve for those

k

variables with

k

equations by using linear algebra.

However, suppose that in each equation above, we randomly add an unknown small noise

e_{i}

(i.e., error) as follows:

S \cdot A^{⟨ 0 ⟩} = s_{0} \cdot a_{0, 0} + s_{1} \cdot a_{0, 1} + \dots + s_{k - 1} \cdot a_{0, k - 1} + e_{0} \approx b_{0}

S \cdot A^{⟨ 1 ⟩} = s_{0} \cdot a_{0, 0} + s_{1} \cdot a_{1, 1} + \dots + s_{k - 1} \cdot a_{1, k - 1} + e_{1} \approx b_{1}

S \cdot A^{⟨ 2 ⟩} = s_{0} \cdot a_{0, 0} + s_{1} \cdot a_{2, 1} + \dots + s_{k - 1} \cdot a_{2, k - 1} + e_{1} \approx b_{2}

Then, even if the attacker has a sufficient number of

(A^{⟨ i ⟩}, b_{i})

tuples, it is not feasible to derive

s_{0}, s_{1}, \dots, s_{k - 1}

, because even a small noise added to each equation prevents linear-algebra-based direct derivation of the unknown variables. For each above equation, the attacker has to consider as many possibilities as the number of the possible values of

e_{i}

. For example, if there are

r

possible values of each noise

e_{i}

, the attacker’s brute-force search space of applying linear algebra to those

n

equations is:

\overset{n times}{\overset{︷}{r \times r \times r \times \dots \times r}} = r^{n}

. Thus, the number of noisy equations grows, the aggregate possibilities of

e_{i}

s grow exponentially, which means that the attacker’s cost of attack grows exponentially.

Based on this intuition, the mathematical hard problem that constitutes lattice-based cryptography is as follows:

$⟨$ Summary B-1.1 $⟩$ The LWE (Learning with Errors) and RLWE Problems

LWE Problem

Suppose we have a plaintext number $m$ to encrypt. The encryption formula is: $b = S \cdot A + Δ \cdot m + e$ . In this formula, $e$ is a small noise, and $Δ$ is a scaling factor to bit-wise separate the plaintext $m$ from the noise $e$ with enough gap when they are added up (this is needed for successful decryption, which will be explained later).

For each encryption, a random $k$ -dimensional vector $A \in ℤ_{q}^{k}$ and a small noise value $e \in ℤ_{q}$ are newly sampled from ${0, 1, \dots, q - 1}$ , where $q$ is the ciphertext domain size. On the other hand, the $k$ -dimensional secret vector $S$ is the same for all encryptions. Suppose we have an enough number of ciphertext tuples:

$(A^{⟨ 1 ⟩}, b^{⟨ 1 ⟩})$ , where $b^{⟨ 1 ⟩} = S \cdot A^{⟨ 1 ⟩} + Δ m^{⟨ 1 ⟩} + e^{⟨ 1 ⟩}$

$(A^{⟨ 2 ⟩}, b^{⟨ 2 ⟩})$ , where $b^{⟨ 2 ⟩} = S \cdot A^{⟨ 2 ⟩} + Δ m^{⟨ 2 ⟩} + e^{⟨ 2 ⟩}$

$(A^{⟨ 3 ⟩}, b^{⟨ 3 ⟩})$ , where $b^{⟨ 3 ⟩} = S \cdot A^{⟨ 3 ⟩} + Δ m^{⟨ 3 ⟩} + e^{⟨ 3 ⟩}$

$⋮$

Suppose that the attacker has a sufficiently large number of $(A^{⟨ i ⟩}, b^{⟨ i ⟩})$ tuples. Given this setup, the following hard problems constitute the defense mechanism of the LWE (Learning with Errors) cryptosystem:

Search-Hard Problem: There is no efficient algorithm for the attacker to find out the secret key vector $S$ .
Decision-Hard Problem: We create a black box system which can be configured to one of the following two modes: (1) all $b^{⟨ i ⟩}$ values are purely randomly generated; (2) all $b^{⟨ i ⟩}$ values are computed as the results of $S \cdot A^{⟨ i ⟩} + e^{⟨ i ⟩}$ based on the randomly picked known public keys $A^{⟨ i ⟩}$ , randomly picked unknown noises $e^{⟨ i ⟩}$ , and a constant unknown secret vector $S$ . Given an enough number of $(A^{⟨ i ⟩}, b^{⟨ i ⟩})$ tuples generated by this black box system, the attacker has no efficient algorithm to determine which mode this black box system is configured to.

These two problems are interchangeable.

RLWE Problem

In the case of the RLWE (Ring Learning with Errors) problem, the only difference is that $A$ , $B$ , $S$ , $m$ , and $e$ are $(n - 1)$ -degree polynomials in $ℤ_{q} [X] ∕ (x^{n} + 1)$ , and its search-hard problem is finding the unknown $n$ coefficients of the secret polynomial $S$ .

B-1.1 Overview