Cryptology ePrint Archive: Report 2020/140

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

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

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 $\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.

Category / Keywords: cryptographic protocols / authentication, lattice and ideal lattice techniques, key exchange, password

Original Publication (with major differences): IACR-PKC-2020

Date: received 9 Feb 2020, last revised 19 Feb 2020

Contact author: shaoquan jiang at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20200219:154010 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]