Multi-bit public key encryption with Learning With Errors (LWE)

Prof Bill Buchanan OBE
Jun 13 · 4 min read
[80, 86, 19, 62, 2, 83, 25, 47, 20, 58, 45, 15, 30, 68, 4, 13, 8, 6, 42, 92]
[3, 3, 4, 1, 3, 3, 4, 4, 1, 4, 3, 3, 2, 2, 3, 2, 4, 4, 1, 3]
[15, 45, 2, 20, 13, 30, 32, 45, 4, 3, 34, 78, 55, 51, 23, 67, 44, 34, 17, 75]
------Parameters and keys-------
Value to cipher: 4
Public Key (A): [6, 38, 90, 83, 51, 15, 31, 40, 18, 0, 10, 89, 93, 88, 32, 52, 24, 86, 82, 92]
Public Key (B): [31, 94, 66, 28, 65, 78, 60, 10, 91, 2, 53, 61, 80, 55, 65, 67, 24, 45, 26, 73]
Errors (e): [1, 1, 4, 1, 4, 3, 2, 4, 1, 2, 3, 4, 3, 3, 2, 1, 1, 3, 4, 1]
Secret key: 5
Prime number: 97
------Sampling Process from public key-------
Bits to be ciphered: [0, 0, 1, 0, 0, 0, 0, 0]
[13, 6, 14, 9, 8]
[18, 11, 9, 6, 0]
[8, 13, 11, 3, 4]
[1, 10, 6, 13, 3]
------Calculation of u and v -----------------
u1,v1: 72 79.0
u2,v2: 14 83.0
u3,v3: 38 57.0
u4,v4: 56 96.0
------Results -----------------
Result bit0 is 0
Result bit1 is 0
Result bit2 is 1
Result bits is 0
import sys
import numpy as np
import random
import math
nvals=20B=[]
e=[]
s = 20
M = 5
q=97
def get_uv(A,B,M,q):
u=0
v=0
sample= random.sample(xrange(nvals-1), nvals/4)
print sample
for x in range(0,len(sample)):
u=u+(A[sample[x]])
v= v+B[sample[x]]
v=v+math.floor(q/2)*M
return u%q,v%q
def get_result(u,v,q):
res=(v-s*u) % q
if (res>q/2):
return 1
return 0def tobits(val):
l = [0]*(8)
l[0]=val & 0x1
l[1]=(val & 0x2)>>1
l[2]=(val & 0x4)>>2
l[3]=(val & 0x8)>>3
return l
A = random.sample(xrange(q), nvals)for x in range(0,len(A)):
e.append(random.randint(1,4))
B.append((A[x]*s+e[x])%q)
print "\n------Parameters and keys-------"
print "Value to cipher:\t",M
print "Public Key (A):\t",A
print "Public Key (B):\t",B
print "Errors (e):\t\t",e
print "Secret key:\t\t",s
print "Prime number:\t\t",q
print "\n------Sampling Process from public key-------"
bits = tobits(M)print "Bits to be ciphered:",bitsu1,v1=get_uv(A,B,bits[0],q)
u2,v2=get_uv(A,B,bits[1],q)
u3,v3=get_uv(A,B,bits[2],q)
u4,v4=get_uv(A,B,bits[3],q)
print
print "\n------Calculation of u and v -----------------"
print "u1,v1:\t\t",u1,v1
print "u2,v2:\t\t",u2,v2
print "u3,v3:\t\t",u3,v3
print "u4,v4:\t\t",u4,v4
print "\n------Results -----------------"print "Result bit0 is",get_result(u1,v1,q)
print "Result bit1 is",get_result(u2,v2,q)
print "Result bit2 is",get_result(u3,v3,q)
print "Result bits is",get_result(u4,v4,q)

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Prof at Napier. Serial innovator. Crypto Punk. 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.