Cortex-M4 optimizations for {R,M} LWE schemes
This paper proposes various optimizations for lattice-based key encapsulation mechanisms (KEM) using the Number Theoretic Transform (NTT) on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polyn...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2020-06-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/8593 |
| _version_ | 1811283780814503936 |
|---|---|
| author | Erdem Alkim Yusuf Alper Bilgin Murat Cenk François Gérard |
| author_facet | Erdem Alkim Yusuf Alper Bilgin Murat Cenk François Gérard |
| author_sort | Erdem Alkim |
| collection | DOAJ |
| description | This paper proposes various optimizations for lattice-based key encapsulation mechanisms (KEM) using the Number Theoretic Transform (NTT) on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of Kyber and NewHope, both round 2 candidates in the NIST post-quantum project, and also NewHope-Compact, a recently proposed variant of NewHope with smaller parameters. Our software is the first implementation of NewHope-Compact on the Cortex-M4 and shows speed improvements over previous high-speed implementations of Kyber and NewHope. Moreover, it gives a common framework to compare those schemes with the same level of optimization. Our results show that NewHope- Compact is the fastest scheme, followed by Kyber, and finally NewHope, which seems to suffer from its large modulus and error distribution for small dimensions. |
| first_indexed | 2024-04-13T02:18:49Z |
| format | Article |
| id | doaj.art-1267f9a49bf24273850871c91e5674aa |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-13T02:18:49Z |
| publishDate | 2020-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-1267f9a49bf24273850871c91e5674aa2022-12-22T03:07:04ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252020-06-012020310.13154/tches.v2020.i3.336-357Cortex-M4 optimizations for {R,M} LWE schemesErdem Alkim0Yusuf Alper Bilgin1Murat Cenk2François Gérard3Department of Computer Engineering, Ondokuz Mayıs University, Samsun, Turkey; Fraunhofer SIT, Darmstadt, GermanyAselsan Inc., Ankara, Turkey; Institute of Applied Mathematics, Middle East Technical University, Ankara, TurkeyInstitute of Applied Mathematics, Middle East Technical University, Ankara, TurkeyUniversité libre de Bruxelles, Brussels, BelgiumThis paper proposes various optimizations for lattice-based key encapsulation mechanisms (KEM) using the Number Theoretic Transform (NTT) on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of Kyber and NewHope, both round 2 candidates in the NIST post-quantum project, and also NewHope-Compact, a recently proposed variant of NewHope with smaller parameters. Our software is the first implementation of NewHope-Compact on the Cortex-M4 and shows speed improvements over previous high-speed implementations of Kyber and NewHope. Moreover, it gives a common framework to compare those schemes with the same level of optimization. Our results show that NewHope- Compact is the fastest scheme, followed by Kyber, and finally NewHope, which seems to suffer from its large modulus and error distribution for small dimensions.https://tches.iacr.org/index.php/TCHES/article/view/8593ARM Cortex-M4Post-quantum key encapsulationlattice-based cryptographyRLWEMLWENTT |
| spellingShingle | Erdem Alkim Yusuf Alper Bilgin Murat Cenk François Gérard Cortex-M4 optimizations for {R,M} LWE schemes Transactions on Cryptographic Hardware and Embedded Systems ARM Cortex-M4 Post-quantum key encapsulation lattice-based cryptography RLWE MLWE NTT |
| title | Cortex-M4 optimizations for {R,M} LWE schemes |
| title_full | Cortex-M4 optimizations for {R,M} LWE schemes |
| title_fullStr | Cortex-M4 optimizations for {R,M} LWE schemes |
| title_full_unstemmed | Cortex-M4 optimizations for {R,M} LWE schemes |
| title_short | Cortex-M4 optimizations for {R,M} LWE schemes |
| title_sort | cortex m4 optimizations for r m lwe schemes |
| topic | ARM Cortex-M4 Post-quantum key encapsulation lattice-based cryptography RLWE MLWE NTT |
| url | https://tches.iacr.org/index.php/TCHES/article/view/8593 |
| work_keys_str_mv | AT erdemalkim cortexm4optimizationsforrmlweschemes AT yusufalperbilgin cortexm4optimizationsforrmlweschemes AT muratcenk cortexm4optimizationsforrmlweschemes AT francoisgerard cortexm4optimizationsforrmlweschemes |