Babai failure and precision issues

[hbennett]

The attached file (which is really a Python file, but can't be attached as one) gives an example of Babai's algorithm in fpylll failing when it shouldn't due presumably to precision issues.

issue.txt

[joerowell]

To make it easier:

import numpy as np
from fpylll import FPLLL, LLL, GSO, IntegerMatrix
from math import ceil, sqrt

# Global set-up.
FPLLL.set_random_seed(1337)
n = 10

# Just to emphasize that it doesn't help.
FPLLL.float_type="mpfr"
FPLLL.set_precision(1000)

# Set up basis and Gram-Schmidt basis.
B = IntegerMatrix(n, n + 1)
B.randomize("intrel", bits=100)

# Set up target.
x = [1, 0, 0, 1, 0, 0, 1, 0, 0, 0]
v_opt = B.multiply_left(x)
s = v_opt[0] # s = <a, x>, where a is the vector of knapsack values.
t = [s] + (n * [0])

# Reduce basis. 
LLL.reduction(B, delta=0.75)
M = GSO.Mat(B)
M.update_gso()

# Get a coefficient vector of a close vector to t from Babai.
y = M.babai(t)
v = B.multiply_left(y)

# These are not equal.
print("t[0]:", t[0])
print("v[0]:", v[0])
print("v[0] = t[0]?", v[0] == t[0])

# Upper bound on Babai approx. factor using a 0.75-LLL-reduced basis.
gamma = ceil(sqrt((n + 1) * (2 ** n)))

# Using NumPy for linear algebra.
# Type numbers in NumPy as Python objects to avoid precision issues.
np_array_obj = lambda a: np.array(a, "object")

# Babai does not work correctly.
assert(np.linalg.norm(np_array_obj(v) - np_array_obj(t)) <= \
       gamma * np.linalg.norm(np_array_obj(v_opt) - np_array_obj(t)))

[cbouilla]

I am hit by the same problem. This other Sagemath script illustrates the problem.

import random
import fpylll

q = random_prime(n=2**256)
bound = 10
n = 10         # variables
m = 5          # linear equations

# build ISIS instance
K = GF(q)
A = matrix.random(GF(q), n, m)
x = vector(K, [random.randrange(bound) for _ in range(n)])
y = x * A

# assemble CVP instance
mu = 1
M = matrix.block(ZZ, [[mu*A, 1], [mu*q, 0]])
t = vector(ZZ, list(mu * vector(ZZ, y)) + [0 for _ in range(n)])   # CVP target
s = vector(ZZ, list(mu * vector(ZZ, y)) + list(x))                 # lattice vector we hope to find

# check that s actually belongs to the lattice
u = vector(ZZ, M.solve_left(s))
assert u*M == s

# check that the distance between s and t is small
dist = (s - t).norm().n()
assert dist < sqrt(n) * bound

# solve CVP exactly using enumeration
G = fpylll.IntegerMatrix.from_matrix(M)
fpylll.LLL.reduction(G)
cvp = fpylll.CVP.closest_vector(G, t)             # finds s in principle
assert cvp == tuple(s)

# now try again using Babai's nearest plane
H = fpylll.IntegerMatrix.from_matrix(M)
_ = fpylll.LLL.reduction(H)
S = fpylll.GSO.Mat(H)
_ = S.update_gso()
w = S.babai(t)
cvp_bis = vector(ZZ, H.multiply_left(w))          # ERRROR ! Very far away from target

# check that CVP approximation ratio is less than sqrt(4/3)**(n+m)
actual_dist = (cvp_bis - t).norm().n()            # ERROR ! astoundingly large
assert actual_dist < 1.1547**(n+m) * dist