Xav
Xav

Reputation: 1

How do I fix runtime error when executing BKZ reduction in FPYLLL?

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

Answers (0)

Related Questions