$$\mathsf {\textsf{Plover}}$$ : Masking-Friendly Hash-and-Sign Lattice Signatures | SpringerLink
Skip to main content
Springer Nature Link
Log in

\(\mathsf {\textsf{Plover}}\): Masking-Friendly Hash-and-Sign Lattice Signatures

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

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

  • 884 Accesses

Abstract

We introduce a toolkit for transforming lattice-based hash-and-sign signature schemes into masking-friendly signatures secure in the t-probing model. Until now, efficiently masking lattice-based hash-and-sign schemes has been an open problem, with unsuccessful attempts such as Mitaka. A first breakthrough was made in 2023 with the NIST PQC submission Raccoon, although it was not formally proven.

Our main conceptual contribution is to realize that the same principles underlying Raccoon are very generic, and to find a systematic way to apply them within the hash-and-sign paradigm. Our main technical contribution is to formalize, prove, instantiate and implement a hash-and-sign scheme based on these techniques. Our toolkit includes noise flooding to mitigate statistical leaks, and an extended Strong Non-Interfering probing security (\(\textsf{SNIu} \)) property to handle masked gadgets with unshared inputs.

We showcase the efficiency of our techniques in a signature scheme, \(\mathsf {\mathsf {\textsf{Plover}} \text {-}\mathsf {\textsf{RLWE}} }\), based on (hint) Ring-LWE. It is the first lattice-based masked hash-and-sign scheme with quasi-linear complexity \(O(d \log d)\) in the number of shares d. Our performances are competitive with the state-of-the-art masking-friendly signature, the Fiat-Shamir scheme \(\textsf{Raccoon}\).

Part of this project was conducted while Guilhem Niot was a student at EPFL and ENS Lyon, interning at PQShield.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7549
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9437
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping 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.

    See https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Hq-wRFDbIaU.

References

  1. Alagic, G., et al.: NISTIR 8413 – Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process (2022). https://doi.org/10.6028/NIST.IR.8413

  2. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015). http://www.degruyter.com/view/j/jmc.2015.9.issue-3/jmc-2015-0016/jmc-2015-0016.xml

  3. Azouaoui, M., et al.: Protecting dilithium against leakage revisited sensitivity analysis and improved implementations. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2023(4), 58–79 (2023). https://doi.org/10.46586/tches.v2023.i4.58-79

  4. 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

  5. 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 

  6. Battistello, A., Coron, J.-S., Prouff, E., Zeitoun, R.: Horizontal side-channel attacks and countermeasures on the ISW masking scheme. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 23–39. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53140-2_2

    Chapter  Google Scholar 

  7. Berzati, A., Viera, A.C., Chartouny, M., Madec, S., Vergnaud, D., Vigilant, D.: Exploiting intermediate value leakage in dilithium: a template-based approach. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2023(4), 188–210 (2023). https://doi.org/10.46586/tches.v2023.i4.188-210

  8. Bronchain, O., Cassiers, G.: Bitslicing arithmetic/boolean masking conversions for fun and profit with application to lattice-based KEMs. IACR TCHES 2022(4), 553–588 (2022). https://doi.org/10.46586/tches.v2022.i4.553-588

  9. 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

  10. Coron, J., Gérard, F., Montoya, S., Zeitoun, R.: High-order polynomial comparison and masking lattice-based encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2023(1), 153–192 (2023). https://doi.org/10.46586/tches.v2023.i1.153-192

  11. Coron, J., Gérard, F., Trannoy, M., Zeitoun, R.: High-order masking of NTRU. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2023(2), 180–211 (2023). https://doi.org/10.46586/tches.v2023.i2.180-211

  12. Coron, J., Gérard, F., Trannoy, M., Zeitoun, R.: Improved gadgets for the high-order masking of dilithium. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2023(4), 110–145 (2023). https://doi.org/10.46586/tches.v2023.i4.110-145

  13. Duc, A., Faust, S., Standaert, F.X.: Making masking security proofs concrete (or how to evaluate the security of any leaking device), extended version. J. Cryptol. 32(4), 1263–1297 (2019). https://doi.org/10.1007/s00145-018-9277-0

    Article  MathSciNet  Google Scholar 

  14. Espitau, T., Fouque, P.A., Gérard, F., Rossi, M., Takahashi, A., Tibouchi, M., Wallet, A., Yu, Y.: Mitaka: A simpler, parallelizable, maskable variant of falcon. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. LNCS, vol. 13277, pp. 222–253. Springer, Heidelberg (May / Jun 2022). https://doi.org/10.1007/978-3-031-07082-2_9

  15. Espitau, T., Kirchner, P.: The nearest-colattice algorithm. Cryptology ePrint Archive, Report 2020/694 (2020). https://eprint.iacr.org/2020/694

  16. 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

  17. Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: Yao, A.C. (ed.) Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, 5–7 January 2010. Proceedings, pp. 230–240. Tsinghua University Press (2010). http://conference.iiis.tsinghua.edu.cn/ICS2010/content/papers/19.html

  18. Goubin, L.: A sound method for switching between Boolean and arithmetic masking. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 3–15. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44709-1_2

    Chapter  Google Scholar 

  19. Guerreau, M., Martinelli, A., Ricosset, T., Rossi, M.: The hidden parallelepiped is back again: Power analysis attacks on falcon. IACR TCHES 2022(3), 141–164 (2022). https://doi.org/10.46586/tches.v2022.i3.141-164

  20. 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 

  21. Ito, A., Ueno, R., Homma, N.: On the success rate of side-channel attacks on masked implementations: information-theoretical bounds and their practical usage. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022, pp. 1521–1535. ACM Press, November 2022. https://doi.org/10.1145/3548606.3560579

  22. Kannwischer, M.J., Genêt, A., Butin, D., Krämer, J., Buchmann, J.: Differential power analysis of XMSS and SPHINCS. In: Fan, J., Gierlichs, B. (eds.) COSADE 2018. LNCS, vol. 10815, pp. 168–188. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89641-0_10

    Chapter  Google Scholar 

  23. Karabulut, E., Alkim, E., Aysu, A.: Single-trace side-channel attacks on \(\omega \)-small polynomial sampling: with applications to NTRU, NTRU prime, and CRYSTALS-DILITHIUM. In: IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2021, Tysons Corner, VA, USA, 12–15 December 2021, pp. 35–45. IEEE (2021). https://doi.org/10.1109/HOST49136.2021.9702284

  24. Kim, D., Lee, D., Seo, J., Song, Y.: Toward practical lattice-based proof of knowledge from hint-MLWE. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part V. LNCS, vol. 14085, pp. 549–580. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38554-4_18

    Chapter  Google Scholar 

  25. Kim, M., Lee, D., Seo, J., Song, Y.: Accelerating HE operations from key decomposition technique. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part IV. LNCS, vol. 14084, pp. 70–92. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38551-3_3

    Chapter  Google Scholar 

  26. Masure, L., Rioul, O., Standaert, F.: A nearly tight proof of Duc et al.’s conjectured security bound for masked implementations. In: Buhan, I., Schneider, T. (eds.) CARDIS 2022. LNCS, vol. 13820, pp. 69–81. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-25319-5_4

    Chapter  Google Scholar 

  27. Mathieu-Mahias, A.: Securisation of implementations of cryptographic algorithms in the context of embedded systems. Theses, Université Paris-Saclay, December 2021. https://theses.hal.science/tel-03537322

  28. Montgomery, P.L.: Speeding the pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987). https://doi.org/10.1090/s0025-5718-1987-0866113-7

    Article  MathSciNet  Google Scholar 

  29. del Pino, R., et al.: Raccoon, a side-channel secure signature scheme. Technical report. National Institute of Standards and Technology (2023). https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures

  30. del Pino, R., Katsumata, S., Maller, M., Mouhartem, F., Prest, T., Saarinen, M.J.: Threshold raccoon: practical threshold signatures from standard lattice assumptions. Cryptology ePrint Archive, Paper 2024/184 (2024). https://eprint.iacr.org/2024/184

  31. del Pino, R., Prest, T., Rossi, M., Saarinen, M.O.: High-order masking of lattice signatures in quasilinear time. In: 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, 21–25 May 2023, pp. 1168–1185. IEEE (2023). https://doi.org/10.1109/SP46215.2023.10179342

  32. Prest, T.: A key-recovery attack against Mitaka in the \(t\)-probing model. In: Boldyreva, A., Kolesnikov, V. (eds.) PKC 2023, Part I. LNCS, vol. 13940, pp. 205–220. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-31368-4_8

    Chapter  Google Scholar 

  33. Saarinen, M.J.O., Rossi, M.: Mask compression: high-order masking on memory-constrained devices. Cryptology ePrint Archive, Paper 2023/1117 (2023). https://eprint.iacr.org/2023/1117

  34. Yu, Y., Jia, H., Wang, X.: Compact lattice gadget and its applications to hash-and-sign signatures. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part V. LNCS, vol. 14085, pp. 390–420. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38554-4_13

    Chapter  Google Scholar 

  35. Zhang, S., Lin, X., Yu, Y., Wang, W.: Improved power analysis attacks on falcon. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part IV. LNCS, vol. 14007, pp. 565–595. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30634-1_19

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Monash University, Melbourne, Australia

    Muhammed F. Esgin, Amin Sakzad & Ron Steinfeld

  2. PQShield SAS, Paris, France

    Thomas Espitau, Guilhem Niot & Thomas Prest

Authors
  1. Muhammed F. Esgin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Espitau
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Guilhem Niot
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Thomas Prest
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Amin Sakzad
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Ron Steinfeld
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Espitau .

Editor information

Editors and Affiliations

  1. Zama, Paris, France

    Marc Joye

  2. Ruhr University Bochum, Bochum, Germany

    Gregor Leander

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Esgin, M.F., Espitau, T., Niot, G., Prest, T., Sakzad, A., Steinfeld, R. (2024). \(\mathsf {\textsf{Plover}}\): Masking-Friendly Hash-and-Sign Lattice Signatures. In: Joye, M., Leander, G. (eds) Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT 2024. Lecture Notes in Computer Science, vol 14657. Springer, Cham. https://doi.org/10.1007/978-3-031-58754-2_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-58754-2_12

  • Published:

  • Publisher Name: Springer, Cham

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

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

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships