Paper 2021/924

On Removing Rejection Conditions in Practical Lattice-Based Signatures

Rouzbeh Behnia, Yilei Chen, and Daniel Masny


Digital signatures following the methodology of “Fiat-Shamir with Aborts”, proposed by Lyubashevsky, are capable of achieving the smallest public-key and signature sizes among all the existing lattice signature schemes based on the hardness of the Ring-SIS and Ring-LWE problems. Since its introduction, several variants and optimizations have been proposed, and two of them (i.e., Dilithium and qTESLA) entered the second round of the NIST post-quantum cryptography standardization. This method of designing signatures relies on rejection sampling during the signing process. Rejection sampling is crucial for ensuring both the correctness and security of these signature schemes. In this paper, we investigate the possibility of removing the two rejection conditions used both in Dilithium and qTESLA. First, we show that removing one of the rejection conditions is possible, and provide a variant of Lyubashevsky’s signature with comparable parameters with Dilithium and qTESLA. Second, we give evidence on the difficulty of removing the other rejection condition, by showing that two very general approaches do not yield a signature scheme with correctness or security.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.PQCrypto 2021
Lattice SignatureRejection SamplingReconciliationFiat Shamir
Contact author(s)
rouzbeh behnia @ gmail com
chenyilei ra @ gmail com
daniel masny @ rub de
2021-07-09: received
Short URL
Creative Commons Attribution


      author = {Rouzbeh Behnia and Yilei Chen and Daniel Masny},
      title = {On Removing Rejection Conditions in Practical Lattice-Based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2021/924},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.