Precomputation Methods for Faster and Greener Post-Quantum Cryptography on Emerging Embedded Platforms.
Aydın Aysu, Patrick R. Schaumont · 2015
Abstract. Precomputation techniques are useful to improve real-time performance of complex algorithms at the expense of extra memory, and extra preparatory computations. This practice is ne-glected especially in the embedded context where energy and mem-ory space is limited. Instead, the embedded space favors the imme-diate reduction of energy and memory footprint. However, the em-bedded platforms of the future may be different from the traditional ones. Energy-harvesting sensor nodes may extract virtually limit-less energy from their surrounding, while at the same time they are able to store more data at cheaper cost, thanks to Moore’s law. Yet, minimizing the run-time energy and latency will still be primary targets for today’s as well as future real-time embed-ded systems. Another important challenge for the future systems is to provide efficient public-key based solutions that can thwart quantum-cryptanalysis. In this article, we address these two con-cepts. We apply precomputation techniques on two post-quantum digital signature schemes: hash-based and lattice-based digital sig-natures. We first demonstrate that precomputation methods are extensible to post-quantum cryptography and are applicable on cur-rent energy-harvesting platforms. Then, we quantify its impact on energy, execution time, and the overall system yield. The results show that precomputation can improve the run-time latency and energy consumption up to a factor of 82.7 × and 11.8×, respectively. Moreover, for a typical energy-harvesting profile, it can triple the total number of generated signatures. We reveal that precompu-tation enables very complex and even probabilistic algorithms to achieve acceptable real-time performance on resource-constrained platforms. Thus, it will expand the scope of post-quantum algo-rithms to a broader range of platforms and applications.