Image for post
Image for post
Photo by Chris Liverani on Unsplash

Homomorphic Encryption with Learning With Errors (LWE)

We secure data in its transit, and at its rest, but what happens in process? Well, we are perhaps moving into a world which will protect data at every point of its journey. This will be a world of homomorphic encryption.

Learning With Errors (LWE) is a quantum robust method of cryptography. Initially we create a secret value (s) and which is our private key. We then create a public key which is based on random numbers (A), and then generate another set of numbers (B) which is based on A, s and random errors e. In this case we will show how a 4-bit value can be encrypted. In this case we will convert an integer to a 4-bit value, and then cipher each of the bits. This is achieved by generating a public key, and then sampling the public key for each of the bits.

First we select a random series of values for our public key (A). For example, let’s select 20 random values from 0 to 100:

[80, 86, 19, 62, 2, 83, 25, 47, 20, 58, 45, 15, 30, 68, 4, 13, 8, 6, 42, 92]

Next we add create a list (B) and were the elements are Bi=Ais+ei(modq), and where s is a secret value, and e is a list of small random values (the error values). If we take a prime number (q) of 97, and an error array (e) of:

[3, 3, 4, 1, 3, 3, 4, 4, 1, 4, 3, 3, 2, 2, 3, 2, 4, 4, 1, 3]

we generate a list (B) of:

[15, 45, 2, 20, 13, 30, 32, 45, 4, 3, 34, 78, 55, 51, 23, 67, 44, 34, 17, 75]

The A and B list will be our public key, and s will be our secret key. We can now distribute A and B to anyone who wants to encrypt a message for us (but keep s secret). To encrypt we take samples from the A and B lists, and take a message bit (M), and then calculate two values:

Image for post
Image for post

The encrypted message is (u,v ). To decrypt, we calculate:

Image for post
Image for post

If Dec is less than q2 , the message is a zero, else it is a 1.

For homomophic encryption, we can perform a single-bit adder function by generating (u,v) for each of the bits and then performing (for the two values for bit0 - v1_0, u1_0,v2_0 and u2_0):

Image for post
Image for post

With multiple bits, we basically take our value and then convert into bits. Next we cipher each bit by taking a random sample from the public key. A sample run where we add 4 plus 1 is [here]:

------Parameters and keys-------
Value to cipher: 4 1
Public Key (A): [59, 0, 44, 8, 14, 17, 78, 34, 50, 52, 42, 70, 86, 27, 79, 94, 29, 40, 24, 4]
Public Key (B): [6, 1, 29, 42, 72, 88, 5, 76, 58, 69, 17, 60, 44, 39, 9, 83, 51, 9, 25, 23]
Errors (e): [2, 1, 3, 2, 2, 3, 3, 3, 2, 3, 1, 1, 2, 1, 2, 1, 3, 3, 2, 3]
Secret key: 5
Prime number: 97
------Sampling Process from public key-------
Bits to be ciphered: [0, 0, 1, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0, 0]
[16, 12, 7, 6, 15]
[15, 14, 4, 17, 10]
[1, 12, 18, 4, 9]
[10, 18, 3, 8, 11]
[15, 7, 17, 6, 12]
[1, 10, 6, 9, 7]
[7, 10, 14, 5, 11]
[3, 5, 16, 15, 9]
------Results -----------------
Result bit0 is 1
Result bit1 is 0
Result bit2 is 1
Result bit3 is 0

The following is an outline of the code [here]:

An outline is here:

With the increasing requirement to protect data, we will see a rise in its protection within processes.

Written by

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

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