BKZreduced

BKZreduced refers to a lattice basis that has been reduced by the Block Korkine-Zolotarev (BKZ) algorithm with a specified block size beta. BKZ is a generalization of lattice reduction methods and, for beta equal to 2, it coincides with the familiar LLL reduction. The BKZ algorithm improves a given basis by repeatedly selecting consecutive blocks of beta vectors, projecting the lattice onto the subspace spanned by the block and its complement, and solving a short vector problem within that projected lattice to update the block. Through repeated passes over all blocks, the basis becomes more reduced.

The term “BKZ-reduced” therefore describes a basis that has undergone BKZ reduction with a chosen beta and has reached a state where further BKZ_beta reductions on any block do not yield meaningful improvements under the applied stopping criteria. The block size beta is a key parameter: larger beta usually yields a higher-quality basis with shorter vectors and better orthogonality, but at substantially increased computational cost. In practice, beta values are selected to balance reduction quality with resource constraints; typical choices in lattice-based cryptanalysis range from about 20 to 60 or higher for stronger targets.

BKZ-reduced bases are central to both lattice-based cryptography and lattice-based attacks. A more reduced basis can make certain problems, such as the shortest vector problem or closest vector problem, more tractable when attempting to solve them with practical algorithms. Consequently, BKZ reduction is a standard preprocessing step in many lattice-reduction tools and cryptanalytic workflows, providing a more favorable starting point for subsequent searches or sieving methods. See also LLL, KZ reduction, BKZ algorithm, and SVP/CVP.