A Comprehensive Comparison of Lattice-Based Password Authenticated Key Exchange Protocols Defined on Modules

Abstract

With the proposal of Shor algorithm, a new era has been started for the security of public-key cryptography. In the presence of large-scale quantum computers, it was proved that some computationally hard problems, such as discrete logarithm and factorization, will be solved, so public-key primitives will be insecure. Password-authenticated key exchange (PAKE) schemes whose security is generally defined under discrete logarithm problem have also been affected due to this ongoing process. To obtain a post-quantum secure PAKE scheme, lattice-based structures come to the fore due to the strong security guarantees and efficient solutions. In this paper, we compare three currently proposed Diffie-Hellman (DH)-like lattice-based PAKE schemes that were constructed based on module structure to provide guidance about efficient password-based authentication with lattice assumptions. By giving the algorithmic explanation of selected PAKEs, we deeply analyze proposed ideas according to the component-wise comparison in terms of reconciliation structure, hard lattice problem, and design idea. The implementation results of selected PAKEs are analyzed in terms of running time and computational costs. According to the experimental results, Kyber.PAKE gives the best performance in high security levels by considering execution time.