Cryptology ePrint Archive: Report 2019/1029

Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures

Yilei Chen and Nicholas Genise and Pratyay Mukherjee

Abstract: We study a relaxed notion of lattice trapdoor called approximate trapdoor, which is defined to be able to invert Ajtai's one-way function approximately instead of exactly. The primary motivation of our study is to improve the efficiency of the cryptosystems built from lattice trapdoors, including the hash-and-sign signatures.

Our main contribution is to construct an approximate trapdoor by modifying the gadget trapdoor proposed by Micciancio and Peikert. In particular, we show how to use the approximate gadget trapdoor to sample short preimages from a distribution that is simulatable without knowing the trapdoor. The analysis of the distribution uses a theorem (implicitly used in past works) regarding linear transformations of discrete Gaussians on lattices.

Our approximate gadget trapdoor can be used together with the existing optimization techniques to improve the concrete performance of the hash-and-sign signature in the random oracle model under (Ring-)LWE and (Ring-)SIS assumptions. Our implementation shows that the sizes of the public-key and signature can be reduced by half from those in schemes built from exact trapdoors.

Category / Keywords: public-key cryptography / Digital Signature, Lattice

Original Publication (in the same form): IACR-ASIACRYPT-2019

Date: received 10 Sep 2019

Contact author: chenyilei ra at gmail com,ngenise@eng ucsd edu,pratyay85@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190911:072950 (All versions of this report)

Short URL: ia.cr/2019/1029


[ Cryptology ePrint archive ]