Standard Lattice-Based Key Encapsulation on Embedded Devices
Standard Lattice-Based Key Encapsulation on Embedded Devices
复制标题
DOI：
10.13154/tches.v2018.i3.372-393
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
James Howe;Tobias Oder;Markus Krausz;Tim Güneysu
中科院分区：
文献类型：
--
作者：
James Howe;Tobias Oder;Markus Krausz;Tim Güneysu
基于晶格的密码学是在量子计算时代替代当前公钥系统的最有前途的候选人之一。在2016年，Bos等人。提出了关键交换方案FrodoCC，这也是对NIST量子后标准化过程的提交，被修改为关键封装机制（Frodokem）。该方案的安全性基于标准晶格和错误问题的学习。由于参数较大，因此长期以来，基于标准的晶格方案在嵌入式设备上被认为是不切实际的。 Frodokem提案实际上带有参数，这些参数带来了基于标准的晶格密码学，可以在受限的设备上可行。在这项工作中，我们采取了在低成本FPGA和微控制器设备上有效实施该方案的最后一步，从而使保守的量子后加密术在小型设备上实用。我们的FPGA实现（计算上最昂贵的操作）需要7,220个查找表（LUTS），3,549个触发器（FFS），单个DSP和仅16个块RAM模块。最大时钟频率为162 MHz，执行解码需要20.7 ms。与参考实现相比，我们的微控制器实现的峰值堆栈使用量减少了66％，并且需要266毫秒的密钥对生成，284毫秒的封装和286毫秒的拆分。我们的结果有助于对量子后标准化候选者的实际评估。
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.