Advances in Cryptology ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8 12, 2019, Proceedings, Part III
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 [Eurocrypt 2012] 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 signature can be reduced by half from those in schemes built from exact trapdoors.
ASIACRYPT