A New Lattice-Based Post-Quantum Digital Signature from Compact Rejection Sampling

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.