Cryptology ePrint Archive: Report 2021/924

On Removing Rejection Conditions in Practical Lattice-Based Signatures

Rouzbeh Behnia and Yilei Chen and Daniel Masny

Abstract: 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.

Category / Keywords: public-key cryptography / Lattice Signature, Rejection Sampling, Reconciliation, Fiat Shamir

Original Publication (with minor differences): PQCrypto 2021

Date: received 7 Jul 2021

Contact author: rouzbeh behnia at gmail com, chenyilei ra at gmail com, daniel masny at rub de

Available format(s): PDF | BibTeX Citation

Version: 20210709:180021 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]