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
-
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},
url = {https://eprint.iacr.org/2021/924}
}
