Key Recovery from Gram-Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices
| Autor: | Paul Kirchner, Mehdi Tibouchi, Alexandre Wallet, Pierre-Alain Fouque, Yang Yu |
|---|---|
| Přispěvatelé: | Embedded Security and Cryptography / Sécurité cryptographie embarquée (EMSEC), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Computer science
NTRU Timing Attacks Gram schmidt Hash function Key recovery 02 engineering and technology Lattice-Based Cryptography 020202 computer hardware & architecture Cryptanalysis [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Norm (mathematics) Lattice (order) Lattice Gaussian Sampling 0202 electrical engineering electronic engineering information engineering NIST 020201 artificial intelligence & image processing Algorithm Algebraic Number Theory Computer Science::Cryptography and Security Leakage (electronics) |
| Zdroj: | Advances in Cryptology – EUROCRYPT 2020 Advances in Cryptology – EUROCRYPT 2020, May 2020, Zagreb, Croatia. pp.34-63, ⟨10.1007/978-3-030-45727-3_2⟩ Lecture Notes in Computer Science Lecture Notes in Computer Science-Advances in Cryptology – EUROCRYPT 2020 Advances in Cryptology – EUROCRYPT 2020 ISBN: 9783030457266 EUROCRYPT (3) Advances in Cryptology – EUROCRYPT 2020-39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part III |
| ISSN: | 0302-9743 1611-3349 |
| DOI: | 10.1007/978-3-030-45727-3_2⟩ |
| Popis: | International audience; In this paper, we initiate the study of side-channel leakage in hash-and-sign lattice-based signatures, with particular emphasis on the two efficient implementations of the original GPV lattice-trapdoor paradigm for signatures, namely NIST second-round candidate Falcon and its simpler predecessor DLP. Both of these schemes implement the GPV signature scheme over NTRU lattices, achieving great speed-ups over the general lattice case. Our results are mainly threefold. First, we identify a specific source of side-channel leakage in most implementations of those schemes, namely, the one-dimensional Gaussian sampling steps within lattice Gaussian sampling. It turns out that the implementations of these steps often leak the Gram-Schmidt norms of the secret lattice basis. Second, we elucidate the link between this leakage and the secret key, by showing that the entire secret key can be efficiently reconstructed solely from those Gram-Schmidt norms. The result makes heavy use of the algebraic structure of the corresponding schemes, which work over a power-of-two cyclotomic field. Third, we concretely demonstrate the side-channel attack against DLP (but not Falcon due to the different structures of the two schemes). The challenge is that timing information only provides an approximation of the Gram-Schmidt norms, so our algebraic recovery technique needs to be combined with pruned tree search in order to apply it to approximate values. Experimentally, we show that around 2 35 DLP traces are enough to reconstruct the entire key with good probability. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|