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.
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.
Rejection sampling technology is a core tool in the design of lattice-based signatures with ‘Fiat–Shamir with Aborts’ structure, and it is related to signing efficiency and signature, size as well as security. In the rejection sampling theorem proposed by Lyubashevsky, the masking vector of rejection sampling is chosen from discrete Gaussian distribution. However, in practical designs, the masking vector is more likely to be chosen from bounded uniform distribution due to better efficiency and simpler implementation. Besides, as one of the third-round candidate signatures in the NIST postquantum cryptography standardization process, the 3rd round version of CRYSTALS-Dilithium has proposed a new method to decrease the rejection probability in order to achieve better efficiency and smaller signature size by decreasing the number of nonzero coefficients of the challenge polynomial according to the security levels. However, it is seen that small entropies in this new method may lead to higher risk of forgery attack compared with former schemes proposed in its 2nd version. Thus, in this paper, we first analyze the complexity of forgery attack for small entropies and then introduce a new method to decrease the rejection probability without loss of security including the security against forgery attack. This method is achieved by introducing a new rejection sampling theorem with tighter bound by utilizing Rényi divergence where masking vector follows uniform distribution. By observing large gaps between the security claim and actual security bound in CRYSTALS-Dilithium, we propose two series of adapted parameters for CRYSTALS-Dilithium. The first set can improve the efficiency of the signing process in CRYSTALS-Dilithium by factors of 61.7 % and 41.7 % , according to the security levels, and ensure the security against known attacks, including forgery attack. And, the second set can reduce the signature size by a factor of 14.09 % with small improvements in efficiency at the same security level.
With the advent of quantum computing, research into post-quantum cryptography has gained significant attention. This is a novel branch of cryptography that utilizes algorithms and protocols designed to withstand attacks from quantum computers. Lattice theory represents a promising area within post-quantum cryptographic research. Two early examples of lattice-based cryptosystems are the GGH and NTRU schemes. These schemes are based on the challenge of finding the closest vector in a lattice and differ primarily in the type of lattice used. The NTRUSign protocol was developed by combining the strengths of both schemes. In 2008, another approach to lattice signatures was introduced by a group of authors. It is based on the hash-and-sign paradigm, in which a signature for a message is generated using a trapdoor. A year later, V. Lyubashevsky proposed another method for constructing lattice-based signatures that utilizes the Fiat — Shamir transform. However, due to the nature of the underlying lattice structure, the algorithm for signature generation produces a correct signature only with a certain probability. This is due to the use of a rejection sampling for security purposes. This paper presents an overview of existing lattice-based signature construction approaches and cryptographic schemes that are based on these approaches. A comparative analysis was conducted on these schemes, identifying the advantages and disadvantages of each method. Based on the results, optimal conditions for the application of each approach have been determined.
The lattice-based signature schemes are promising quantum-resistant replacements for classical signature schemes based on number theoretical hard problems. An important approach to construct lattice-based signature is utilizing the Fiat-Shamir transform and rejection sampling techniques. There are two Fiat-Shamir signatures among five lattice signature schemes submitted to the post-quantum project initiated by National Institute of Standards and Technology. One of them is called Dilithium, which is based on Module-Learning-With-Errors (MLWE) problem, it features on its simple design in the signing algorithm by using uniform sampling. The Dilithium is built on the generic lattices, to make the size of public key more compact, Dilithium adopts compression technique. On the other hand, schemes using NTRU lattices outperform schemes using generic lattices in efficiency and parameter sizes. This paper devotes to designing an efficient NTRU variant of Dilithium, by combining the advantage of NTRU and uniform rejection sampling, this scheme enjoys a concise structure and gains performance improvement over other lattice-based Fiat-Shamir signature without using extra compression techniques.
This paper proposes an efficient lattice-based blind signature scheme built upon the BLISS framework. By incor porating bimodal Gaussian distributions and rejection sampling techniques, the scheme ensures secure output distributions and prevents information leakage during the signing process. It achieves blindness and one-more unforgeability with only two rounds of interaction, significantly improving efficiency compared to earlier multi-round lattice-based blind signature schemes. Performance analysis demonstrates that the scheme maintains relatively compact parameters, with a public key size of about 20KB, a private key size of 99KB, and a signature size of 120KB. These characteristics make it practical for post-quantum secure environments. Overall, the proposed scheme combines provable security, anonymity, and efficiency, and is well-suited for privacy preserving applications such as blockchain systems, electronic voting, and anonymous payments.
With the emergence of quantum computers, traditional digital signature schemes based on problems such as large integer solutions and discrete logarithms will no longer be secure, and it is urgent to find effective digital signature schemes that can resist quantum attacks. Lattice cryptography has the advantages of computational simplicity and high security. In this paper, we propose an identity-based digital signature scheme based on the rejection sampling algorithm. Unlike most schemes that use a common Gaussian distribution, this paper uses a bimodal Gaussian distribution, which improves efficiency. The identity-based signature scheme is more convenient for practical application than the traditional certificate-based signature scheme.
This work proposes a Fiat-Shamir linkable ring lattice-based signature scheme, building on Yuen et al. ‘s generic ring signature. It converts the MLWE-based Σ-protocol into a linkable ring signature through the Fiat-Shamir transformation, employing rejection sampling to avoid private key leakage. Linkability is achieved by attaching a public key structure label, avoiding complex zero-knowledge proofs and pseudorandom function calculations. Compared to other lattice-based schemes, our approach improves signature length. Security analysis under the random oracle model confirms correctness, anonymity, unforgeability, linkability, and non-slanderability.