Running Longer To Slim Down: Post-Quantum Cryptography on Memory-Constrained Devices

Since we are getting closer to the realisation of a quantum computer capable of breaking the currently deployed public key cryptosystems, we need to be ready with the next generation of quantum-safe cryptosystems. In the case of small, low-memory embedded/cyber physical systems frequently used in the IoT world, the adoption of these post-quantum cryptography algorithms (PQC) is far from being straightforward. Currently available implementations are mostly characterized by high memory requirements that make the adoption on constrained devices a difficult challenge. In this work, we explore the feasibility of implementing quantum resistant cryptography on memory-restricted devices and we present the strategies that should be adopted while tackling the problem. We summarize and discuss the most common techniques currently available in literature for trading speed with reduced memory footprint. Discussed techniques range from strategies to minimise the static memory required by an implementation to techniques to deal with large artifact sizes. We show that, by using the appropriated optimization technique, even PQC schemes that require an amount of memory that largely exceeds the memory available on certain devices, can be successfully implemented, while also leaving enough memory for other applications that might reside on the same device.