Exact Lattice Sampling from Non-Gaussian Distributions

Guotao Chai, Renjie Jin, Shuoqu Jian +1 more

Rongxun Yao

The Learning with Errors (LWE) problem is a fundamental hardness assumption for post-quantum lattice-based cryptography. Standard LWE schemes rely on discrete Gaussian error distributions, which incur high sampling overhead. This paper explores the feasibility of replacing the Gaussian distribution with a novel non-Gaussian alternative—the Step Distribution—within Regev’s classic LWE public-key encryption scheme. The Step Distribution partitions the error range into equal-width steps, with probabilities proportional to Gaussian weights at step midpoints. The distribution is formally defined, its asymptotic convergence to the discrete Gaussian is proved, and conditions under which the decryption error probability becomes negligible are derived. The Step Distribution offers a tunable parameter—the number of steps—that allows a trade-off between security (closeness to the Gaussian) and computational efficiency. This work provides a flexible error distribution for LWE-based cryptosystems, particularly suitable for resource-constrained environments.

Vadim Lyubashevsky, Daniel Wichs

Pingyuan Zhang, Limin Wang

Rejection samplings are the essential building blocks to design lattice-based digital signatures under the Fiat–Shamir paradigm. Up to now most of them have been built by Gaussian samplings or uniform samplings. Gaussian-based rejection sampling signatures such as the BLISS scheme have very short signature sizes but are vulnerable to timing attacks, whereas the uniform-based rejection sampling signatures such as ML-DSA are allowed to be simply implemented but have larger signature sizes. This work intends to use a new probability distribution, rather than Gaussian or uniform distributions, to build the rejection sampling in Fiat–Shamir signatures, and aims to achieve short signature sizes while avoiding the cost of Gaussian sampling. To this end, we choose centered binomial distribution as a replacement, and build a new and compact rejection sampling that has the properties of both high-precision sampling and semi-uniform operation. As an application, we combine this rejection sampling with Lyubashevsky’s signature scheme, then propose the first lattice-based Fiat–Shamir signature scheme from centered binomial distribution. The proposed scheme not only avoids Gaussian sampling, but also is very efficient in terms of the signature sizes.

Jack A. Tuszyński, M. J. Clouter, Harry Kiefte

This paper investigates the role of statistical fluctuations about the equilibrium value of the order parameter in the vicinity of a phase-transition temperature. The systems under consideration are assumed to be of finite size, but the behavior in the thermodynamic limit is also described. Our objective is to examine the simplest exactly solvable model of non-Gaussian static fluctuations for samples of finite size. To this end a Landau form is employed for the model Hamiltonian and various expansions are analyzed in order to describe first- and second-order phase transitions, field-induced transitions, and liquid-vapor critical phenomena. The approach differs from previous treatments primarily in the application of a quartic non-Gaussian model for statistical fluctuations which redresses some of the shortcomings of the standard Gaussian approximation. In particular, it is found that for finite values of V (volume) no singularities exist even at the critical temperature. The treatment is generalized by examining a class of non-Gaussian distribution functions, and particular emphasis is placed on strict adherence to the uniform convergence criterion so that general conclusions can be drawn.

Fa Yueh Wu