Learning With Errors and Ring Learning With Errors

Our existing public key methods are at great danger of being cracked by quantum computers. One of the methods that is proposed as a hard problem for quantum computers of Learning With Errors (LWE).

Introduction

LWE is a quantum robust method of cryptography. Initially we create a secret key value (s) and another value (e). Next we select a number of values (A[]) and calculate B[] = A[] x s + e. The values of A[] and B[] become our public key. If s is a single value, A and B are one dimensional matrices. If we select s to be a one-dimensional matrix, A will be a two-dimensional matrix, and B will be a one-dimensional matrix.

Learning with errors is a method defined by Oded Regev in 2005 [here] and is known as LWE (Learning With Errors). It involves the difficulty of finding the values which solve:

B=A×s+e

where you know A and B. The value of s becomes the secret values (or the secret key), and A and B can become the public key. Slides: [here]