Giant Footprint Sharing: A Memory-Efficient Decryption Implementation for Classic McEliece

Classic McEliece has gathered attention as a candidate in NIST post-quantum cryptography standardization. However, it suffers from high demands on the decryption algorithm, making it unsuitable for resource-constrained devices. In this paper, we propose a novel implementation method, named giant footprint sharing, that reduces memory size during decryption in Classic McEliece. The decryption algorithm processes a large number of intermediate variables computed from a secret key in memory. The giant footprint sharing identifies the largest variable among them and allocates a memory-sharing structure to store it, thereby reducing the overall memory size regardless of the implementation platform. The giant footprint sharing can also be combined with existing acceleration techniques, such as fast Fourier transformation. We evaluate Classic McEliece with the giant footprint sharing on the Arm Cortex-M33 CPU and show that it reduces memory size by up to 46% without significant degradation in computation time compared with the existing fast-implementation by Chen et al. (at TCHES 2021). Extensive experiments with the giant footprint sharing further reveal that it maintains a constant memory size regardless of the compiler optimization, and it also achieves an optimal balance in the trade-off between memory size and computation time. The giant footprint sharing is remarkable for any scheme, that contains a large-scale matrix computation and the life cycle for each variable is limited.