Learning-With-Errors (LWE) and Ring-LWE (RLWE)

Modern lattice based cryptography relies on hard mathematical problems that remain secure even against quantum computers. Two foundational assumptions in this area are Learning-With-Errors (LWE) and its more efficient variant, that is, Ring-LWE (RLWE). These problems form the backbone of many encryption, signature, and homomorphic encryption schemes.

Learning-With-Error (LWE)

The LWE problem was introduced by Regev in 2005 [1].                                                        

Imagine a scenario where we have a secret key (s). We construct many linear equations related to this secret. However, unlike a standard algebra problem, we introduce a small, random error (or noise) into the result of every single equation.

The objective is to find the original secret key (s) using only the set of these noisy equations.

  • If there were no error, the system would be easy to solve.

  • The deliberate addition of this small, carefully controlled error makes the problem computationally impossible to solve, even for the most powerful conventional or quantum computers.

The security of cryptographic schemes based on LWE is derived from the proven hardness of this "noisy" linear algebra problem.

Definition:


The standard LWE problem requires working over high-dimensional vectors, leading to large key sizes and high computational cost. Because of this inefficiency, Ring-LWE is preferred as it offers the same security with much smaller keys and significantly faster operations.

Ring-Learning-With-Error


RLWE is a ring version of LWE assumption which was introduced by Lyubashevsky, Peikert and Regev in 2010 [2]. 

In RLWE, instead of working with traditional vectors and matrices over integers (like standard LWE), we use polynomials over polynomial ring R.

  • Think of secret key s and noisy equations a and b as polynomials rather than long lists of numbers (vectors).

  • The multiplication is now polynomial multiplication modulo a polynomial (i.e., convolution), which is much faster than matrix multiplication.

  • By operating in this ring structure, an RLWE sample compresses a large number of standard LWE samples into a single, compact unit. This compression is key reason RLWE achieves smaller key sizes and faster computation compared to LWE.

Definition:


We thank ...

[1] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC 2005, pages 84–93. ACM, 2005.

[2] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology - EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 1–23. Springer, 2010. 

Comments

Post a Comment

Popular posts from this blog

Elliptic Curve Cryptography (ECC) and ECDSA

Image
Elliptic Curve Cryptography (ECC) Elliptic curve (EC) was first introduced by Neal Kobiltz and Victor Miller in 1985. Elliptic curve is a non-singular curve that is operated on a finite field Zq (where q is the order of elliptic curve). EC consists of set of points that satisfies the following equation as follows.                                                                   Y 2 = X 3 + aX + b Where {X,Y,a,b} ∈ Zq, and 4a 3 + 27b 2 ≠ 0. Next, we discuss the encryption and decryption mechanism between two parties (Say α and γ ). Remark 1: Elements selected from party α is represented by capital letters whereas elements selected from party γ is represented by small letters. i) Key Generation: 1. Secret key: Each party α and γ selects secret keys S ∈ Zq and s ∈ Zq. 2. Public key: P ...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more

NP-Hardness vs Cryptographic Hardness

To understand the gap between these two terms, we divide this blog into two parts. In first part, we discuss complexity theory, and in second part, we explore cryptographical perspective.  Complexity Theory:  For a better understanding of complexity theory, we refer readers to [1] Language L : A language L is a set of strings defined over an alphabet set Σ. Class P  (polynomial time) : A language L is in P if L is decidable in polynomial time by a deterministic Turing machine. Example: Language = Reachability. Input: Graph G(V,E), and s,t ∊ V(G). Question: Does their exist a path from s to t ?  The above Language is an example of Class P  (hint: can be easily solved by BFS/DFS algorithm).  Class NP (non deterministic polynomial time) : A language L  ∊  NP  if the certificate for L can be verified by a non-deterministic Turing machine in polynomial time.   A certificate for a language L is an instance of the solution ...
Read more