Paper 2019/1029

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

Yilei Chen, Nicholas Genise, and Pratyay Mukherjee


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.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2019
Digital SignatureLattice
Contact author(s)
chenyilei ra @ gmail com
ngenise @ eng ucsd edu
pratyay85 @ gmail com
2019-09-11: received
Short URL
Creative Commons Attribution


      author = {Yilei Chen and Nicholas Genise and Pratyay Mukherjee},
      title = {Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1029},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.