Cryptology ePrint Archive: Report 2018/677

Module-lattice KEM Over a Ring of Dimension 128 for Embedded Systems

François Gérard

Abstract: Following the development of quantum computing, the demand for post-quantum alternatives to current cryptosystems has firmly increased recently. The main disadvantage of those schemes is the amount of resources needed to implement them in comparison to their classical counterpart. In conjunction with the growth of the Internet of Things, it is crucial to know if post-quantum algorithms can evolve in constraint environments without incurring an unacceptable performance penalty. In this paper, we propose an instantiation of a module-lattice-based KEM working over a ring of dimension 128 using a limited amount of memory at runtime. It can be seen as a lightweight version of Kyber or a module version of Frodo. We propose parameters targeting popular 8-bit AVR microcontrollers and security level 1 of NIST. Our implementation fits in around 2 KB of RAM while still providing reasonable efficiency and 128 bits of security, but at the cost of a reduced correctness.

Category / Keywords: KEM Module lattices AVR embedded

Date: received 13 Jul 2018, last revised 19 Jul 2018

Contact author: fragerar at ulb ac be

Available format(s): PDF | BibTeX Citation

Note: A flaw in this work as been pointed out by Leo Ducas. The CCA secure transformation cannot be applied to a scheme with such a low correctness. Hence, only results about the CPA version of the KEM are relevant.

Version: 20180719:141451 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]