ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (10): 2086-2103.doi: 10.7544/issn1000-1239.2020.20200452

所属专题: 2020密码学与数据隐私保护研究专题

• 信息安全 • 上一篇    下一篇



  1. 1(山东大学数学学院 济南 250100);2(复旦大学计算机科学技术学院 上海 200433);3(密码技术与信息安全教育部重点实验室(山东大学) 济南 250100) (
  • 出版日期: 2020-10-01
  • 基金资助: 

Comparisons and Optimizations of Key Encapsulation Mechanisms Based on Module Lattices

Wang Yang1,3, Shen Shiyu2, Zhao Yunlei2, Wang Mingqiang1,3   

  1. 1(School of Mathematics, Shandong University, Jinan 250100);2(School of Computer Science, Fudan University, Shanghai 200433);3(Key Laboratory of Cryptologic and Information Security(Shandong University), Ministry of Education, Jinan 250100)
  • Online: 2020-10-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61672019, 61832012, 61877011, 61472084), the National Key Research and Development Program of China (2017YFB0802000), the National Cryptography Development Fund (MMJJ20180210), and the Shandong Provincial Key Research and Development Program of China (2017CXG0701, 2018CXGC0701).

摘要: 到目前为止,不使用复杂纠错码的基于模LWE/LWR问题设计的高效密钥封装方案主要有2类:1)如Kyber,Aigis和Saber直接基于(对称或非对称)模LWE/LWR问题设计;2)如AKCN-MLWE和AKCN-MLWR基于密钥共识机制结合模LWE/LWR问题设计.一般来说,在满足一定安全性和实现效率的基础上,实际应用中构造的密钥封装方案会通过压缩一些通信比特来达到节省通信带宽的目的.据作者所知,现存文献的关注点一般集中在详细分析对应某具体参数条件下密码体制的安全性,还没有文献系统地分析上述2类构造方式的异同以及采用相同(或不同)压缩函数情况下不同参数选择与错误率的关系.从理论上系统地比较了直接基于LWE/LWR构造的密钥封装方案和基于密钥共识机制结合模LWE/LWR问题设计的密钥封装方案的异同,并从理论分析和实际测试2方面证明了当采用相同的压缩函数和相同的参数设置时,AKCN-MLWE采用的构造方式要优于Kyber采用的构造方式,而Saber采用的构造方式本质上与AKCN-MLWR是相同的.针对Kyber-1024这一组参数对应的安全强度,还详细分析了3种封装512b密钥长度的方法.根据理论分析和大量的实验测试,给出了AKCN-MLWE和AKCN-MLWR的新的优化建议和参数推荐,也给出了对于Aigis和Kyber的优化方案(对应的命名为AKCN-Aigis和AKCN-Kyber)和新的参数推荐.

关键词: 后量子密码, 模LWE/LWR问题, 密钥封装方案, 密钥共识, 错误率分析

Abstract: Till now, there are two kinds of constructions of highly efficient key encapsulation mechanisms based on module LWE/LWR problems without using complicate error correcting codes: one is direct constructions based on (symmetric or asymmetric) module LWE/LWR problems such as Kyber, Aigis and Saber; the other is constructions based on key consensus mechanisms and module LWE/LWR problems such as AKCN-MLWE and AKCN-MLWR. In order to save bandwidth, the constructed key encapsulation mechanisms may usually compress the communications under tolerable security and efficiency. To the best of our knowledge, the existing literatures all focus on the security analysis of corresponding schemes under concrete parameters, and there are no literatures which focus on the analysis of similarities and differences about the above two kinds of constructions with the same (or different) compress functions, let alone the relationships between parameters and error rates. In this paper, we compare the above two kinds of constructions systematically. It is proved that constructions of AKCN-MLWE are better than constructions of Kyber when using the same compress functions and parameter settings from both theoretical analysis and practical tests. Meanwhile, similar analysis shows that the constructions of Saber are essentially the same as the constructions of AKCN-MLWR. Corresponding to the security strength of parameters recommended as Kyber-1024, we also analyze three kinds of methods about how to encapsulate 512 bits. Based on our theoretical analysis and a large number of experimental tests, we present new optimization suggestions and parameter recommendations for AKCN-MLWE and AKCN-MLWR. New optimized schemes corresponding to Aigis and Kyber (named AKCN-Aigis and AKCN-Kyber), and new recommended parameters are also proposed.

Key words: post-quantum cryptograph, module LWE/LWR problems, key encapsulation mechanisms, key consensus, error rates analysis