DongHyun Shin
Kookmin University, Seoul, Republic of Korea

YoungBeom Kim
Kookmin University, Seoul, Republic of Korea; Queen’s University Belfast, Northern Ireland, United Kingdom

Ayesha Khalid
Queen’s University Belfast, Northern Ireland, United Kingdom

Maire O’Neill
Queen’s University Belfast, Northern Ireland, United Kingdom

Seog Chung Seo
Kookmin University, Seoul, Republic of Korea; Queen’s University Belfast, Northern Ireland, United Kingdom

Keywords: CRYSTALS-Kyber, CRYSTALS-Dilithium, 16-bit MSP430 microcontroller, NTT, SHA-3, modular arithmetic, lattice-based cryptography, Keccak

Abstract

Post-Quantum cryptography (PQC) typically requires more memory and computational power than conventional public-key cryptography. Until now, most active research in PQC optimization for embedded devices has focused on 32-bit and 64-bit ARM architectures, specifically Cortex-M0/M3/M4 and ARMv8. To enable a smooth migration of PQC algorithms in Internet of Things environments, optimization research is also required for devices with lower computational capabilities. To address this gap, we present the optimized implementation methodologies of CRYSTALS– Kyber and CRYSTALS–Dilithium, the National Institute of Standards and Technology (NIST) standardized key-encapsulation mechanism (KEM) and digital signature algorithm (DSA) on a widely used 16-bit MSP430 microcontroller. We review the current state-of-the-art implementation methodologies for Keccak, Kyber, and Dilithium, and carefully redesign them to suit the MSP430 architecture. For Number-Theoretic Transform (NTT)-based polynomial multiplication, we redesign optimal modular arithmetic, layer merging, and point-wise multiplication by taking full advantage of the characteristics of the MSP430. As a result, compared with the reference implementations in C, the optimized 16-bit NTT achieves performance improvements of 134%, 249%, and 210% for NTT, NTT−1, and point-wise multiplication, respectively, while the optimized 32-bit NTT achieves performance improvements of 91%, 96%, and 56% for NTT, NTT−1, and point-wise multiplication, respectively. Furthermore, for Keccak, we propose twisting and zig-zag techniques tailored to the MSP430, aimed at optimizing memory accesses. As a result, compared with the reference implementation in C, the optimized Keccak achieves a performance improvement of 57%. Moreover, compared with the reference implementations in C, our Kyber and Dilithium implementations achieve 46.1%–51.3%, 45.6%–60.0%, and 46.2%–62.3% for key generation (KeyGen), encapsulation (Encaps), and decapsulation (Decaps), respectively, and 44.5%–48.3%, 57.5%–65.0%, and 46.1%–50.0% improvements for KeyGen, signing (Sign), and verifying (Verify), respectively.