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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb {Z}[i]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="double-struck">Z</mi> <mo stretchy="false">[</mo> <mi>i</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathbb {Z}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">Z</mi> </math></EquationSource> </InlineEquation>. Building on these structural insights, we introduce a new algorithm for efficient sampling from a discrete Gaussian distribution on <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$BW_N$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <msub> <mi>W</mi> <mi>N</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> lattices with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$N=2^n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>. 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.

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

期刊论文
发表日期：

2026年7月16日

查看全文

Artyom Kuninets,
Anton Leevik,
Ekaterina Malygina,
Evgeniy Melnichuk,
Denis Nabokov

摘要

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 $\mathbb {Z}[i]$ $Z [i]$ and $\mathbb {Z}$ $Z$ . Building on these structural insights, we introduce a new algorithm for efficient sampling from a discrete Gaussian distribution on $BW_N$ $B W_{N}$ lattices with $N=2^n$ $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.