基于格陷门的高效密钥封装算法

The Efficient Key Encapsulation Algorithm from the Lattice Trapdoor

量子计算机的深入研究已经威胁到基于离散对数和大整数分解问题的传统公钥密码,美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)于2017年开始了后量子密码算法征集,希望从全球提交的算法中评选出可以代替传统公钥密码的后量子公钥密码标准。在征集的后量子密码算法中,基于格的密码算法占比最多,基于格的密码算法具有抵抗量子算法攻击、困难问题存在“最坏情形”到“平均情形”的安全归约、计算简单等优势,是后量子密码算法中最具应用前景的密码算法。目前为止,提交的基于格的密钥封装算法均需要去随机化、误差采样等操作。去随机化即将底层概率性加密算法,通过引入随机喻言机模型(Random Oracle Model,ROM),将加密算法转化为确定性算法,以实现量子随机喻言机模型下的安全归约。误差采样指模空间上的离散高斯采样,在基于格的公钥加密中,通常需要特殊的算法设计,以满足加密算法性能与安全性需求。去随机化和误差采样操作既降低了算法运行效率,又增加了遭受侧信道攻击的风险。本文基于格的单向陷门函数,设计并实现了高效密钥封装算法,算法避免了去随机化和误差采样等操作,从算法设计层面提升了方案的效率。首先,本文提出了针对密钥封装算法设计场景的格上单向陷门优化技术,显著减小了格陷门的长度;其次,基于优化的格上陷门单向函数,构造了高效的量子随机喻言机模型(Quantum Random Oracle Model,QROM)下选择密文攻击不可区分安全(Indistinguishability against Chosen Ciphertext,IND-CCA)的密钥封装方案;最后,对密钥封装方案进行了攻击分析和实用参数设置分析,并对方案进行了软件实现和性能分析。

The in-depth study of quantum computers has threatened the traditional public key cryptography based on the discrete logarithm or large integer factor problem.National Institute of Standards and Technology(NIST)has announced a competition for the post-quantum cryptography from 2017,which hopes to select the post-quantum public key cryptography standard which can replace the traditional public key cryptography from the algorithms submitted worldwide.The lattice-based cryptography algorithms account for the largest proportion among the collected post-quantum cryptography algorithms.Lattice-based cryptography is one of the most promising post-quantum cryptography algorithms because of its advantages of resisting attacks from quantum algorithms,security reduction from“worst-case”to“average-case”for dif-ficult problems,and simplicity of calculation.However,up to now,these lattice-based key encapsulation algorithms need de-randomization and error sampling.De-randomization refers to the conversion of the underlying probabilistic encryption algorithm into a deterministic algorithm by introducing the random oracle model,so as to realize the security reduction under the quantum random oracle model.Error sampling refers to discrete Gaussian sampling in modular space.In the lattice-based public key encryption,special algorithm design is usually required to meet the performance and security requirements of encryption algorithm.These two operations not only reduce the efficiency of the algorithm,but also increase the risk of the side channel attack.In this paper,we design and implement an efficient key encapsulation algorithm,which avoids the de-randomization and error sampling,from the lattice-based one-way trapdoor function.Then,we improve the efficiency of our key encapsulation mechanism(KEM)from the algorithm design.Concretely,we first optimize the lattice-based one-way trapdoor function for designing the KEM.Then,we construct the efficient KEM,which satisfies the indistinguishability security against chosen ciphertext attack(IND-CCA)in the quantum random oracle model(QROM),based on the optimizing one-way trapdoor function.Finally,we analyze the security of the KEM by attack methods,propose the practical parameters for the scheme,give a reference implementation and analyze the performance of our scheme.