Reputation: 1
I'm trying to use BKZ reduction as part of the primal attack on an MLWE instance. When I run the reduction as seen below, I will receive a runtime error.
Code
def small_poly_vector(size, high=2, low=-1):
v = [R(list(np.random.randint(low, high, N))) for _ in range(size)]
if size==1:
return v[0]
return vector(v)
Q = 3329
N = 64
k = 2
eta1 = 2
eta2 = 2
HALF_Q = int((Q + 1) / 2)
PR.<x> = PolynomialRing(GF(Q))
R.<z> = PR.quotient_ring(x^N + 1)
A = random_matrix(R, k, k)
s = small_poly_vector(k, eta1)
e = small_poly_vector(k, eta2)
t = A*s+e
A_t = matrix(QQ, 2*N+1, 2*N)
A_t[:N,:N] = A[0][0].matrix()
A_t[N:2*N,:N] = A[0][1].matrix()
A_t[:N,N:] = A[1][0].matrix()
A_t[N:2*N,N:] = A[1][1].matrix()
A_t[2*N] = [int(i) for i in t[0]]+[int(i) for i in t[1]]
lattice_size = 4*N+1
B = matrix(QQ, lattice_size, lattice_size)
B[:2*N,:2*N] = Q * identity_matrix(QQ, 2*N, 2*N)
B[2*N:,:2*N] = A_t
B[2*N:,2*N:] = identity_matrix(QQ, 2*N+1, 2*N+1)
B = IntegerMatrix.from_matrix([[int(entry) for entry in row] for row in B])
BKZ.reduction(B, o=BKZ.Param(block_size=20))
reduced_matrix = [[B[i, j] for j in range(B.ncols)] for i in range(B.nrows)]
shortest_vector = reduced_matrix[0]
Error Message
terminate called recursively
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
Cell In[43], line 30
27 B[Integer(2)*N:,Integer(2)*N:] = identity_matrix(QQ, Integer(2)*N+Integer(1), Integer(2)*N+Integer(1))
29 B = IntegerMatrix.from_matrix([[int(entry) for entry in row] for row in B])
---> 30 BKZ.reduction(B, o=BKZ.Param(block_size=Integer(20)))
31 reduced_matrix = [[B[i, j] for j in range(B.ncols)] for i in range(B.nrows)]
32 shortest_vector = reduced_matrix[Integer(0)]
File src/fpylll/fplll/bkz.pyx:1129, in fpylll.fplll.bkz.bkz_reduction()
RuntimeError: Aborted
When N=32, it is able to successfully execute the BKZ reduction. However, it is not working for N=64.
Upvotes: 0
Views: 40