(Full) Leakage resilience of Fiat-Shamir signatures over lattices

Abstract

Fiat-Shamir is a mainstream construction paradigm of lattice-based signature schemes. While its theoretical security is well-studied, its implementation security in the presence of leakage is a relatively under-explored topic. Specifically, even some side-channel attacks on lattice-based Fiat-Shamir signature (FS-Sig) schemes have been proposed since 2016, little work on the leakage resilience of these schemes appears. Worse still, the proof idea of the leakage resilience of FS-Sig schemes based on traditional number-theoretic assumptions does not apply to most lattice-based FS-Sig schemes. For this, we propose a framework to construct fully leakage resilient lattice-based FS-Sig schemes in the bounded memory leakage (BML) model. The framework consists of two parts. The first part shows how to construct leakage resilient FS-Sig schemes in BML model from leakage resilient versions of non-lossy or lossy identification schemes, which can be instantiated based on lattice assumptions. The second part shows how to construct fully leakage resilient FS-Sig schemes based on leakage resilient ones together with a new property called state reconstruction. We show almost all lattice-based FS-Sig schemes have this property. As a concrete application of our fundamental framework, we apply it to existing lattice-based FS-Sig schemes and provide analysis results of their security in the leakage setting.

Graphical abstract

Keywords

leakage resilience / lattice-based signatures / Fiat-Shamir paradigm / side-channel attacks / post-quantum cryptography

References

[1] National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization. 2016

[2] Fouque P A, Hoffstein J, Kirchner P, Lyubashevsky V, Pornin T, Prest T, Ricosset T, Seiler G, Whyte W, Zhang Z F. FALCON: fast-Fourier lattice-based compact signatures over NTRU. Submission to the NIST Post-Quantum Cryptography Standardization. 2019

[3] Ducas L , Kiltz E , Lepoint T , Lyubashevsky V , Schwabe P , Seiler G , Stehlé D . CRYSTALS-Dilithium: a lattice-based digital signature scheme. Journal of IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018, 2018( 1): 238– 268

[4] Fiat A, Shamir A. How to prove yourself: practical solutions to identification and signature problems. In: Proceedings on Advances in Cryptology – CRYPTO. 1987, 186– 194

[5] Lyubashevsky V. Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security. 2009, 598– 616

[6] Lyubashevsky V. Lattice signatures without trapdoors. In: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2012, 738– 755

[7] Ducas L, Durmus A, Lepoint T, Lyubashevsky V. Lattice signatures and bimodal Gaussians. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 40– 56

[8] Bai S, Galbraith S D. An improved compression technique for signatures based on learning with errors. In: Proceedings of Cryptographers’ Track at the RSA Conference. 2014, 28– 47

[9] Bindel N, Akleylek S, Alkim E, Barreto P S L M, Buchmann J, Eaton E, Gutoski G, Krämer J, Longa P, Polat H, Ricardini J E, Zanon G. qTESLA. Submission to the NIST Post-Quantum Cryptography Standardization. 2019

[10] Bruinderink L G, Hülsing A, Lange T, Yarom Y. Flush, gauss, and reload – a cache attack on the BLISS lattice-based signature scheme. In: Proceedings of the 18th International Conference on Cryptographic Hardware and Embedded Systems. 2016, 323– 345

[11] Pessl P, Bruinderink L G, Yarom Y. To BLISS-B or not to be: attacking strongSwan’s implementation of post-quantum signatures. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1843−1855

[12] Ducas L. Accelerating bliss: the geometry of ternary polynomials. Journal of IACR Cryptology ePrint Archive, 2014

[13] Espitau T, Fouque P A, Gérard B, Tibouchi M. Side-channel attacks on BLISS lattice-based signatures: exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1857−1874

[14] Dziembowski S, Pietrzak K. Leakage-resilient cryptography. In: Proceedings of 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 2008, 293– 302

[15] Katz J, Vaikuntanathan V. Signature schemes with bounded leakage resilience. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security. 2009, 703– 720

[16] Alwen J, Dodis Y, Wichs D. Leakage-resilient public-key cryptography in the bounded-retrieval model. In: Proceedings of the 29th Annual International Cryptology Conference. 2009, 36– 54

[17] Dodis Y, Haralambiev K, Lopez-Alt A, Wichs D. Cryptography against continuous memory attacks. In: Proceedings of 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. 2010, 511– 520

[18] Hazay C, López-Alt A, Wee H, Wichs D. Leakage-Resilient cryptography from minimal assumptions. In: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 160– 176

[19] Katz J, Wang N. Efficiency improvements for signature schemes with tight security reductions. In: Proceedings of the 10th ACM Conference on Computer and Communications Security. 2003, 155– 164

[20] Goldwasser S, Kalai Y T, Peikert C, Vaikuntanathan V. Robustness of the learning with errors assumption. In: Proceedings of Innovations in Computer Science – ICS. 2010, 230– 240

[21] Brakerski Z, Döttling N. Hardness of LWE on general entropic distributions. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020, 551– 575

[22] Garg S, Jain A, Sahai A. Leakage-resilient zero knowledge. In: Proceedings of the 31st Annual Cryptology Conference. 2011, 297– 315

[23] Abdalla M, Fouque P A, Lyubashevsky V, Tibouchi M. Tightly-secure signatures from lossy identification schemes. In: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2012, 572– 590

[24] Kiltz E, Lyubashevsky V, Schaffner C. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In: Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2018, 552– 586

[25] Kocher P, Jaffe J, Jun B. Differential power analysis. In: Proceedings of the 19th Annual International Cryptology Conference. 1999, 388– 397

[26] Halderman J A, Schoen S D, Heninger N, Clarkson W, Paul W, Calandrino J A, Feldman A J, Appelbaum J, Felten E W. Lest we remember: Cold boot attacks on encryption keys. In: Proceedings of the 17th USENIX Security Symposium. 2008, 45– 60

[27] Akavia A, Goldwasser S, Vaikuntanathan V. Simultaneous hardcore bits and cryptography against memory attacks. In: Proceedings of the 6th Theory of Cryptography Conference. 2009, 474– 495

[28] Naor M, Segev G. Public-key cryptosystems resilient to key leakage. In: Proceedings of the 29th Annual International Cryptology Conference. 2009, 18– 35

[29] Brakerski Z, Kalai Y T, Katz J, Vaikuntanathan V. Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage. In: Proceedings of IEEE 51st Annual Symposium on Foundations of Computer Science. 2010, 501– 510

[30] Dodis Y, Haralambiev K, López-Alt A, Wichs D. Efficient public-key cryptography in the presence of key leakage. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security. 2010, 613– 631

[31] Boyle E, Segev G, Wichs D. Fully leakage-resilient signatures. In: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2011, 89– 108

[32] Malkin T, Teranishi I, Vahlis Y, Yung M. Signatures resilient to continual leakage on memory and computation. In: Proceedings of the 8th Theory of Cryptography Conference. 2011, 89– 106

[33] Faust S, Hazay C, Nielsen J B, Nordholt P S, Zottarel A. Signature schemes secure against hard-to-invert leakage. In: Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security. 2012, 98– 115

[34] Nielsen J B, Venturi D, Zottarel A. Leakage-resilient signatures with graceful degradation. In: Proceedings of the 17th International Workshop on Public Key Cryptography. 2014, 362– 379

[35] Dodis Y , Ostrovsky R , Reyzin L , Smith A . Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 2008, 38( 1): 97– 139

[36] Alwen J, Krenn S, Pietrzak K, Wichs D. Learning with rounding, revisited - new reduction, properties and applications. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 57– 74

[37] Lyubashevsky V, Neven G. One-shot verifiable encryption from lattices. In: Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2017, 293– 323

[38] Brakerski Z, Döttling N. Lossiness and entropic hardness for Ring-LWE. In: Proceedings of the 18th Theory of Cryptography Conference. 2020, 1– 27

Acknowledgements

This work was supported in part by National Natural Science Foundation of China (Grant Nos. 61632020, U1936209, 62002353) and Beijing Natural Science Foundation (4192067).

RIGHTS & PERMISSIONS

2022 Higher Education Press