SpringerLink
Log in

Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2022 (EUROCRYPT 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13277))

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 128.39
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 168.79
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Sometimes, this is also seen as a bounded distance decoding problem, BDD, but with large enough decoding bound that there are exponentially many solutions, instead of a unique one as is typically the case in the traditional formulation of BDD.

  2. 2.

    Other techniques have been proposed that avoid Gaussian distributions, as in [30], but they tend not to be competitive.

  3. 3.

    Trivia: Mitaka is a neighborhood in Tokyo, Japan whose name means “the three falcons”. It sounded fitting considering the maskable, parallelizable nature of our scheme and its strong points compared to Falcon.

  4. 4.

    In principle, even more general number fields are possible as well, provided a good basis is known for their canonical embedding. The corresponding security analysis is cumbersome, however.

  5. 5.

    The same idea can be adapted to the offline phase by masking the zero center. This is a bit less compelling, however, as it requires more shares, and replaces centered Gaussian sampling by variable center sampling.

  6. 6.

    This is the so-called coefficient embedding.

  7. 7.

    This is the case at least for Falcon and for the hybrid sampler, as for both of them, one can compute the quality of the trapdoor given only (f, g). This is especially fast for the hybrid sampler. For the Peikert sampler, however, doing so without also obtaining (F, G) seems difficult, and is left as an open problem.

References

  1. Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) USENIX Security 2016, pp. 327–343. USENIX Association, August 2016

    Google Scholar 

  2. Barthe, G., et al.: Strong non-interference and type-directed higher-order masking. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 116–129. ACM Press, October 2016. https://doi.org/10.1145/2976749.2978427

  3. Barthe, G., et al.: Masking the GLP lattice-based signature scheme at any order. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 354–384. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_12

    Chapter  Google Scholar 

  4. Barthe, G., Belaïd, S., Espitau, T., Fouque, P.A., Rossi, M., Tibouchi, M.: GALACTICS: Gaussian sampling for lattice-based constant- time implementation of cryptographic signatures, revisited. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 2147–2164. ACM Press, November 2019. https://doi.org/10.1145/3319535.3363223

  5. Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 27th SODA, pp. 10–24. ACM-SIAM, January 2016. https://doi.org/10.1137/1.9781611974331.ch2

  6. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3

    Chapter  MATH  Google Scholar 

  7. Chuengsatiansup, C., Prest, T., Stehlé, D., Wallet, A., Xagawa, K.: ModFalcon: compact signatures based on module-NTRU lattices. In: Sun, H.M., Shieh, S.P., Gu, G., Ateniese, G. (eds.) ASIACCS 2020, pp. 853–866. ACM Press, October 2020. https://doi.org/10.1145/3320269.3384758

  8. Coron, J.-S.: Higher order masking of look-up tables. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 441–458. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_25

    Chapter  Google Scholar 

  9. Ding, J., et al.: Rainbow. Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions

  10. Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_3

    Chapter  Google Scholar 

  11. Ducas, L., Galbraith, S., Prest, T., Yu, Y.: Integral matrix gram root and lattice Gaussian sampling without floats. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 608–637. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_21

    Chapter  Google Scholar 

  12. Ducas, L., et al.: CRYSTALS-Dilithium: a lattice-based digital signature scheme. IACR TCHES 2018(1), 238–268 (2018). https://doi.org/10.13154/tches.v2018.i1.238-268. https://tches.iacr.org/index.php/TCHES/article/view/839

  13. Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 22–41. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_2

    Chapter  Google Scholar 

  14. Ducas, L., Nguyen, P.Q.: Learning a zonotope and more: cryptanalysis of NTRUSign countermeasures. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 433–450. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_27

    Chapter  Google Scholar 

  15. Ducas, L., Prest, T.: Fast Fourier orthogonalization. Cryptology ePrint Archive Report 2015/1014 (2015). https://eprint.iacr.org/2015/1014

  16. Espitau, T., et al.: MITAKA: a simpler, parallelizable, maskable variant of falcon. Cryptology ePrint Archive Report 2021/1486 (2021). https://ia.cr/2021/1486

  17. Fouque, P.-A., Kirchner, P., Tibouchi, M., Wallet, A., Yu, Y.: Key recovery from gram–schmidt norm leakage in hash-and-sign signatures over NTRU lattices. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 34–63. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_2

    Chapter  MATH  Google Scholar 

  18. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press, May 2008. https://doi.org/10.1145/1374376.1374407

  19. Gérard, F., Rossi, M.: An efficient and provable masked implementation of qTESLA. In: Belaïd, S., Güneysu, T. (eds.) CARDIS 2019. LNCS, vol. 11833, pp. 74–91. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-42068-0_5

    Chapter  Google Scholar 

  20. Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052231

    Chapter  Google Scholar 

  21. Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: Performance improvements and a baseline parameter generation algorithm for NTRUSign. Cryptology ePrint Archive Report 2005/274 (2005). https://eprint.iacr.org/2005/274

  22. Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSign: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36563-X_9

    Chapter  Google Scholar 

  23. Howe, J., Prest, T., Ricosset, T., Rossi, M.: Isochronous Gaussian sampling: from inception to implementation. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 53–71. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_4

    Chapter  Google Scholar 

  24. Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_27

    Chapter  Google Scholar 

  25. Karabulut, E., Aysu, A.: Falcon down: breaking falcon post-quantum signature scheme through side-channel attacks (2021)

    Google Scholar 

  26. Laarhoven, T.: Search problems in cryptography. Ph.D. thesis, Eindhoven University of Technology (2015)

    Google Scholar 

  27. Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Crypt. 75(3), 565–599 (2014). https://doi.org/10.1007/s10623-014-9938-4

    Article  MathSciNet  MATH  Google Scholar 

  28. Lyubashevsky, V., et al.: CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

  29. Lyubashevsky, V., et al.: CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions

  30. Lyubashevsky, V., Wichs, D.: Simple lattice trapdoor sampling from a broad class of distributions. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 716–730. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_32

    Chapter  Google Scholar 

  31. Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_2

    Chapter  Google Scholar 

  32. Micciancio, D., Walter, M.: Gaussian sampling over the integers: efficient, generic, constant-time. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 455–485. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_16

    Chapter  Google Scholar 

  33. Nguyen, P.Q., Regev, O.: Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. J. Cryptol. 22(2), 139–160 (2008). https://doi.org/10.1007/s00145-008-9031-0

    Article  MathSciNet  MATH  Google Scholar 

  34. Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_5

    Chapter  Google Scholar 

  35. Pornin, T.: New efficient, constant-time implementations of Falcon. Cryptology ePrint Archive Report 2019/893 (2019). https://eprint.iacr.org/2019/893

  36. Pornin, T., Prest, T.: More efficient algorithms for the NTRU key generation using the field norm. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11443, pp. 504–533. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_17

    Chapter  MATH  Google Scholar 

  37. Prest, T.: Gaussian sampling in lattice-based cryptography. Ph.D. thesis, École Normale Supérieure, Paris, France (2015)

    Google Scholar 

  38. Prest, T., et al.: FALCON. Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions

  39. Rivain, M., Prouff, E.: Provably secure higher-order masking of AES. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 413–427. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15031-9_28

    Chapter  Google Scholar 

  40. Yu, Y., Ducas, L.: Learning strikes again: the case of the DRS signature scheme. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 525–543. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_18

    Chapter  Google Scholar 

  41. Zhao, R.K., Steinfeld, R., Sakzad, A.: FACCT: fast, compact, and constant-time discrete gaussian sampler over integers. IEEE Trans. Comput. 69(1), 126–137 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We would like to thank Léo Ducas, Thomas Prest and Damien Stehlé for valuable comments and discussions. The second and seventh authors were supported by the European Union H2020 Research and Innovation Program Grant 780701 (PROMETHEUS). The third author was supported by the ERC Advanced Grant No. 787390. The fifth author has been supported by the Carlsberg Foundation under the Semper Ardens Research Project CF18-112 (BCM); the European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No. 803096 (SPEC). The eighth author has been supported by the National Natural Science Foundation of China (No. 62102216), the National Key Research and Development Program of China (Grant No. 2018YFA0704701), the Major Program of Guangdong Basic and Applied Research (Grant No. 2019B030302008) and Major Scientific and Techological Innovation Project of Shandong Province, China (Grant No. 2019JZZY010133).

Author information

Authors and Affiliations

  1. NTT Corporation, Tokyo, Japan

    Thomas Espitau & Mehdi Tibouchi

  2. IRISA, Univ Rennes 1, Inria, Rennes Bretagne-Atlantique Center, Rennes, France

    Pierre-Alain Fouque & Alexandre Wallet

  3. University of Luxembourg, Esch-sur-Alzette, Luxembourg

    François Gérard

  4. ANSSI, Paris, France

    Mélissa Rossi

  5. Aarhus University, Aarhus, Denmark

    Akira Takahashi

  6. BNRist, Tsinghua University, Bei**g, China

    Yang Yu

Authors
  1. Thomas Espitau
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pierre-Alain Fouque
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. François Gérard
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mélissa Rossi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Akira Takahashi
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Mehdi Tibouchi
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Alexandre Wallet
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Yang Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yang Yu .

Editor information

Editors and Affiliations

  1. University of Haifa, Haifa, Haifa, Israel

    Orr Dunkelman

  2. University of Warsaw, Warsaw, Poland

    Stefan Dziembowski

Rights and permissions

Reprints and permissions

Copyright information

© 2022 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Espitau, T. et al. (2022). Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon. In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13277. Springer, Cham. https://doi.org/10.1007/978-3-031-07082-2_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-07082-2_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-07081-5

  • Online ISBN: 978-3-031-07082-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation