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

<br>Abstract: <br><br><br>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]. <br><br>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.<br><br>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: <a href=""></a>.

Thursday, December 5, 2019 - 4:15pm to 5:15pm
Gates 358