基于模格的密钥封装方案的比较分析与优化

Comparisons and Optimizations of Key Encapsulation Mechanisms Based on Module Lattices

到目前为止,不使用复杂纠错码的基于模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种封装512 b密钥长度的方法.根据理论分析和大量的实验测试,给出了AKCN-MLWE和AKCN-MLWR的新的优化建议和参数推荐,也给出了对于Aigis和Kyber的优化方案(对应的命名为AKCN-Aigis和AKCN-Kyber)和新的参数推荐.

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.