Paper 2020/140

PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model

Shaoquan Jiang, Guang Gong, Jingnan He, Khoa Nguyen, and Huaxiong Wang


Password-based authenticated key exchange (PAKE) allows two parties with a shared password 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 efficiency. In this work, we first 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 efficient than previous proposals, thanks to three novel technical ingredients that may be of independent interests. The first ingredient consists of two approximate smooth projective hash (ASPH) functions from LWE, as well as two ASPHs from Ring-LWE. The latter are the first ring-based constructions in the literature, one of which only has a quasi-linear runtime while its function value contains $\Theta(n)$ field elements (where $n$ is the degree of the polynomial defining the ring). The second ingredient is a new key conciliation scheme that is approximately rate-optimal and that leads to a very efficient key derivation for PAKE protocols. The third one is a new authentication code that allows to verify a MAC with a noisy key.

Note: This revision adds a new reference [11].

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2020
authenticationlattice and ideal lattice techniqueskey exchangepassword
Contact author(s)
shaoquan jiang @ gmail com
2020-02-19: revised
2020-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shaoquan Jiang and Guang Gong and Jingnan He and Khoa Nguyen and Huaxiong Wang},
      title = {PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2020/140},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.