On the construction of Barnes–Wall lattices and their application in cryptography

Journal of Computer Virology and Hacking Techniques. 2026. No. 22. Article 62.

Kuninets A., Malygina E., Leevik A. G., Melnichuk E. M.

In this work, we investigate the application of Barnes–Wall lattices in post-quantum cryptographic schemes. We survey and analyze several constructions of Barnes–Wall lattices, including subgroup chains, the generalized k-ing construction, and connections with Reed-Muller codes, highlighting their equivalence over both Z[i] and Z. Building on these structural insights, we introduce a new algorithm for efficient sampling from a discrete Gaussian distribution on BW_N lattices with N = 2^n. Our approach exploits the k-ing and squaring constructions to achieve low-variance sampling, which is particularly relevant for cryptographic applications such as digital signature schemes. We further examine the cryptographic hardness of Lattice Isomorphism Problem (LIP), showing that Barnes–Wall lattices provide inherent resistance to hull-based and other known attacks. Our results on sampling algorithms, combined with existing advances in the cryptanalysis of the LIP, indicate that Barnes–Wall lattices hold strong potential for the design of post-quantum schemes based on the LIP problem.

Keywords: lattice-based cryptography, Barnes–Wall lattice, Gaussian sampling, Lattice Isomorphism Problem