Provably secure verifier-based password authenticated key exchange based on lattices

Abstract Verifier-based Password Authenticated Key Exchange (VPAKE) protocol enables users to generate a session key over insecure channels, which can limit the impact of server's information leakage. However, most existing VPAKE protocols are based on the integer factorization problem and the discrete logarithm problem; they cannot resist attack by quantum computers. In this chapter, we propose a new VPAKE protocol based on lattices. The protocol is constructed by using Chosen-Ciphertext Attacks (CCA) secure public-key encryption scheme, which is based on the learning with errors problem and an associated approximate smooth projective hash. Furthermore, this protocol uses a new randomized password hashing scheme based on lattices. This scheme enables ASCII-based passwords and a zero-knowledge password policy check; it allows users to prove the compliance of their password without revealing any information. Meanwhile, through explicit mutual authentication between the users and the servers, the protocol can resist undetectable online dictionary attacks. We then prove the security of this protocol. Our new protocol only involves three-round interactions with mutual explicit authentication. In addition, it avoids vulnerability of cryptosystem based on the integer factorization problem, and it is robust against quantum attacks.