GLWE example

glwe.sage

#GLWE PKE, q = 1423, n=2, d=2, https://eprint.iacr.org/2011/277.pdf

Z5x.<x> = GF(1423)[]
R = Z5x.quotient(x**2+1,"a")
a = R.gen()


ss = matrix([[1],[a]])
s = block_matrix([[1],[ss]])
AA = matrix([[a+1,a],[2*a,1],[2,4*a+4],[4*a+2,3*a]])

e = matrix([[1],[1+a],[a+1],[a]])

b = AA*ss+2*e

m = matrix([[a+1],[0], [0]]) # message is (1,1)
r = matrix([[a+1],[1],[1],[a]])

#print(AA)

A = block_matrix([[b,-AA]])

c = m + A.transpose() * r
mm = vector(c).dot_product(vector(s))
print(mm.lift().coefficients()) ##apply modulo 2 and result is the message