Paper 2019/1029
Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures
Yilei Chen, 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
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1029,
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},
url = {https://eprint.iacr.org/2019/1029}
}
