International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Shaoquan Jiang
Guang Gong
Jingnan He
Khoa Nguyen
Huaxiong Wang
DOI: 10.1007/978-3-030-45374-9_14
Search ePrint
Search Google
Abstract: 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 $$varTheta (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.
Video from PKC 2020
  title={PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model},
  booktitle={Public-Key Cryptography – PKC 2020},
  series={Public-Key Cryptography – PKC 2020},
  author={Shaoquan Jiang and Guang Gong and Jingnan He and Khoa Nguyen and Huaxiong Wang},