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

• Main Authors: Jiang, Shaoquan, Gong, Guang, He, Jingnan, Nguyen, Khoa, Wang, Huaxiong
• Other Authors: School of Physical and Mathematical Sciences
• Format: Conference or Workshop Item
• Language: English
• Published: 2021
• Subjects: Science::Physics
• Online Access: https://hdl.handle.net/10356/152460
• Institution: Nanyang Technological University

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.