Hello everyone! Welcome to the 2nd post of the FHE series. In the previous post, we covered the basics of lattice theory. In this one, we will discuss another important concept: Learning-With-Errors (LWE).

LWE
1. What is it?
2. Encryption with LWE
Ideal Lattices & Ring-LWE
1. Rings and Ideals
2. What is an ideal lattice?
3. Encryption with Ring-LWE
4. Verifying the Correctness
Conclusion

Learning-With-Errors (LWE)

What is it?

In cryptography, Learning-With-Errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms.

Let $\mathbb{Z}_q$ denote the ring of integers modulo $q$ and let $\mathbb{Z}_q^n$ denote the set of $n$-vectors over $\mathbb{Z}_q$. There exists a certain unknown linear function $f: \mathbb{Z}_q^n \rightarrow \mathbb{Z_q}$, and the input to the LWE problem is a sample of pairs $(x, y),$ where $x \in \mathbb{Z}_q^n$ and $y \in \mathbb{Z}_q$, so that with high probability $y = f(x)$.

It is based on the idea of representing secret information as a set of vector equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it.

The concept of Learning-With-Errors (LWE) introduces a computational problem where solving linear equations becomes infeasible due to the addition of noise. Specifically, LWE is based on the premise that given a set of linear equations defined over a finite field, it is computationally hard to find the solution when each equation is perturbed by a small, random error. This principle leverages the difficulty in distinguishing between random noise and structured data, laying the groundwork for cryptographic schemes that are secure against quantum attacks. The noise component is essential, as it obscures the relationship between the input vectors and their corresponding outputs, making it challenging to reverse-engineer the secret linear function.

Encryption with LWE

In the context of LWE-based encryption, the security model revolves around the difficulty of solving the LWE problem. The encryption scheme is constructed around a public and a private key, where the public key is derived from the private key with the addition of noise. This ensures that, while encryption can be performed by anyone possessing the public key, decryption is feasible only with the knowledge of the private key. The essence of this encryption lies in its ability to mask the message with a layer of computational complexity that is impractical to breach without the private key, thus ensuring confidentiality.

Private Key:$s \leftarrow \mathbb{Z}_q^n$.

Public Key:$(A, b \in \mathbb{Z}_q^N)$ where

$$A = (a_1, a_2, ..., a_N) \leftarrow \mathbb{Z}_q^{n \times N}$$

and

$$b = s \cdot A + \epsilon$$

where $\epsilon$ is a randomly chosen $N$-vector.

Encryption: To encrypt a message $m \in \{ 0, 1 \}$,

$$Enc(0) = (\mathbf{c}_1, c_2) = (\sum_i \mathbf{a}_i, \sum_i b_i)$$

$$Enc(1) = (\mathbf{c}_1, c_2) = (\sum_i \mathbf{a}_i, \lfloor q/2 \rfloor + \sum_i b_i).$$

Decryption: To decrypt a given ciphertext $(\mathbf{c}_1, c_2)$,

$Dec((\mathbf{c}_1, c_2)) = 0$ if $c_2 - s \cdot \mathbf{c_1}$ is close to 0,
$Dec((\mathbf{c}_1, c_2)) = 1$ if $c_2 - s \cdot \mathbf{c_1}$ is close to $\lfloor q/2 \rfloor$.

Ideal Lattices & Ring-LWE

Ideal lattices form the backbone of Ring-LWE, a variant of the LWE problem that operates within the structure of polynomial rings. This adaptation provides a more efficient framework for cryptographic applications by leveraging the algebraic properties of rings (we're about to discuss). Ideal lattices are characterized by their basis, derived from ideals in polynomial rings, which enables the construction of cryptographic schemes that are both secure and efficient. The introduction of Ring-LWE marks a significant advancement in cryptographic techniques, offering a practical approach to securing information in the face of evolving computational capabilities.

Rings and Ideals

Rings

A ring is a set $R$ equipped with two binary operations $+$ and $\cdot$ satisfying the following sets of axioms:

$R$ is an abelian group under addition:

$(a + b) + c = a + (b + c)\ \forall a, b, c \in R.$

$a + b = b + a \ \forall a, b \in R.$

$\exists 0 \in R$ such that $a + 0 = 0 + a = a \ \forall a \in R.$

$\forall a \in R \ \exists -a$ such that $a + (-a) = 0.$

$R$ is a monoid under multiplication:

$(a \cdot b) \cdot c = a \cdot (b \cdot c) \ \forall a,b,c \in R.$

$\exists1 \in R$ such that $a \cdot 1 = 1 \cdot a = a \ \forall a \in R.$

Multiplication is distributive w.r.t. addition:

$a \cdot (b + c) = (a \cdot b) + (a \cdot c) \ \forall a, b, c \in R.$

$(b + c) \cdot a = (b \cdot a) + (c \cdot a) \ \forall a, b, c \in R.$

Rings pop up everywhere in math and computer science, particularly when you're exploring algebraic structures and how they're used. The beauty of a ring lies in its ability to stretch the usual arithmetic operations we're used to with integers and real numbers out to more complex stuff like polynomials, matrices, and functions. This flexibility is super handy in cryptography, where the characteristics of rings help create systems that are not just secure, but also run smoothly and efficiently.

Ideals

For a ring $(R, +, \cdot)$, let $(R, +)$ be its additive group. A subset $I$ is called a left ideal of $R$ if:

$(I, +)$ is a subgroup of $(R, +)$,

$\forall r \in R$ and $\forall x \in I$, $r \cdot x \in I.$

In the context of cryptography, particularly in schemes based on lattice and Ring-LWE problems, ideals play a crucial role in defining the structure of the cryptographic system. By utilizing the concept of ideals, cryptographic constructions can achieve desired properties such as homomorphism, which allows for operations on encrypted data without decryption. This property is particularly valuable in secure multi-party computation and homomorphic encryption schemes. The use of ideals in cryptography also contributes to the efficiency and security of the system, as the mathematical properties of ideals can be exploited to resist attacks, including those leveraging quantum computing advancements.

What is an ideal lattice?

An ideal lattice is an integer lattice $L(B) \subset \mathbb{Z}^n$ such that $B = \{ g \ (mod \ f): g \in I \}$ for some monic polynomial $f$ of degree $n$ and ideal $I \subset \mathbb{Z}[x]/\langle f \rangle$.

In general terms, ideal lattices are corresponding to ideals in rings of the form $\mathbb{Z}[x]/\langle f \rangle$ for some irreducible polynomial $f$ of degree $n$.

Encryption with Ring-LWE

Ring-LWE extends the foundational concepts of LWE into the context of ring theory, optimizing the efficiency of cryptographic operations. This approach involves the utilization of polynomial rings for key generation, encryption, and decryption, thereby streamlining the cryptographic process. The security of Ring-LWE is predicated on the difficulty of solving the LWE problem within the context of polynomial rings, which, like its predecessor, is believed to be resistant to quantum attacks. The process encompasses the generation of keys through the selection of elements within a specific ring, followed by the encryption and decryption of messages. This methodology effectively encapsulates messages within the complexity of the Ring-LWE problem, ensuring their confidentiality and integrity.

Public Setup

A prime $p$ and dimension $n$ and resulting Ring-LWE ring:

$$R_p := \mathbb{Z}[x]/(x^n + 1),$$

A moderately large $k \in \mathbb{Z}.$

Key-Pair Generation

Bob selects a small random element $s \in R_p$.
Bob selects a small random element $e_1 \in R_p$.
Bob defines $(a, b) \in R_p \times R_p,$ where $b = a \cdot s + e_1$.
Bob keeps $s$ as his private ket and shares $(a, b)$ as his public key.

Encryption

Alice selects a random $r \in R_p$, this is the ephemeral key.
Alice selects small random $e_2, e_3 \in R_p$.
Alice defines

$$v = a \cdot r + e_2$$

$$w = b \cdot r + e_3 + k \cdot m.$$

Alice sends the ciphertext $(v, w)$ to Bob.

Decryption

Bob computes

$$x = w - v \cdot s.$$

Bob rounds $x$ to the nearest multiple of $k$.
Bob divides the result by $k,$ reveals the message.

Verifying the Correctness

$$x = w - vs$$

$$x = br + e_3 + km - (ar + e_2)s$$

$$x = br + e_3 + km - ars - e_2s$$

$$x = ars + e_1r + e_3 + km - ars - e_2s$$

$$x = km + e_1r + e_3 - e_2s$$

As $e_1r + e_3 - e_2s$ is a fairly small element of $R_p$, rounding to the nearest multiple of $k$ (moderately large) gives $k \cdot m $ . Hence, dividing it by $k$ reveals $m.$

Conclusion

In this post, I tried to discuss the basics of LWE, Ring-LWE, and ideal lattices, trying to make these complex concepts easier to understand. In the next post, I'm excited to chat about the basics of fully homomorphic encryption.

Image Reference

(The Lord of the Rings: The Fellowship of the Ring, 2001)

Furkan's Blog