Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures
Pratyay Mukherjee
Abstract:
In this talk I will be introducing 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 first proposed by Gentry, Peikert and Vaikuntanathan [GPV'08].
First, I will be presenting the background of our work, by explaining the concept of trapdoors and the hash-and-sign signature construction from GPV'08 and then the relevant optimization of Micciancio-Peikert [MP'12]. Then I shall present our relaxed notion, its relation to SIS and its impact on the efficiency. I will conclude by presenting results from our implementation which shows that the sizes of the public-key and signature can be reduced by half from those in schemes built from exact trapdoors.
This is a joint work with Yilei Chen and Nicholas Genise. The paper with the same title is accepted to Asiacrypt, 2019 and is available here: https://eprint.iacr.org/2019/1029.