April 11, 2024
Thi Thu Quyen Nguyen - IDEMIA, Université de Rennes - Irisa
This talk proposal presents Antrag, a trapdoor generation technique for Prest’s hybrid sampler over NTRU lattices which we recently introduced at Asiacrypt 2023. Prest’s sampler is used in particular in the recently proposed Mitaka signature scheme (Eurocrypt 2022), a variant of Falcon. 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 hybrid 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.
5th PQC Standardization Conference (2024) [in-person]