Skip to content

bkz.bkz_schnorr_euchner

bkz_se(basis_matrix, block_size, enum_algo)

Executes the BKZ reduction algorithm as presented in Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems by C. P. Schnorr, M. Euchner (1994).

Parameters:

Name Type Description Default
basis_matrix ndarray

A 2D NumPy array of shape (n, n) representing a lattice basis, where each column is a basis vector.

 required
block_size int

An integer that determines the width of the search window for svp-solver.

 required
enum_algo string
required 
A string key selecting the enumeration algorithm variant from `ENUM_ALGORITHMS`.
Notes
  • Our implementation uses 0-based indices (0,...,n-1) for basis and block boundaries, whereas the original Schnorr–Euchner paper uses 1-based indices (1,...,n).

Returns:

Type Description
tuple

-basis_matrix (np.ndarray): A 2D Numpy array of shape (n, n) representing a BKZ-reduced lattice basis, where each column is a basis vector.

-gs_coeff_matrix (np.ndarray): A 2D Numpy array of shape (n, n) representing the updated Gram-Schmidt coefficients.

-gs_squared_norms (np.ndarray): A 1D Numpy array of shape (n,) representing the updated squared lengths of The Gram-Schmidt vectors.
Source code in bkz/bkz_schnorr_euchner.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def bkz_se(basis_matrix, block_size, enum_algo):
	"""Executes the BKZ reduction algorithm as presented in
	*Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems*
	by C. P. Schnorr, M. Euchner (1994).

	Args:
		basis_matrix (np.ndarray):
			A 2D NumPy array of shape (n, n) representing a lattice basis, where each column is a basis vector.
		block_size (int):
			An integer that determines the width of the search window for svp-solver.
		enum_algo (string):
            A string key selecting the enumeration algorithm variant from `ENUM_ALGORITHMS`.

	Notes:
	    - Our implementation uses 0-based indices (`0,...,n-1`) for basis and block boundaries,
	    whereas the original Schnorr–Euchner paper uses 1-based indices (`1,...,n`).

	Returns:
		(tuple):
			-basis_matrix (np.ndarray):
				A 2D Numpy array of shape (n, n) representing a BKZ-reduced lattice basis,
				where each column is a basis vector.

			-gs_coeff_matrix (np.ndarray):
				A 2D Numpy array of shape (n, n) representing the updated Gram-Schmidt coefficients.

			-gs_squared_norms (np.ndarray):
				A 1D Numpy array of shape (n,) representing the updated squared lengths of The Gram-Schmidt vectors.
	"""
	svp_solver = ENUM_ALGORITHMS[enum_algo]
	m = len(basis_matrix[0]) - 1
	basis_matrix, gs_coeff_matrix, gs_squared_norms = l3fp(basis_matrix)
	z = 0
	j = -1  # Ensure that we start the first loop from j=0
	pbar = tqdm(
		total=m,
		desc="BKZ (Schnorr-Euchner) reduction loop",
		leave=False,
		ascii="-##",
		colour="yellow",
		position=1,
	)
	while z < m:
		j += 1
		k = min(j + block_size - 1, m)
		if j == m:
			j = 0
			k = block_size
		candidate_proj_len, candidate_coeff_vec = svp_solver(
			basis_matrix[:, j:k + 1], gs_squared_norms[j:k + 1], gs_coeff_matrix[:, j:k + 1]
		)
		block_end = min(k + 1, m)
		if DELTA * gs_squared_norms[j] > candidate_proj_len:
			b_new = np.dot(basis_matrix[:, j:k + 1], candidate_coeff_vec)
			injected_basis = np.insert(basis_matrix[:, :block_end + 1], j, np.transpose(b_new), axis=1)

			(
				basis_matrix[:, :block_end + 1],
				gs_coeff_matrix[:block_end + 1, :block_end + 1],
				gs_squared_norms[:block_end + 1],
			) = l3fp_deep_insert(
				injected_basis_matrix=injected_basis,
				gs_coeff_matrix=gs_coeff_matrix[:j, :j],
				gs_squared_norms=gs_squared_norms[:j],
				start_stage=j,
                Lovasz_cond_param=DELTA,
				f_c=True,
			)
			z = 0

		else:
			z += 1
			(
				basis_matrix[:, :block_end + 1],
				gs_coeff_matrix[:block_end + 1, :block_end + 1],
				gs_squared_norms[:block_end + 1],
			) = l3fp(
				basis_matrix=basis_matrix[:, :block_end + 1],
				gs_coeff_matrix=gs_coeff_matrix[: block_end, : block_end],
				gs_squared_norms=gs_squared_norms[: block_end],
				start_stage=block_end - 1,
				Lovasz_cond_param=0.99,
			)
			pbar.update(1)

	pbar.close()
	return basis_matrix, gs_coeff_matrix, gs_squared_norms