Paper 2021/1486
Mitaka: a simpler, parallelizable, maskable variant of Falcon
Abstract
This work describes the Mitaka signature scheme: a new hash-and-signsignature scheme over NTRU lattices which can be seen as a variant ofNIST finalist Falcon. It achieves comparable efficiency but isconsiderably simpler, online/offline, and easier to parallelize andprotect against side-channels, thus offering significant advantages froman implementation standpoint. It is also much more versatile in terms ofparameter selection.We obtain this signature scheme by replacing the FFO lattice Gaussiansampler in Falcon by the ``hybrid'' sampler of Ducas and Prest, forwhich we carry out a detailed and corrected security analysis. Inprinciple, such a change can result in a substantial security loss, butwe show that this loss can be largely mitigated using new techniques inkey generation that allow us to construct much higher quality latticetrapdoors for the hybrid sampler relatively cheaply. This new approachcan also be instantiated on a wide variety of base fields, in contrastwith Falcon's restriction to power-of-two cyclotomics.We also introduce a new lattice Gaussian sampler with the same qualityand efficiency, but which is moreover compatible with the integral matrixGram root technique of Ducas et al., allowing us to avoid floating pointarithmetic. This makes it possible to realize the same signaturescheme as Mitaka efficiently on platforms with poor support forfloating point numbers.Finally, we describe a provably secure masking of Mitaka. More precisely,we introduce novel gadgets that allow provable masking at any order at muchlower cost than previous masking techniques for Gaussian sampling-basedsignature schemes, for cheap and dependable side-channel protection.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2022
- Keywords
- lattice-based cryptograpgy signature schemes Gaussian sampling masking
- Contact author(s)
- thomas espitau ax @hco ntt co jp
pa fouque @gmail com
francois gerard @uni lu
melissa rossi @ssi gouv fr
takahashi @cs au dk
mehdi tibouchi br @hco ntt co jp
alexandre wallet @inria fr
yu-yang @mail tsinghua edu cn - History
- 2022-05-28: revised
- 2021-11-15: received
- See all versions
- Short URL
- https://ia.cr/2021/1486
- License
CC BY
BibTeX
@misc{cryptoeprint:2021/1486, author = {Thomas Espitau and Pierre-Alain Fouque and François Gérard and Mélissa Rossi and Akira Takahashi and Mehdi Tibouchi and Alexandre Wallet and Yang Yu}, title = {Mitaka: a simpler, parallelizable, maskable variant of Falcon}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1486}, year = {2021}, url = {https://eprint.iacr.org/2021/1486}}