Comparisons and Optimizations of Key Encapsulation Mechanisms Based on Module Lattices

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.