The Mod-NTRU Problem and Applications

          @misc{ scivideos_15657,
            doi = {},
            url = {https://simons.berkeley.edu/talks/mod-ntru-problem-and-applications},
            author = {},
            keywords = {},
            language = {en},
            title = {The Mod-NTRU Problem and Applications},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {apr},
            note = {15657 see, \url{https://scivideos.org/Simons-Institute/15657}}
          }
          

Abstract

In this talk, I will present an extension of Ducas, Lyubashesky and Prest instantiation of Gentry, Peikert and Vaikuntanathan (GPV) framework. More precisely, I will describe a larger class of trapdoored NTRU lattices that can be used to extend the practical parameter sets for some cryptographic schemes. Indeed, as shown by NIST candidates such as Kyber or Dilihtium, relying on module lattices and the relevant hard problems can allow for some meaningful trade-offs between security and efficiency. I will explain the regime of parameters that are needed to generate "almost optimal" (in an asymptotic sense) yet practical trapdoored NTRU modules. In particular, I will discuss the notion of hardness underlying this instantiation, and highlight some new results giving strong backups toward the computational and decisional hardness assumptions behind these trapdoors. On the more practical side, I will briefly compare the potency of a new signature scheme relying on these trapdoors to some of the NIST Round 2 candidates. Based on a joint work with Chitchanok Chuengsatiansup, Thomas Prest, Damien Stehlé and Keita Xagawa.