'''
	reference https://cims.nyu.edu/~regev/papers/gghattack.pdf
'''

d = 70
P = Primes()
q = 129


sk = Matrix(ZZ, d, d)

for i in range(d):
	sk[i,i] = q


print('generating random unimodular...')
random_U = random_matrix(ZZ, d, d, algorithm='unimodular')
random_U_inverse = random_U.inverse()
pk = random_U*sk

def simple_Babai(t):
	'''
	closest vector on the specific lattice generated by q*Id

	returns both the closest vector and its coefficient wrt. pk
	'''
	assert(len(t)==d)
	b = vector(ZZ, d)
	coeff = vector(ZZ, d)
	for i in range(len(t)):
		coeff[i] = round(t[i]/q)
		b[i] = coeff[i]*q

	coeff_public = pk.solve_left(b) #same as below
	#coeff_public = coeff*random_U_inverse
	return b, coeff_public

def sign(sk, mes):
	'''
	signing procedure
	'''
	b, coeff = simple_Babai(mes)
	return coeff

def verify(pk, mes, sigma):
	'''
	verification procedure
	'''
	b = sigma*pk
	for i in  range(len(mes)):
		assert(abs(mes[i]-b[i])<q/2)
	return (mes-b).norm().n()<(sqrt(d)*q/2).n()


def random_vector(d):
	'''
	messages are mapped to vectors
	'''
	t = vector(ZZ, d)
	for i in range(d):
		t[i] = ZZ.random_element(-1000*q, 1000*q)
	return t

message = random_vector(d)
sigma = sign(sk, message)
ver = verify(pk, message, sigma)