You are looking at a specific version 20190911:072950 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2019
Keywords
Digital SignatureLattice
Contact author(s)
chenyilei ra @ gmail com,ngenise @ eng ucsd edu,pratyay85 @ gmail com
History
2019-09-11: received
Short URL
https://ia.cr/2019/1029
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.