Multi-server Password authenticated Key Exchange Protocol Based on MLWE

Abstract

Currently, PAKE (Password Authenticated Key Exchange) protocols on lattice using a single-server architecture are widely applied. However, such protocols are vulnerable to server leakage attacks, dictionary attacks, and other threats. To address these issues, researchers have proposed multi-server and two-server architecture-based PAKE protocols. However, PAKE protocols in a multi-server architecture require the use of complex cryptographic primitives such as signatures, and zero-knowledge proofs to ensure security, which reduces the execution efficiency of the protocol. To tackle these challenges, we propose two new multi-server password authentication key exchange protocols based on the MLWE (Module learning with errors) problem. Both protocols rely on MLWE instances, using Peikert's error coordination technique to enable two parties with similar values to compute the same result. Furthermore, we introduce the error pairing assumption and proves its security within random oracle model. The proposed protocol divides the password information into different shares and stores them on separate servers. In protocol 1, all servers and user collaboratively generate session keys, making it suitable for high-security application scenarios. In protocol 2, both user and servers generate session keys individually, which is ideal for high-efficiency application scenarios. Compared to similar protocols, both protocols lower computation and communication costs, better addressing practical application needs while providing protection against quantum computing attacks and server leakage threats.