On (n,k)-Simple Random Integer Lattices.

Random integer lattices are fundamental to lattice-based cryptography and algorithmic number theory. A new random integer lattice model, free of any restrictions on the Hermite Normal Form (HNF), was introduced by in 2016. It was also observed that the probability of such a lattice being in a simple HNF form is approximately 44%. In this paper, the gap between general random integer lattices and those in a simple HNF is bridged by introducing the concept of the (n,k)-simple random integer lattice, where the first k diagonal entries of the HNF are fixed to 1. We derive the asymptotic counting formula for such lattices and compute their density among all integer lattices. Furthermore, a generation algorithm for the (n,k)-simple random integer lattice based on rejection sampling and inverse sampling methods are proposed, with the analysis showing that it achieves O(n2) expected running time. This work provides a theoretical foundation and practical toolkit for constructing structured random lattices with controlled HNF forms.