基于格的后量子密钥交换研究

Post-quantum Key Exchange from Lattice

理论上量子算法可高效破解基于整数分解类和离散对数类等经典数论假设的密码体制;近年来量子计算机的研制进展迅速,使经典公钥密码面临现实威胁.因此,设计后量子密码系统是当前密码学研究以及标准制定中的重要课题.其中以后量子密钥交换协议的需求最为迫切,因此成为近年来的热点研究方向.本文主要关注基于格上的计算困难问题,LWE,环LWE和模LWE设计的后量子密钥交换协议,尤其是最基础的无认证密钥交换协议,包括BCNS15,NewHope/NewHope-Simple,Prodo,Kyber.KE等.本文将介绍这些协议中的关键技术,参数选取,以及通信量,计算效率和安全性等指标.

Cryptosystems based on classical number-theoretical assumptions, such as integer factoring and discrete logarithm, can be broken by quantum algorithms efficiently in theory, while the rapid development of quantum computers is becoming threats of classical cryptosystems in practice.Thus, the design of post-quantum cryptosystems is an important(or even urgent) research direction of cryptography, wherein the most urgent is the need for post-quantum key exchange protocols,which is a hot topic in recent years. In this paper we mainly focus on the post-quantum protocols from computational hard problems on lattices, such as LWE, ring-LWE, and module-LWE, especially the most-basic unauthenticated key exchange protocols, such as BCNS15, NewHope/NewHope-simple,Frodo, and Kyber.KE. We will introduce the key techniques, the choice of parameters, communication costs, computation efficiency and security of these protocols.