|随着量子理论研究的突破性进展，基于经典数学问题的公钥密码体制将在多项式时间内被破解，设计抵御量子攻击的后量子密码算法愈加紧迫。基于格构造的密码方案可以有效抵抗量子计算机攻击，具有可移植性强、易于实现等优点，已成为当前研究的热点。提出了一种基于格上Ring Learning with Errors（RLWE）问题的三方口令认证密钥交换（Three-party Password Authenticated Key Exchange, 3PAKE）协议，使用D4格解码方法构造错误协调机制，通过口令提供服务器和客户端之间的身份认证，最终在客户端之间生成会话密钥。在Bellare Pointcheval Rogaway（BPR）模型中，证明了协议满足相互认证安全、弱完美前向安全、会话密钥安全，且能抵抗口令猜测字典攻击。与其他基于RLWE的口令认证密钥交换协议相比，设计的隐式认证结构显著减少了哈希计算次数，采用的误差协调机制允许更大的容错距离，在平衡维度、模数、标准差、错误率并选择合适的参数之后，将协议错误率降低至2-61，模数缩小至12289，进一步减少了计算量与通信量。在C++上结合NFL（NTT-based Fast Lattice）加速算法对协议进行了实现，实验结果表明，协议实现了高达17倍的加速，具有255比特量子安全性。
|关键词: RLWE 后量子密码学 三方口令认证密钥交换
|A RLWE-based Three-party Password Authenticated Key Exchange scheme
Wang Ziliang1,2, Gu Xiaozhuo1,2, Ren Peixin1,2
|(1.State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences;2.School of Cyber Security, University of Chinese Academy of Sciences)
|With breakthroughs in quantum theory research, public key cryptosystems based on classical mathematical problems can be cracked in polynomial time. It becomes very urgent to design post-quantum cryptographic algorithms that can resist quantum attacks. Lattice-based cryptographic algorithms can effectively resist quantum computer attacks, has some excellent properties such as strong portability and easy-to-implement characteristics, and has become a current research hotspot. This paper proposes a Three-party Password Authenticated Key Exchange (3PAKE) protocol based on the Ring Learning with Errors (RLWE) problem, which introduces the D4 lattice as reconciliation mechanism, provides identity authentication between the server and two clients through pre-stored passwords, and enables the participants to establish the session key. In the Bellare Pointcheval Rogaway (BPR) model, it is proved that the protocol has mutual authentication security, weak perfect forward secrecy, session key security and resilience to password guessing attacks. Compared with other RLWE-based authenticated key exchange protocols, the implicit authenticatied scheme significantly reduces the number of hash calculations, and the error reconciliation mechanism allows higher error tolerance. After balancing the dimensions, modulus, variance, error rate and selecting appropriate parameters, the error rate is reduced to 2-61 and the modulus is reduced to 12289, which further decreases the amount of calculation and communication complexity. The protocol is implemented in C++ with NFL (NTT-based Fast Lattice) acceleration algorithm. The results in practice show the protocol achieves at most 17x speedup and provides 255-bit quantum security.
|Key words: ring learning with errors post-quantum cryptography three-party password authenticated key exchange