(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

RIGHTS & PERMISSIONS

Higher Education Press