Computational methods in discrete mathematics

Sampling discrete Gaussian algorithm for Barnes — Wall lattices

E. M. Melnichuk


Abstract: Barnes — Wall lattices are of great interest in the context of their application in cryptography. In particular, they can be used to construct a digital signature scheme based on the lattice isomorphism problem (LIP). There is a challenge to construct an efficient discrete Gaussian sampling algorithm for these lattices. Barnes — Wall lattices can be obtained using quadratic constructions, which allows applying the $k$-ing Gaussian sampling algorithm for them for $k=2$ and $4$. We generalize this approach and present a discrete Gaussian sampling algorithm for Barnes — Wall lattices based on an $n$-fold iterative quadratic construction. This algorithm allows for an arbitrary $n\in \mathbb{N}$ to sample $x\in \text{BW}_N$, where $N=2^n$, using the lattice chain $(1+i)^n \text{BW}_1\subset (1+i)^{n-1} \text{BW}_1 \subset \ldots \subset \text{BW}_1$.

Keywords: lattice theory, Barnes — Wall lattices, Gaussian sampler for Barnes — Wall lattices.

UDC: 519.7

DOI: 10.17223/2226308X/18/59