Post-Quantum Secure Server-aided Password-based Authentication using Module-LWE

Password-based authentication systems remain the most widely used method for user verification despite being highly susceptible to offline dictionary attacks. To mitigate such attacks, server-aided password-based authentication schemes utilize an independent server, which helps to harden the credentials to be stored on the website database. Existing server-aided password-based authentication schemes rely on number-theoretic assumptions that are vulnerable to quantum-enabled adversaries and incorporate complex computations such as bilinear pairings, exponentiation, and Zero-Knowledge Proofs. In this work, we introduce a novel post-quantum secure server-aided password-based authentication scheme based on the Module Learning With Errors (M-LWE) problem. A defining feature of our protocol is its complete operational transparency as it integrates with existing web interfaces without requiring users to modify their login behaviour or perform additional computation. To ensure long-term resilience, our scheme includes a transparent key rotation mechanism that allows service providers to update the entire credential database with a fresh secret key without user intervention. We provide a formal security analysis in the Real-or-Random (RoR) framework. This analysis demonstrates that our protocol’s resistance to offline dictionary attacks reduces to the underlying hardness of the M-LWE problem and the system achieves forward secrecy through key rotation mechanism. Through an optimized Number Theoretic Transformation (NTT)-based implementation for faster polynomial multiplications, our empirical analysis demonstrates high computational efficiency, with average registration and authentication latencies of 3.09 ms and 2.48 ms, respectively.