The Giant Footprint is the Smallest: Low-Footprint Decryption of Classic McEliece

Classic McEliece has garnered attention as a candidate in NIST post-quantum cryptography standardization. However, it suffers from high computational demands in its decryption, making it unsuitable for resource-constrained devices. In this paper, we propose a low-footprint implementation method, named Giant Footprint Sharing, that reduces memory size during decryption in Classic McEliece. The decryption algorithm processes a large number of in-memory intermediate variables computed from the secrets. We identify the largest variable among them and implement a memory-sharing structure to store it, thereby reducing the overall memory size. Giant Footprint Sharing can also be combined with high-throughput acceleration techniques, such as fast Fourier transformation. We evaluate Classic McEliece with Giant Footprint Sharing on the Arm Cortex-M33 CPU and show that it reduces memory size by more than half without significant degradation in computation time compared with the existing optimized implementation (Chen et al., TCHES 2021). A detailed examination of the proposed method further reveals that our implementation achieves an optimal balance in the trade-off between memory size and computation time.