Lyubashevsky’s lattice-based digital signature schemes: analysis of the parameters and the rejection sampling technique

Lattice-based cryptography has emerged as one of the most promising candidates for post-quantum secure systems, thanks to its solid hardness assumptions and efficiency compared to other approaches. A central challenge in this field has been the design of secure and practical digital signature schemes. Lyubashevsky’s attempt to create such scheme goes way back in 2009 with the publication of his work “Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures”, where he presents a digital signature scheme -obtained through Fiat-Shamir Transform- which rely on collision-resistant hash functions and the idea of aborting secret-leaking signatures to guarantee the security of the signature scheme itself. While conceptually innovative, the resulting scheme was not practical for deployment. The turning point came with "Lattice Signatures Without Trapdoors" (2012), where Lyubashevsky’s digital signature scheme is now based on the well-known Small Integer Solution (SIS) problem, and uses the rejection sampling technique to ensure that the signatures are statistically independent of the secret key, preventing any leakage. The abort technique introduced in “Fiat–Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures” can be viewed as an early form of rejection sampling, though it was only with "Lattice Signatures Without Trapdoors" that the method was explicitly formalized and in terms of gaussian rejection sampling. The influence of this idea has been long-lasting. The lattice-based digital signature scheme Dilithium, selected in the NIST Post-Quantum Cryptography standardization process, is explicitly based on Lyubashevsky’s rejection sampling framework. However, because gaussian sampling is difficult to implement both securely and efficiently, Dilithium adopts a simplified approach using only uniform distributions. This highlights both the power and the practical challenges of rejection sampling in lattice-based cryptography. This thesis investigates Lyubashevsky’s 2012 scheme in depth, with particular emphasis on the rejection sampling procedure: why it is required, how it guarantees independence of the signatures from the secret key, and what trade-offs it introduces. A detailed analysis of the parameters is provided, establishing the relationship between those concerning the security assumptions and those concerning the efficiency of the protocol, in particular the rejection sampling step and the size of the signature. Building on this foundation, the thesis also examines the “bimodal gaussian” idea, a refinement that further improves efficiency by modifying the sampling distribution. The impact of this approach is studied through parameter analysis and comparison with the original scheme, with additional consideration of the Ring-SIS assumption. The results of this work clarify the role of rejection sampling and parameter selection in lattice-based signature design. By analyzing both the original and refined techniques, the thesis contributes to a better understanding of how these schemes balance security and efficiency, and how the ideas pioneered by Lyubashevsky continue to shape practical post-quantum signatures.