大型量子计算机和高效的量子算法被认为可以快速完全攻破目前广泛使用的一系列基于离散对数问题、大整数分解问题、椭圆曲线离散对数问题等的公钥密码算法,并降低对称密码算法的安全性。随着量子计算机研究、设计和制造等技术的迅速发展,量子计算机对于目前的密码算法的威胁越来越大。在真实世界中,大量的公钥密码和对称密码算法被应用于各类安全协议、应用和设备中。受到直接威胁的公钥密码算法包括且不限于:公钥加密、密钥交换、数字签名等,重要的安全协议和应用包括且不限于:HTTPS、SSH、系统和软件安全、区块链、物联网等。在量子计算机上,Shor的量子算法和Grover的量子算法及其变种对目前广泛使用的密码算法体制威胁最大,其中Shor的量子算法对目前广泛使用的公钥密码算法造成了极大的真实的威胁。这要求密码学界给出应对措施,即用属于后量子密码学(Post-quantum Cryptography)的新算法抵抗经典和量子计算机的攻击。实现后量子密码学的技术手段主要包括:基于哈希(Hash-based)、基于编码(Code-based)、基于多变量(Multivariate-based)、基于格(Lattice-based)等。这四种方法各有其利弊。目前认为,在上述四种实现后量子密码算法的技术中,基于格的密码算法可以实现更强的安全性、更小的总通信开销、更快的计算速度和更多样化的密码算法设计。目前,美国国家标准技术研究所(National Institute of Standards and Technology,NIST)启动了全球范围内的后量子公钥密码算法标准征集,主要关注后量子公钥加密、密钥交换和数字签名算法。RLWE问题是一个新型的高效的格困难问题。本文主要关注基于RLWE问题的非身份认证密钥交换协议和增强型基于口令的身份认证密钥交换协议两个方面,研究、设计并实现新的后量子密钥交换协议及应用。非身份认证密钥交换协议:设计并实现安全性高、通信开销小、计算性能高的非身份认证密钥交换协议始终是研究的热点和难点,也是真实世界的安全协议和应用中最需要的协议。由于基于RLWE问题的密钥交换协议的一个重要技术是错误消除,即双方如何从近似相等的元素中计算得到相同的共享密钥,因此错误消除问题是一个重要的研究方向。如何给出基于RLWE问题的密钥交换协议的框架设计、错误消除、参数选取、安全性评估、快速工程实现以及和相关工作的对比是目前主要的研究方向。①本文对目前主要的基于RLWE问题的密钥交换协议,从算法设计细节、错误消除算法的区别、错误容忍度、参数选择和对应的安全性级别、工程实现、其他实践中的问题等进行了全面的对比分析。本文为经典的DING12密钥交换协议的RLWE版本选取了2套参数,分别达到大于300和200比特安全,并对两个实例化进行了快速工程实现。本文给出的实现可以在0.1 ms左右完成密钥交换计算,比类似协议的计算速度最多快10倍左右。本文与不能抵抗量子计算机攻击的公钥交换/加密算法进行了安全性、通信开销、计算开销的详细对比,展示了目前后量子密钥交换协议的实际计算开销、通信开销和安全性强度,为基于RLWE问题的密钥交换协议研究打下基础。②本文从对比分析中的已有基础和指出的研究方向入手,结合基于RLWE问题的密钥交换协议设计和安全性分析方法,给出了新的基于RLWE+Rounding方法的类Diffie-Hellman的密钥交换协议设计、参数选取、安全性评估方法、被动安全性证明和工程实现。本文的构造与只基于RLWE的构造相比,通信开销至少降低25%,且参数达到了更高的安全性。与相关工作相比,本文的新协议的通信开销至少降低10%,因此新的协议在安全性、计算开销、通信开销等方面取得了更好的平衡。此外,本文中新提出的参数安全性方法将RLWE+Rounding实例转化为SIS实例,再使用格基归约算法的开销进行评估,解决了针对唯一 RLWE+Rounding实例的参数安全性分析问题中,现有方法不能适用此情况(唯一实例、RLWE+Rounding实例)造成分析结果不准确的问题。③本文针对基于错误消除方法的RLWE密钥交换协议在公私钥对重复使用时会受到私钥恢复攻击的情况,构造了新的可以抵抗私钥恢复攻击的密钥交换协议,给出了协议设计、参数选取、安全性评估结果、随机性测试结果和工程实现。在相同的攻击和公私钥对复用的情况下,新的协议的通信传输内容与均匀随机不可区分,且相同的攻击无法恢复出私钥。新协议共有两种模式:常规模式和复用模式。其中,复用模式的性能和通信开销与相关工作相比有数倍的提升。新协议解决了目前缺少实用的可以抵抗私钥恢复攻击的基于RLWE问题的类Diffie-Hellman密钥交换协议的问题。增强型基于口令的身份认证密钥交换协议:可以抵抗量子计算机攻击的增强型基于口令的身份认证密钥交换协议是重要安全应用最迫切需要的。目前广泛应用于AppleiCloud、1Password、ProtonMail、TLS等安全应用和协议中的安全远程口令协议(Secure Remote Password,SRP)协议不能抵抗量子计算机攻击,因此设计实现实用的SRP协议的后量子变种具有重要的意义。SRP协议是增强型的基于口令的身份认证密钥交换协议,可以实现非增强型的基于口令的身份认证密钥交换协议不能实现的安全属性,例如:服务器端不存储用户的密码(或密码的哈希值等),即使服务器端令牌被盗或遗失,敌手无法利用令牌冒充真正的用户完成身份认证操作;在协议的执行过程中,用户无需向服务器端发送密码(或密码的哈希值等)等。本文结合基于RLWE问题的密钥交换协议和安全远程口令协议的设计原理、思想和实现方法,提出了基于RLWE问题的安全远程口令协议。新协议在可以抵抗量子计算机攻击的同时,继承了所有经典安全远程口令协议的特性。本文给出了协议的设计、209-bit安全的参数选取、安全性分析、快速工程实现,并与经典的安全远程口令协议、非增强型的经典/后量子基于口令的身份认证密钥交换协议进行了安全性、性能、通信开销等方面的对比。与同样基于RLWE问题的非增强型PAKE协议相比,安全性更好,通信开销更小,且计算性能有近14倍的提升。与经典的安全远程口令协议相比,新协议的参数安全性更高,计算性能有近3倍的提升,且能够抵抗量子计算机的攻击。