Paper 2023/1335

Antrag: Annular NTRU Trapdoor Generation

Thomas Espitau, PQShield SAS
Thi Thu Quyen Nguyen, IDEMIA, Normandie Univ, UNICAEN, ENSICAEN, CNRS
Chao Sun, Osaka University
Mehdi Tibouchi, NTT (Japan)
Alexandre Wallet, IRISA, Univ Rennes, Inria, CNRS

In this paper, we introduce a novel trapdoor generation technique for Prest's hybrid sampler over NTRU lattices. Prest's sampler is used in particular in the recently proposed Mitaka signature scheme (Eurocrypt 2022), a variant of the Falcon signature scheme, one of the candidates selected by NIST for standardization. Mitaka was introduced to address Falcon's main drawback, namely the fact that the lattice Gaussian sampler used in its signature generation is highly complex, difficult to implement correctly, to parallelize or protect against side-channels, and to instantiate over rings of dimension not a power of two to reach intermediate security levels. Prest's sampler is considerably simpler and solves these various issues, but when applying the same trapdoor generation approach as Falcon, the resulting signatures have far lower security in equal dimension. The Mitaka paper showed how certain randomness-recycling techniques could be used to mitigate this security loss, but the resulting scheme is still substantially less secure than Falcon (by around 20 to 50 bits of CoreSVP security depending on the parameters), and has much slower key generation. Our new trapdoor generation techniques solves all of those issues satisfactorily: it gives rise to a much simpler and faster key generation algorithm than Mitaka's (achieving similar speeds to Falcon), and is able to comfortably generate trapdoors reaching the same NIST security levels as Falcon as well. It can also be easily adapted to rings of intermediate dimensions, in order to support the same versatility as Mitaka in terms of parameter selection. All in all, this new technique combines all the advantages of both Falcon and Mitaka (and more) with none of the drawbacks.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
Post-quantum cryptographyHash-and-sign lattice-based signaturesNTRU trapdoorsDiscrete Gaussian sampling
Contact author(s)
t espitau @ gmail com
thi-thu-quyen nguyen @ inria fr
c-sun @ ist osaka-u ac jp
mehdi tibouchi @ ntt com
alexandre wallet @ inria fr
2023-10-03: last of 2 revisions
2023-09-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Espitau and Thi Thu Quyen Nguyen and Chao Sun and Mehdi Tibouchi and Alexandre Wallet},
      title = {Antrag: Annular NTRU Trapdoor Generation},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1335},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.