ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (10): 2086-2103.doi: 10.7544/issn1000-1239.2020.20200452

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

Previous Articles     Next Articles

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).

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

CLC Number: