IACR News item: 08 September 2023
Thomas Espitau, Thi Thu Quyen Nguyen, Chao Sun, Mehdi Tibouchi, Alexandre Wallet
ePrint Report
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
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.
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.
Additional news items may be found on the IACR news page.