Image for post
Image for post

Learning With Errors (LWE) and Ring LWE

The method describing LWE is defined here.

Learning With Errors (LWE) is a quantum robust method of cryptography. It is also used within homomorphic encryption. 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.

Outline

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]

Basics for LWE

To illustrate the method — and prove the results — I will use the examples defined here. The following code implements a basic LWE method:

The output of this is:

The following code implements a basic Ring LWE method:

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 operations will then be conducted with a modulus of q and where the largest coefficient value will be q−1. She then creates a_i(x) which is a set of polynomial values:

Next Alice will divide by Φ(x), which is x^n+1:

In Python this is achieved with:

Alice now generates an error polynomial (e) and a secret polynomial (s):

Alice now creates b_A which is a polynomial created from A, e_A and s_A:

In coding this is defined as:

Bob now generates his own error polynomial e′ and a secret polynomial s′:

Alice shares A with Bob, and Bob now creates b_B which is a polynomial created from A, e_B and s_B:

The code for this is:

Alice then takes Bob’s value (b_B) and multiplies by s_A and divides by xn+1:

Bob then takes Alice’s value (b_A) and multiplies by s_B and divides by xn+1:

At the end of this, Bob and Alice will have the same shared value (and thus can create a shared key based on it).

In code this is:

Conclusions

As our existing public cryptography methods are at risk, LWE looks to be a good solution in creating quantum robust cryptography.

The method describing LWE is defined here.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store