Paper 2025/1359

Runtime Code Generation for Constant-Time Secret-Indexed Array Accesses: Applications to PERK and NTRU

Abstract

One of the main guidelines to prevent timing side-channel attacks against cryptographic implementations is to avoid array accesses indexed by secret data. However, alternatives and countermeasures often incur significant performance losses. We propose a novel methodology for secure, constant-time implementation of algorithms that read and write to small arrays with secret-dependent indices, with a constant-factor performance impact compared to timing-unprotected accesses. It is specifically suitable for simple in-order CPUs like those in embedded systems, e.g., the ARM Cortex-M4 core. Although our methodology is general, we illustrate it with secure implementation of permutation operations, such as composition, inversion, and sampling, the latter using the Fisher-Yates shuffle. We apply this methodology to the post-quantum cryptosystems PERK and NTRU, bridging most of the performance gap to unprotected implementations that employ secret-dependent array accesses.