'''
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])