International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Standard Lattice-Based Key Encapsulation on Embedded Devices

Authors:
James Howe , Department of Computer Science, University of Bristol
Tobias Oder , Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
Markus Krausz , Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
Tim Güneysu , Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
Download:
DOI: 10.13154/tches.v2018.i3.372-393
URL: https://tches.iacr.org/index.php/TCHES/article/view/7279
Search ePrint
Search Google
Abstract: Lattice-based cryptography is one of the most promising candidates being considered to replace current public-key systems in the era of quantum computing. In 2016, Bos et al. proposed the key exchange scheme FrodoCCS, that is also a submission to the NIST post-quantum standardization process, modified as a key encapsulation mechanism (FrodoKEM). The security of the scheme is based on standard lattices and the learning with errors problem. Due to the large parameters, standard latticebased schemes have long been considered impractical on embedded devices. The FrodoKEM proposal actually comes with parameters that bring standard lattice-based cryptography within reach of being feasible on constrained devices. In this work, we take the final step of efficiently implementing the scheme on a low-cost FPGA and microcontroller devices and thus making conservative post-quantum cryptography practical on small devices. Our FPGA implementation of the decapsulation (the computationally most expensive operation) needs 7,220 look-up tables (LUTs), 3,549 flip-flops (FFs), a single DSP, and only 16 block RAM modules. The maximum clock frequency is 162 MHz and it takes 20.7 ms for the execution of the decapsulation. Our microcontroller implementation has a 66% reduced peak stack usage in comparison to the reference implementation and needs 266 ms for key pair generation, 284 ms for encapsulation, and 286 ms for decapsulation. Our results contribute to the practical evaluation of a post-quantum standardization candidate.
BibTeX
@article{tches-2018-29069,
  title={Standard Lattice-Based Key Encapsulation on Embedded Devices},
  journal={IACR Trans. Cryptogr. Hardw. Embed. Syst.},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 3},
  pages={372-393},
  url={https://tches.iacr.org/index.php/TCHES/article/view/7279},
  doi={10.13154/tches.v2018.i3.372-393},
  author={James Howe and Tobias Oder and Markus Krausz and Tim Güneysu},
  year=2018
}