Paper 2021/1486

Mitaka: a simpler, parallelizable, maskable variant of Falcon

Thomas Espitau, NTT Corporation
Pierre-Alain Fouque, IRISA, Univ Rennes 1
François Gérard, University of Luxembourg
Mélissa Rossi, ANSSI
Akira Takahashi, Aarhus University
Mehdi Tibouchi, NTT Corporation
Alexandre Wallet, IRISA, Univ Rennes 1
Yang Yu, Tsinghua University

This work describes the Mitaka signature scheme: a new hash-and-sign signature scheme over NTRU lattices which can be seen as a variant of NIST finalist Falcon. It achieves comparable efficiency but is considerably simpler, online/offline, and easier to parallelize and protect against side-channels, thus offering significant advantages from an implementation standpoint. It is also much more versatile in terms of parameter selection. We obtain this signature scheme by replacing the FFO lattice Gaussian sampler in Falcon by the ``hybrid'' sampler of Ducas and Prest, for which we carry out a detailed and corrected security analysis. In principle, such a change can result in a substantial security loss, but we show that this loss can be largely mitigated using new techniques in key generation that allow us to construct much higher quality lattice trapdoors for the hybrid sampler relatively cheaply. This new approach can also be instantiated on a wide variety of base fields, in contrast with Falcon's restriction to power-of-two cyclotomics. We also introduce a new lattice Gaussian sampler with the same quality and efficiency, but which is moreover compatible with the integral matrix Gram root technique of Ducas et al., allowing us to avoid floating point arithmetic. This makes it possible to realize the same signature scheme as Mitaka efficiently on platforms with poor support for floating 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 much lower cost than previous masking techniques for Gaussian sampling-based signature schemes, for cheap and dependable side-channel protection.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
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
2022-05-28: revised
2021-11-15: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.