Ring Learning With Errors for Key Exchange (RLWE-KEX)

Public key and key exchange methods which use Diffie-Hellman, Elliptic Curve, RSA and El Gamal will be cracked by quantum computers. In order to overcome this we need new methods which are quantum robust. One of these methods is Learning With Errors (LWE). With RLWE we use the learning with errors (LWE) method but add polynomial rings over finite fields.

If you want to understand LWE, click [here].

Let’s say that Bob and Alice want to create a shared encryption key. In this case, Bob and Alice agree on shared values of A, n and q, and each of them generate error values (e) and secret values (s). They then calculate b based on A, and their own values of e and s. After this they exchange their values of b and calculate new values with the b values they have received and their own secret values. After this they will generate the same shared key.

In this method we perform a similar method to the Diffie Hellman method, but use Ring Learning With Errors (RLWE). With RLWE we use the coefficients of polynomials and which can be added and multiplied within a finite field (Fq) [theory] and where all the coefficients will be less than q. Initially Alice and Bob agree on a complexity value of n, and which is the highest co-efficient power to be used. They then generate q which is 2^n−1. All the polynomial…