Paper 2021/924

On Removing Rejection Conditions in Practical Lattice-Based Signatures

Rouzbeh Behnia, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2021
Keywords
Lattice SignatureRejection SamplingReconciliationFiat Shamir
Contact author(s)
rouzbeh behnia @ gmail com
chenyilei ra @ gmail com
daniel masny @ rub de
History
2021-07-09: received
Short URL
https://ia.cr/2021/924
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/924,
      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{https://eprint.iacr.org/2021/924}},
      url = {https://eprint.iacr.org/2021/924}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.