Abstract
Lattice-based schemes are among the most promising post-quantum schemes, yet the effect of both parameter and implementation choices on their side-channel resilience is still poorly understood. Aysu et al. (HOST’18) recently investigated single-trace attacks against the core lattice operation, namely multiplication between a public matrix and a “small” secret vector, in the context of a hardware implementation. We complement this work by considering single-trace attacks against software implementations of “ring-less” LWE-based constructions. Specifically, we target Frodo, one of the submissions to the standardisation process of NIST, when implemented on an (emulated) ARM Cortex M0 processor. We confirm Aysu et al.’s observation that a standard divide-and-conquer attack is insufficient and instead we resort to a sequential, extend-and-prune approach. In contrast to Aysu et al. we find that, in our setting where the power model is far from being as clear as theirs, both profiling and less aggressive pruning are needed to obtain reasonable key recovery rates for SNRs of practical relevance. Our work drives home the message that parameter selection for LWE schemes is a double-edged sword: the schemes that are deemed most secure against (black-box) lattice attacks can provide the least security when considering side-channels. Finally, we suggest some easy countermeasures that thwart standard extend-and-prune attacks.
Original language | English |
---|---|
Title of host publication | Selected Areas in Cryptography – SAC 2018 - 25th International Conference, Revised Selected Papers |
Editors | Carlos Cid, Michael J. Jacobson |
Publisher | Springer Verlag |
Pages | 216-234 |
Number of pages | 19 |
ISBN (Print) | 9783030109691 |
DOIs | |
Publication status | Published - 2019 |
Event | 25th International Conference on Selected Areas in Cryptography, SAC 2018 - Calgary, Canada Duration: 15 Aug 2018 → 17 Aug 2018 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11349 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 25th International Conference on Selected Areas in Cryptography, SAC 2018 |
---|---|
Country/Territory | Canada |
City | Calgary |
Period | 15/08/18 → 17/08/18 |
Bibliographical note
Funding Information:The research leading to these results has received funding from the European Union’s Horizon 2020 research and innovation programme Marie Sk lodowska-Curie ITN ECRYPT-NET (Project Reference 643161) and Horizon 2020 project PQCRYPTO (Project Reference 645622). Furthermore, Elisabeth Oswald was partially funded by H2020 grant SEAL (Project Reference 725042). We thank the authors of ELMO for their kind help, comments and feedback.
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
Keywords
- Frodo
- Lattices
- LWE
- Side-channel analysis
- Template attacks
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science