PAKEs : new framework, new techniques and more efficient lattice-based constructions in the standard model

Abstract

Password-based authenticated key exchange (PAKE) allows two parties with a shared pass- word to agree on a session key. In the last decade, the design of PAKE protocols from lattice assumptions has attracted lots of attention. However, existing solutions in the standard model do not have appealing e ciency. In this work, we rst introduce a new PAKE framework. We then provide two realizations in the standard model, under the Learning With Errors (LWE) and Ring-LWE assumptions, respectively. Our protocols are much more e cient than previous proposals, thanks to three novel technical ingre- dients that may be of independent interests. The rst ingredient consists of two approximate smooth projective hash (ASPH) functions from LWE, as well as two ASPHs from Ring-LWE. The latter are the rst ring-based constructions in the literature, one of which only has a quasi-linear runtime while its function value contains Θ(n) eld elements (where n is the degree of the polynomial de ning the ring). The second ingredient is a new key conciliation scheme that is approximately rate-optimal and that leads to a very e cient key derivation for PAKE protocols. The third one is a new authentication code that allows to verify a MAC with a noisy key.