[Resource Topic] 2023/1335: Antrag: Annular NTRU Trapdoor Generation

Welcome to the resource topic for 2023/1335

Antrag: Annular NTRU Trapdoor Generation

Authors: Thomas Espitau, Thi Thu Quyen Nguyen, Chao Sun, Mehdi Tibouchi, Alexandre Wallet


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 by Falcon (by around 20 to 50 bits of
CoreSVP security depending on the parameters), and has much slower key

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.

ePrint: https://eprint.iacr.org/2023/1335

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .